스택 (Stack)은 대표적인 후입선출 (Last In First Out, LIFO)의 자료구조로,
데이터 저장소에 새로 들어오는 데이터의 위치가 저장소의 끝이고, 내보내는 데이터 또한 저장소의 끝에서 나간다.
스택에 데이터를 집어 넣는 건 push, 데이터를 내보내는 건 pop이며 Top 위치에 있는 데이터를 확인하는 걸 peek라고 한다.
스택의 구조를 이미지로 표현하면 아래 이미지와 같다.
출처 : 위키백과 스택 문서 (https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D)
그러면 스택을 실제로 활용하기 위해 C 언어로 구현해보자.
#include <stdio.h>
#define STACK_SIZE 5
int top = -1;
int stack[STACK_SIZE];
// 스택 push
void push(int n)
{
stack[++top] = n;
}
int pop()
{
return stack[top--];
}
int peek()
{
return stack[top];
}
void printStack()
{
printf("[ ");
for (int i = top; i >= 0; i--)
{
printf("%d ", stack[i]);
}
printf("]\n");
}
int main()
{
push(1);
push(2);
push(3);
push(4);
push(5);
printStack();
printf("%d\n", peek());
printf("%d\n", pop());
printf("%d\n", peek());
printStack();
}
위에서 얘기한 push, pop, peek는 물론 스택의 전체 구조를 확인하기 위한 printStack 까지 작성했다.
이제 실행 결과를 통해 우리가 계획한 대로 작동하는지 확인해보자.
잘 작동하는 걸 볼 수 있다.
하지만 이 소스는 부족한 점이 있다.
바로 스택 오버플로우나 스택 언더플로 발생시 대응할 수 없다는 점이다.
스택 오버플로 (Stack Overflow) 란 스택이 넘친다는 뜻으로,
위 코드의 스택은 5개까지 넣을 수 있지만, 사용자가 5개 이상의 스택을 넣는 것을 방지하지 않는다.
스택에 값을 더 밀어 넣으면서 메모리에 있는 다른 값까지 건드릴 수 있기 때문에 심각한 문제다.
스택 언더플로의 경우 스택 오버플로와 반대로 스택에는 값이 없지만 peek를 요청해서 메모리에 있는 다른 값을 가져올 수 있다.
이제 위 코드에 스택 오버플로와 스택 언더플로를 방지하는 코드를 추가해보자.
#include <stdio.h>
#define STACK_SIZE 5
int top = -1;
int stack[STACK_SIZE];
// 스택 push
void push(int n)
{
if (top > STACK_SIZE)
{
printf("Stack Overflow!\n");
}
else
{
stack[++top] = n;
}
}
int pop()
{
if (top <= -1)
{
printf("Stack Underflow!\n");
return 0;
}
return stack[top--];
}
int peek()
{
if (top <= -1)
{
printf("Stack Underflow!\n");
return 0;
}
return stack[top];
}
void printStack()
{
printf("[ ");
for (int i = top; i >= 0; i--)
{
printf("%d ", stack[i]);
}
printf("]\n");
}
int main()
{
printf("%d\n", pop());
for (int i = top; i <= STACK_SIZE + 1; i++)
push(i);
}
스택 관련 함수에 스택 오버플로 및 스택 언더플로를 방지하는 코드를 넣어줬다.
이제 실제로 작동하는지 확인해보자.
제대로 작동하는 걸 볼 수 있다.
우리는 기본적인 기능을 하는 스택을 만들어봤다.
이 글을 통해 스택을 쉽게 이해할 수 있었으면 좋겠다.