스택(Stack)

 

💡 정의

스택은 한쪽으로만 데이터를 넣고 뺄 수 있는 형태의 데이터 구조로, 후입 선출(Last In First Out, LIFO)이라는 특성을 지니고 있다.

차곡차곡 쌓여 있는 형태의 데이터 구조라고 보면 된다.

🌱 ADT

스택(Stack)

스택은 그림과 같이 한쪽으로만 데이터를 넣고(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)이라는 개념이 존재하기도 한다.

 

스택이라는 개념을 잘 숙지하도록 하자.