스택의 정의
"스택"은 컴퓨터에서 굉장히 많이 사용하는 자료구조 중 하나입니다. 대표적으로 인터넷에서 뒤로 가기를 누르면 현재 진행되는 웹에서 이전에 수행되던 웹사이트로 돌아갑니다. 이것이 스택의 예시 중 하나입니다. 스택은 '쌓다, 더미'라는 뜻을 가지고 있는데, 이에 뜻에 걸맞게 스택은 데이터를 차곡차곡 쌓아올린 형태인 자료구조입니다.
창고에 쌓여있는 상자를 예시로 들어봅시다. 창고에 새로운 상자를 쌓을 때는 상자의 가장 윗 부분에 놓습니다. 그리고 필요하다면 상자더미에서 가장 위에 있는 상자를 꺼내게 됩니다. 그렇지 않고 상자더미의 가장 아래에 있는 상자를 꺼낸다면 상자더미는 붕괴될 것입니다. 이러한 형태를 후입선출(LIFO: Last-In First-Out)이라고 합니다. 스택 자료구조는 이러한 후입선출(LIFO) 형태를 따릅니다.
후입선출 원리에 따라 스택에서의 입출력은 가장 위에서만 일어나며, 스택의 중간에서는 데이터를 삭제할 수 없습니다. 스택에서 입출력이 일어나는 부분을 스택 상단(Stack Top)이라고 하고, 스택의 바닥 부분을 스택 하단(Stack Bottom)이라고 합니다. 이때, 스택에 저장되는 것을 요소(Element)라고 부르며, 요소가 하나도 없을 때의 스택을 공백 스택(Empty Stack)이라고 합니다.
그렇다면 이러한 스택은 어떤 부분에 많이 사용될까요? 바로 "자료의 출력순서가 입력순서의 역순으로 이루어져야 할 때에 주로 사용됩니다." 예를 들면 "뒤로 가기 버튼", "되돌리기" 같은 기능을 구현할 대 스택이 사용됩니다.
push 연산과 pop 연산
스택에는 두 가지의 기본 연산이 있습니다. 바로 "push 연산"과 "pop 연산"입니다.
push 연산
push 연산은 삽입 연산으로서 비어있는 스택에 데이터(A)를 삽입합니다. 이렇게 비어있는 스택에 데이터를 삽입한 후, 또 push 연산을 실행하면 데이터(A) 위에 새로운 데이터(B)가 쌓이게 됩니다. 이러한 식으로 계속 진행하면 많은 양의 데이터가 쌓이게 되는데 만약 push 연산 중 스택이 가득차서 입력이 불가능하면 오류가 발생하게 됩니다.
pop 연산
pop 연산은 삭제 연산으로서 가장 위에 있는 스택 데이터, 즉 스택 상단의 데이터를 삭제합니다. pop 연산은 항상 가장 위에 있는 데이터를 삭제하며, 그렇게 삭제를 계속하다 보면 스택이 비어있는 상태가 되는데, 이때 pop 연산을 수행하면 출력이 불가능하기에 오류가 발생하게 됩니다.
스택의 구현
지금부터 본격적으로 스택을 구현해보도록 하겠습니다. 스택을 구현하기 위해서는 여러가지 연산을 구현해야 합니다. 실제로 먼저 스택을 정의해야하고, push 연산, pop 연산 그리고 스택이 비어있는지 확인하는 empty 연산, 스택이 가득 찼는지 확인하는 full 연산, 스택의 가장 맨 위 요소를 반환하는 peek 연산이 필요합니다. 스택을 구현하기 전 필요한 것들을 확인했으니 지금부터 c언어를 통해서 스택을 구현하겠습니다.
#include <stdio.h>
#include <stdlib.h>
// ========== 스택 코드 시작 ==========
#define MAX_STACK_SIZE 100
// 스택이 구조체로 정의된다.
typedef int element;
typedef struct {
element data[MAX_STACK_SIZE];
int top;
} StackType;
// 스택 초기화 함수
void init_stack(StackType *s) {
s->top = -1;
}
// 모든 연산은 구조체의 포인터를 받는다.
// 공백 상태 검출 함수
int is_empty(StackType *s) {
return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s) {
return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입 함수
void push(StackType *s, element item) {
if (is_full(s)) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
else s->data[++(s->top)] = item;
}
// 삭제 함수
element pop(StackType *s) {
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[(s->top)--];
}
// 피크 함수
element peek(StackType *s) {
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[s->top];
}
// ========== 스택 코드의 끝 ==========
int main() {
StackType s;
// 스택을 동적으로 생성한다.
// s = (StackType *)malloc(sizeof(StackType));
init_stack(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
// 동적 메모리는 반드시 반환한다.
// free(s);
return 0;
}
댓글