선형 구조
자료구조에는 선형 구조와 비선형 구조가 있다. 선형 구조(linear structure) 말처럼 일렬로/한줄로 이루어진 자료구조를 말한다. 자료와 자료의 관계가 1:1인 특징이 있다. 우리가 많이 쓰는 배열도 사실 선형 구조라고 말할 수 있다.
반대로 비선형 구조는 일렬이 아닌, 자료와 자료의 관계가 여럿 얽혀있는 그물같은 구조라고 할 수 있다.
오늘은 선형 구조의 대표격이라고 할 수 있는 스택을 알아보고자 한다.
1000스택 나서스
리그오브 레전드에는 나서스 라는 캐릭터가 있다. 이 캐릭터의 특징으로는
Q 스킬로 공격할수 있는 유닛을 처치하면 중첩이 쌓이고, 이 중첩의 수만큼 공격력이 증가한다. 이 과정을 '스택을 쌓는다'고 표현한다.
이처럼 스택은 특정한 공간 안에 물건을 차곡차곡 쌓는것 이라고 말 할 수 있다. (나서스도 나름 공격 포인트에 중첩을 쌓으니까,,)
일상생활 속에서 스택을 찾아보자면,, 이런 느낌?
스택의 성질
스택은 가장 먼저 들어온 자료가 가장 밑에 있고, 또 가장 늦게 나가는 구조이다. 위에서 본 사진들 중 종이컵 사진을 보자. 맨 밑에 있는 종이컵이 위에 종이컵에 눌리고, 또 그 위에 종이컵이 있다. 맨 밑에 종이컵을 빼기 위해서는 위에 두 종이컵을 빼야 사용할 수 있다.
이러한 방식을 후입선출이라고 부른다. (Last In First Out)
스택을 구현하는 방법에는 배열과 연결리스트가 있지만, 오늘은 배열만 알아볼 것이다.
스택은 어떻게 만들까?
스택은 top이라는 변수를 활용해 자료의 삽입과 삭제를 '강제'시킨다.
top은 가장 최근에 들어온 자료의 인덱스를 가리킨다. 자료를 삽입하면 top에 1을 더한곳에 자료를 넣어주고, 자료를 삭제하면 top은 1을 뺀 곳을 가리킨다. 사실 배열 속에 자료는 있지만, top 변수를 통해 자료를 없는것처럼 '취급'하는 것이다.
스택에 쓰이는 함수들
다른 기능이 있는 함수들도 여럿 있지만, 보편적으로는 아래 4개를 주로 사용한다.
- 스택이 비어있는지 확인해주는 is_empty()
- 스택이 가득 차있는지 확인해주는 is_full()
- 스택에 자료를 넣을때 사용하는 push()
- 스택에서 자료를 뺄때 사용하는 pop()
하나씩 코드를 살펴보며 이해해보자
is_empty 함수
#define MAX_SIZE 100
element stack[MAX_SIZE];
int top = -1;
int is_empty() {
if(top == -1) return 1;
else return 0;
}배열은 0번째 인덱스부터 시작하기 때문에 top 변수의 초기값을 -1로 잡아주고, 만약에 top이 초기값인 경우에는 1을, 아니면 0을 리턴해서 비어있는지 알려주는 함수이다.
is_full 함수
#define MAX_SIZE 100
element stack[MAX_SIZE];
int top = -1;
int is_full() {
if(top == MAX_SIZE - 1) return 1;
else return 0;
}배열을 100으로 선언하는 것은 "100개의 공간을 만들게요~"와 같기 때문에 인덱스는 0부터 시작해서 99까지 만들어진다. 그러므로 top이 99까지 온다면 선언한 배열을 모두 채웠으므로 할당한 공간을 모두 사용했으므로 top이 MAX_SIZE -1 까지 왔다면 1을, 아니면 0을 리턴해서 가득 찼는지 알려준다.
push 함수
#define MAX_SIZE 100
element stack[MAX_SIZE];
int top = -1;
int is_full() {
if(top == MAX_SIZE - 1) return 1;
else return 0;
}
void push(int value){
if (is_full() == 1) printf("오버플로우\n");
else stack[++top] = value;
}is_full 함수를 사용해 가득 찼다면 오버플로우를 출력해주고, 아니라면 top을 1만큼 올린 위치에 매개변수로 들어온 value 값을 넣어준다.
pop 함수
#define MAX_SIZE 100
element stack[MAX_SIZE];
int top = -1;
int is_empty() {
if(top == -1) return 1;
else return 0;
}
element pop(){
if (is_empty() == 1){
printf("언더플로우\n");
return;
}
else return stack[top--];
}is_empty 함수를 사용해 비어있다면 언더플로우를 출력해주고, 아니라면 현재 위치에 있는 값을 리턴해준 후 top에서 1을 뺀 위치로 top을 옮겨준다.
element는 자료형일 뿐이라 신경쓰지 않아도 된다,, 정수면 int, 문자형이면 char,,,
이런 느낌으로 top 변수를 올리고 내리면서 자료를 관리하는것이 스택이다.
스택 전체 코드
#define MAX_SIZE 100
element stack[MAX_SIZE];
int top = -1;
int is_empty() {
if(top == -1) return 1;
else return 0;
}
int is_full() {
if(top == MAX_SIZE - 1) return 1;
else return 0;
}
void push(int value){
if (is_full() == 1) printf("오버플로우\n");
else stack[++top] = value;
}
int pop(){
if (is_empty() == 1){
printf("언더플로우\n");
return;
}
else return stack[top--];
}
int main(){
push(10);
push(30);
printf("%d\n", pop());
push(20);
printf("%d\n", pop());
printf("%d\n", pop());
}다음 스택 코드는 어떤 결과를 출력할까?
10, 30을 삽입해서 스택에는 [10, 30]이 남아있고, 여기서 pop을 해주면 30이 출력된 후 top은 10을 가리키게 된다.
20을 삽입하면 top은 다시 20을 가리키고, pop을 두번 해주면 나중에 들어온 순서대로 20, 10을 출력하고 스택은 비워지게 된다.
출력 결과는 다음과 같다.
30
20
10
배열 방식 -> 구조체
배열로 만든 스택의 단점이라고 한다면 여러개의 스택을 동시에 사용하기 어렵고, 저장할 때 다양한 자료형을 동시에 저장할 수 없다는 것이다.
객체지향 언어를 사용한다면 클래스를 만들어서 객체를 찍어낼 수 있지만, 우리 C언어는 그런게 없기 때문에 구조체를 사용해 만들 수 있다.
#include <stdio.h>
#define MAX_SIZE 100
struct element {
char name[20];
int num;
} stack[MAX_SIZE];
int top = -1;
int is_empty() {
if (top == -1) return 1;
else return 0;
}
int is_full() {
if (top == MAX_SIZE - 1) return 1;
else return 0;
}
void push(struct element data) {
if (is_full() == 1) printf("오버플로우\n");
else stack[++top] = data;
}
struct element pop() {
if (is_empty() == 1) printf("언더플로우\n");
else return stack[top--];
}
int main() {
struct element data, popData;
for (int i = 0; i < 5; i++) {
scanf("%s %d", data.name, &data.num);
push(data);
}
for (int i = 0; i < 5; i++) {
popData = pop();
printf("%s %d\n", popData.name, popData.num);
}
}구조체를 사용해 여러 데이터를 한 묶음으로 스택에 쌓고싶다면 이렇게,
#include <stdio.h>
#define MAX_element_SIZE 100
typedef int element;
struct element {
int data[MAX_element_SIZE];
int top;
};
void init_stack(struct element *p) {
p->top = -1;
}
int is_empty(struct element *p) {
if (p->top == -1) return 1;
else return 0;
}
int is_full(struct element *p) {
if (p->top == (MAX_element_SIZE - 1)) return 1;
else return 0;
}
void push(struct element *p, int value) {
if (is_full(p)) printf("오버플로우");
else p->data[++(p->top)] = value;
}
element pop(struct element *p) {
if (is_empty(p)) printf("언더플로우");
else return p->data[(p->top)--];
}
int main(void) {
struct element s;
int n;
init_stack(&s);
for (int i = 0; i < 5; i++) {
scanf("%d", &n);
push(&s, n);
}
for (int i = 0; i < 5; i++) {
printf("%d\n", pop(&s));
}
}여러개의 스택을 쓰고 싶을 때는 이런 느낌으로 사용하면 좋을 것 같다.
init_stack() 함수는 구조체 안에 있는 top 변수를 초기화하기 위한 함수에요 !!
마무리
스택은 top 변수의 위치에 바로 접근이 가능하기 때문에 시간복잡도는 O(1)로 매우 빠르지만, 원하는 데이터에 접근하기 위해서는 하나하나 pop 하면서 살펴봐야 하기에 이 부분은 단점이라고 할 수 있다.
스택은 많은 부분에서 사용하는 자료구조이기 때문에 개발자라면 꼭 숙지하고 다니는 것을 추천한다.
개웃기네 ㅋㅋ