스택

스택의 사전적 의미는 쌓아올림, 더미 등이다.

스택은 아주 중요한 자료구조이고 기본 동작에서부터 고급 알고리즘에 이르기까지 아주 많이 쓰이고 있다.

스택의 방식은 소주잔을 생각하면 된다. 단, 전제로 소주는 섞이지 않고 차례로 쌓인다고 가정한다.

우리가 소주를 소주잔에 따라서 가득 채웠다가 마실 때는 맨위에 찰랑거리는 소주부터 입으로 들어간다.

이것을 LIFO(Last In First Out)이라고 한다. 가장 먼저 따른 것은 가장 마지막에 우리의 입으로 들어가고, 가장 나중에 따른 것이 우리의 입에 맨처음 들어가게 된다. 물론 현실에서는 소주가 섞여서 어느게 먼저 일지 모르겠지만 말이다.

하지만 소주가 넘치면 곤란하다. 왜 피같은 술이지 않는가 ?
또 소주가 비워져 있는데 마시려고 하면 열 받지 않겠는가 ?

우리는 그것을 눈으로 확인할 수 있지만 프로그램은 우리가 프로그래밍 언어로 지시전달한 것만 실행하기에 우리가 지시를 해주어야 한다. 

그래서 top이라는 지시자에게 현재 술이 소주잔의 어느 위치에 있는지 항상 가리키도록 한다.

간단하게 배열로 스택을 구현해 보자

배열은 0 번지 부터 시작하므로 배열이 비어있을 때는 top은 (-1)의 값을 가져야 한다.

스택의 기본 동작은 스택 구조에 값을 넣는 push 와 스택 구조에서 값을 꺼내는 pop 이 있다.

#include <stdio.h> #define MAX 10 int stack[MAX]; int top; void init_stack(void) { top = (-1); } int is_empty(void) { return top == (-1); } int is_full(void) { return top == (MAX - 1); } int pop(void) { if (is_empty()) { printf("Stack underflow!!\n"); return (-1); } return stack[top--]; } int push(int value) { if (is_full()) { printf("Stack overflow!!\n"); return (-1); } stack[++top] = value; return 0; } void print_stack(void) { printf("\n------ Stack is going empty ------\n"); while (!is_empty()) printf("%-6d", pop()); }

위의 C 코드에서는 main 함수는 존재하지 않는다. main은 위의 함수들을 이용해서 스택 테스트를 만들어 보면 될 것이다.

또한 top-- 와 ++top 에 대해서 잘 구별해야 할 것이다. 이런 이유는 top 의 초기값을 (-1)로 규정했기 때문이다.

만약 top의 초기값을 0 로 규정하게 되면 top 은 언제나 앞으로 저장될 값이 들어갈 위치를 가리키게 된다.

(-1)과 0 은 개인 취향이다. 프로그래밍을 하는 사람 마음이라는 것이다.