[자료구조] 스택(Stack) 완벽 정리: 작동 원리와 코딩 테스트 활용 전략

1. 🔍 스택 개념

stack의 어원은 쌓는다이다. 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다. 먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 또는 LIFO(Last In First Out)라고 한다. 이때 스택에 삽입하는 연산을 push, 꺼내는 연산을 pop이라고 한다.

💯 스택의 특징

• 후입선출 또는 LIFO(Last In First Out): 마지막에 입력한 데이터가 먼저 나오는 자료구조
• 스택의 push(), pop(), top(), empty() 연산 모두 시간 복잡도가 $O(1)$이다.

📝 스택의 ADT

ADT(Abstract Data Type)는 추상 자료형이며, 추상 자료형이란 인터페이스만 있고 실제로 구현되지 않은 자료형이다. 일종의 자료형의 설계도라고 생각하면 된다.

• 스택에는 push, pop, isFull, isEmpty 연산을 정의해야 한다.
• 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 top도 있어야 한다.
• 스택의 원소는 배열이 아니라 다른 자료구조로 관리할 수도 있다.

구분	정의	설명
연산	boolean isFull()	스택에 들어 있는 데이터의 개수가 maxsize인지 확인해 boolean 값을 반환한다. 가득 차 있다면 True, 아니면 False이다.
연산	boolean isEmpty()	스택에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환한다. 데이터가 하나라도 있으면 False, 아니면 True이다.
연산	void push(ItemType item)	스택에 데이터를 푸시한다.
연산	ItemType pop()	스택에서 최근에 푸시한 데이터를 팝하고, 그 데이터를 반환한다.
상태	Int top	스택에서 최근에 푸시한 데이터의 위치를 기록한다.
상태	ItemType data[maxsize]	스택의 데이터를 관리하는 배열이다. 최대 maxsize개의 데이터를 관리한다.

• 그림에서는 연산 시 해야 할 동작(operation)과 상태(status)를 정의하고 있지만 세부 구현 내용, 즉, 프로그래밍 언어는 무엇을 사용해야 하고 데이터는 이렇게 저장해야 한다는 등의 내용은 없다.
• data 배열을 보면 최대 크기는 maxsize이므로 인덱스의 범위는 0부터 maxsize - 1이다.
• top은 가장 최근에 추가한 데이터의 위치를 참조한다.
• 지금 그림에서는 아무 데이터도 없으므로 top에 -1이 들어 있다.
• 만약 top이 0이면 데이터가 1개 있는 것이므로 초기값을 0이 아니라 -1로 했음에 주의하자.

스택의 세부 구현을 이해하는 것은 코딩 테스트와 면접 모두에서 매우 중요하다.
실제 문제에서는 “스택으로 풀어라”와 같이 명확하게 지시하지 않기 때문에, 문제를 보고 “이건 스택으로 풀면 되겠다!”라는 직관이 떠오르려면 스택의 동작 원리와 내부 구조를 충분히 이해하고 있어야 한다.

자료구조의 세부 동작을 깊이 있게 공부하면, 해당 자료구조의 성능과 특성을 정확히 파악할 수 있다.
이는 효율적인 알고리즘을 설계하는 데 큰 도움이 되며, 실제로 자료구조의 원리와 구현을 묻는 문제가 코딩 테스트와 면접에서 자주 출제된다.

2. 🎨 스택에서 데이터가 이동하는 과정 살펴보기

🧠 스택의 세부 동작 과정 예시

스택에 데이터를 추가하는 경우를 생각해보자.

1단계 push(3)

1. isFull() 연산으로 현재 스택이 가득 찼는지 확인한다.
2. top을 +1한다.
3. top이 가리키는 위치에 3을 push한다.

2단계 pop

1. isEmpty() 연산으로 현재 스택이 비어있는지 확인한다.
2. top을 -1한다.
3. top이 가리키는 위치에 있는 데이터를 반환한다.
   • 여기서 중요한 점은 data[0] 위치에 있던 3을 지우지 않았다는 점이다.
   • 앞서 정의한 스택의 ADT에서 top은 최근에 삽입한 데이터의 위치라 하였고 top이 가리키는 위치가 -1이므로 실제 data 배열에 데이터가 남아 있더라도 스택은 비어 있다고 보아도 된다.
   • 또한 언어마다 세부적 구현이 달라 pop() 연산을 수행하여 3을 반환하지 않고 그냥 top을 1만큼 감소만 시키는 구현이 될 수도 있으므로 언어별 세부 구현을 확인해야 한다.(C++은 pop() 연산을 해도 값을 반환하지는 않는다.)

3. 📦 스택 사용하기

코딩 테스트에서는 문제에 적용할 자료구조 혹은 알고리즘을 파악하는 능력이 중요하다. 문제에서 의도한 데이터 흐름이 스택에 딱 맞는지 알아차리는 것이 중요하다. 예를 들어 데이터를 그냥 저장하고 순서와 상관없이 임의 접근하기만 해도 되면 배열을 사용하면 되지만 최근에 삽입한 데이터를 대상으로 뭔가 연산해야 한다면 스택을 떠올리는 것이 좋다.

⚡ C++

STL에서 스택을 제공한다. #include <stack>

• stack에 대해 자세히 공부하고 싶다면 [C++ STL] stack 완벽 정리: 기본부터 심화까지 (면접 대비)을 참고하자.

#include <stack>

stack<int> s;

⚡ Python

Python의 경우 표준 라이브러리에 스택 전용 모듈이 없지만 여러 모듈에서 스택처럼 사용 가능한 클래스가 있다.

stack = []

# push
stack.append(1)
stack.append(2)
stack.append(3)

Algorithm Theory 카테고리 내 다른 글 보러가기