💡 정의
스택은 한쪽으로만 데이터를 넣고 뺄 수 있는 형태의 데이터 구조로, 후입 선출(Last In First Out, LIFO)이라는 특성을 지니고 있다.
차곡차곡 쌓여 있는 형태의 데이터 구조라고 보면 된다.
🌱 ADT
스택은 그림과 같이 한쪽으로만 데이터를 넣고(push), 뺄(pop) 수 있다. 스택은 일반적으로 자료를 넣고 빼는 것뿐만 아니라 가장 위에 있는 자료를 확인(peek)하거나, 스택이 비어(isEmpty)있는지 확인할 수 있다.
스택에 필요한 기능들이 어느 정도 나열되었는데, 추상 자료형을 간략하게 코드로 표현해보자.
Stack<T> {
push(T);
pop();
peek();
isEmpty();
}어느 정도 정리되었으니 이를 C언어로 구현해보자.
👀 스택 살펴보기
스택을 구현할 수 있는 방법은 여러 가지가 있지만 이번 글에서는 배열(Array)을 활용하여 스택을 구현하려고 한다. 아래 예제 코드를 확인해보자.
#define STACK_SIZE 10
int top = -1;
int stack[STACK_SIZE];STACK_SIZE 라는 매크로를 정의했다.
스택의 크기를 10으로 정의할 것이기 때문에 10이라는 값으로 지정해주었다.
top 이라는 정수형 변수와 stack 이라는 이름의 배열이 선언되어있다. 용도는 아래와 같다.
- top: 스택 최상단 자료의 위치를 나타내는 변수
- stack: 자료를 저장할 배열 (스택 공간)
top 의 초기 값이 -1인 이유는 아직 스택이 비어있기 때문이다. 즉 -1은 비어있다(empty)라는 의미로 받아들이려고 한다. 먼저 기본적으로 데이터를 넣고, 뺄 수 있는 기능을 구현해보자.
void push(int);
int pop(void);
void push(int data)
{
// 배열 인덱스는 0부터 시작이므로, STACK_SIZE - 1
if (top >= STACK_SIZE - 1)
{
printf("꽉 찼다!");
return;
}
stack[++top] = data;
}
int pop(void)
{
if (isEmpty())
{
printf("텅 비어있네");
return 0;
}
return stack[top--];
}데이터를 넣고 뺄 때 스택이 가득 찼는지, 아니면 비어있는지 확인할 수 있도록 조건이 추가되어있다.
여기서 주의 깊게 봐야 할 부분은 top 변수 값의 변화이다.
push 함수에서는 선위 증가되고 있고, pop 에서는 후위 감소되고 있다.
자료를 넣기 위해선 미리 위치가 정해져 있어야 하고, 반대로 뺄 때에는 자료가 나온 후 최상위 위치가 다시 계산되어야 한다.
우리 일상에서 새로운 집으로 이사간다고 생각하면 이해하기 쉬울 것이다. (먼저 집을 구한 뒤 들어가고, 나올 때에는 정리 먼저 한 후 방을 뺀다)
자료를 넣고 빼는 기능을 구현했으니, 이번에는 나머지 두 기능(peek, isEmpty)을 구현해보자.
int peek(void):
int isEmpty(void);
int peek(void)
{
if (isEmpty())
{
printf("스택이 비어있어요");
return 0;
}
return stack[top];
}
int isEmpty(void)
{
return top == -1 ? 1 : 0;
}peek은 현재 스택 최상단에 어떤 값이 있는지 확인하는 기능을 제공한다. 스택이 비어있는지 확인하고, 비어있지 않을 경우 stack[top] 위치에 있는 값을 전달해주기만 하면 된다.
isEmpty는 스택이 비어있는지 확인하는 기능을 제공한다.
우리는 top 값이 -1 일 때 스택이 비어있다고 판단하기로 했으니 이에 맞게 조건을 추가했다.
-1인 경우 1(참)을 반환하고, -1이 아닌 경우 0(거짓)을 반환하도록 했다.
이렇게 스택의 기본 기능을 모두 구현해보았다.
스택에 담겨져있는 값을 확인할 수 있도록 아래와 같은 함수를 추가로 구현하고, 직접 스택을 사용해보며 동작하는 모습을 확인해보자.
void printStack(void);
// 스택 값 확인을 위한 함수
void printStack(void) {
if (isEmpty())
{
printf("[]\n");
return;
}
printf("[ ");
for (int i = 0; i < STACK_SIZE; i++)
{
if (i <= top)
{
printf("%d ", stack[i]);
}
else
{
printf("- ");
}
}
printf("]\n");
}
#include <stdio.h>
#define STACK_SIZE 10
int top = -1;
int stack[STACK_SIZE];
void push(int);
int pop(void);
int peek(void);
int isEmpty(void);
void printStack(void);
void push(int data)
{
// 배열 인덱스는 0부터 시작이므로, STACK_SIZE - 1
if (top >= STACK_SIZE - 1)
{
printf("꽉 찼다!");
return;
}
stack[++top] = data;
}
int pop(void)
{
if (isEmpty())
{
printf("텅 비어있네");
return 0;
}
return stack[top--];
}
int peek(void)
{
if (isEmpty())
{
printf("스택이 비어있어요");
return 0;
}
return stack[top];
}
int isEmpty(void)
{
return top == -1 ? 1 : 0;
}
// 스택 값 확인을 위한 함수
void printStack(void) {
if (isEmpty())
{
printf("[]\n");
return;
}
printf("[ ");
for (int i = 0; i < STACK_SIZE; i++)
{
if (i <= top)
{
printf("%d ", stack[i]);
}
else
{
printf("- ");
}
}
printf("]\n");
}
int main(void)
{
push(4);
push(-102);
push(23);
push(9);
push(10);
printStack();
int popValue = pop();
printf("pop: %d\n", popValue);
int peekValue = peek();
printf("peek: %d\n", peekValue);
pop();
pop();
printStack();
return 0;
}
/*
Result
[ 4 -102 23 9 10 - - - - - ]
pop: 10
peek: 9
[ 4 -102 - - - - - - - - ]
*/메인 함수를 살펴보면 스택에 4, -102, 23, 9, 10 값을 넣은 후 스택 값을 출력하니 차례대로 값이 스택에 들어가 있는 것을 볼 수 있다.
이후 값을 꺼낸 후 해당 값을 출력해보고 있다. 가장 마지막에 push 한 값은 10이기 때문에 해당 값이 먼저 꺼내졌다. (후입선출)
값이 꺼내진 상태에서 가장 위에 있는 값을 출력(peek)해보면 이전에 넣었던 값인 9를 확인할 수 있다.
마지막으로 값을 2개 더 스택에서 꺼낸 뒤 스택 내부를 보면 나머지 두 개의 값을 확인할 수 있다.
지금까지 스택에 대해 알아보았다.
스택 자료구조는 재귀 알고리즘에서 널리 사용하기도 하고, 몇몇 프로그래밍 언어의 동작을 살펴보면 콜 스택(Call stack)이라는 개념이 존재하기도 한다.
스택이라는 개념을 잘 숙지하도록 하자.