스택은 뭐야?

"스택은 후입 선출(LIFO) 형식의 자료구조이다." 정도의 개념은 다들 한 번씩 들어봤을 거라고 생각한다. 스택의 개념은 이렇게 한 줄로 설명할 수 있지만 스택은 프로그래밍 언어, 시스템 기능 등 많은 부분에서 활용되고 있다. 스택 활용 예시는 다음과 같다.

• 함수 호출 및 실행
• 웹페이지 또는 핸드폰의 뒤로 가기 기능
• 후위표기식을 사용한 수식 계산

스택을 구현하기 위해서는 원소를 저장하기 위한 data와 가장 최근에 입력되었던 원소의 인덱스 위치를 가리키는 top이 필요하다. 구조체로 표현하면 다음과 같다.

typedef int element;
typedef struct {
    element data[STACK_SIZE];
    int top;
} StackType;

위와 같은 구조를 가진 스택을 구현하기 위해서는 pop, push 등의 함수들을 구현해야한다. 스택의 추상 자료형은 다음과 같다.

item: 스택에 저장될 원소, size: 스택의 최대 크기, s: 스택 포인터

create(size)  : 최대 크기 size의 공백 스택을 생성한다.
is_full(s)    : 스택이 가득 찼는지 확인한다.
is_empty(s)   : 스택이 비어있는지 확인한다.
push(s, item) : 스택에 item을 저장한다.
pop(s)        : 스택의 맨 위 원소를 제거하여 반환한다.
peek(s)       : 스택의 맨 위 원소를 제거하지 않고 반환한다.

대부분의 프로그래밍 언어들은 stack 기능을 제공해주기 때문에 함수명이 다르게 작성될 수는 있지만 기능은 동일하게 제공해준다.

 

간단하게 스택의 push와 pop 예제를 확인해보겠다.

스택 예제

위의 자료에서 다음 2가지 조건을 가정하겠다.

• size 2 이상의 스택이 생성되어있다.
• 화살표는 현재 top이 가르키고 있는 값이다.

예제에서 배열을 세로로 그렸지만 가로로 생각해도 동일하게 작동한다. 4가지 단계에 따른 스택의 반환 값과 top이 변하는 과정을 알아보겠다.

1. 공백 스택에 원소 A를 넣어 저장한다. top = 0
2. 스택에 원소 B를 넣어 저장한다. top = 1
3. 스택의 맨 위 원소를 제저하여 반환한다. top = 0, return = 원소 B
4. 스택에 원소 C를 넣어 저장한다. top = 1

이렇게 스택의 구조, 추상 자료형, 예제까지 알아보았다. 스택은 자료구조를 학습하게 될 때 처음 접하는 개념인 만큼 이해하기 어렵지는 않다.

 

스택은 이미 활용되고 있는 분야가 많고, 코딩 테스트에서도 스택을 활용한 쉬운 문제부터 어려운 문제까지 어렵지 않게 찾아볼 수 있다.