스택(Stack)은 가장 최근에 삽입한 원소가 가장 먼저 나오는 LIFO(Last In First Out) 구조의 자료구조다. 데이터를 쌓아 올리는 접시 더미처럼, 꺼낼 때는 맨 위부터 꺼낸다.
코딩테스트에서 스택이 등장하는 패턴은 대부분 "가장 최근에 넣은 원소"를 즉시 참조하거나 제거해야 하는 상황이다. 괄호 검증, 단조 스택(Monotone Stack), 함수 콜스택 시뮬레이션 등이 대표적이다.
| 구조 | 설명 | 대표 자료구조 |
|---|---|---|
| LIFO | 마지막에 넣은 원소가 먼저 나옴 | Stack |
| FIFO | 먼저 넣은 원소가 먼저 나옴 | Queue |
스택은 이론 속 개념이 아니라 우리가 매일 쓰는 기능에 이미 녹아 있다. 두 가지 대표 예시를 코드와 함께 살펴보자.
예시 1 — 웹 브라우저 뒤로 가기
방문한 페이지를 스택에 순서대로 push하고,
뒤로 가기를 누르면 pop하여 직전 페이지로 돌아간다.
LIFO 구조이므로 가장 최근에 방문한 페이지가 자연스럽게 제거된다.
// 방문한 페이지를 스택에 저장하고, 뒤로 가기 시 최근 페이지를 제거 #include <iostream> #include <stack> #include <string> using namespace std; int main() { stack<string> history; history.push("A"); history.push("B"); history.push("C"); cout << "현재 페이지: " << history.top() << endl; // C history.pop(); // C → B cout << "뒤로 가기 후 현재 페이지: " << history.top() << endl; // B return 0; } /* 출력결과 현재 페이지: C 뒤로 가기 후 현재 페이지: B */
예시 2 — 함수 호출 스택
C++ 프로그램이 실행될 때 함수 호출은 내부적으로 콜 스택(Call Stack)으로 관리된다.
main이 A를 호출하고, A가 B를 호출하면
스택에 순서대로 쌓인다. B가 종료되면 LIFO 구조에 따라 A로 자연스럽게 복귀한다.
main 함수에서 A 함수 호출 → 스택에 main, A 순으로 적재
A 함수에서 B 함수 호출 → 스택에 main, A, B 순으로 적재
B 함수 종료 → B가 pop되고 자신을 호출한 A로 반환
#include <iostream> using namespace std; void B() { cout << "B 함수 호출됨" << endl; cout << "B 함수 종료됨" << endl; } void A() { cout << "A 함수 호출됨" << endl; B(); cout << "A 함수 종료됨" << endl; } int main() { cout << "main 함수 호출됨" << endl; A(); cout << "main 함수 종료됨" << endl; return 0; } /* 출력결과 main 함수 호출됨 → A 함수 호출됨 → B 함수 호출됨 → B 함수 종료됨 → A 함수 종료됨 → main 함수 종료됨 */
ADT(Abstract Data Type, 추상 자료형)란 자료구조의 동작을 구체적인 구현과 분리하여 인터페이스 수준에서 정의한 설계도다. 실제로 배열로 구현하든 연결 리스트로 구현하든 외부에서는 동일하게 사용할 수 있다.
| 구분 | 정의 | 설명 |
|---|---|---|
| 연산 | boolean isFull() |
데이터 개수가 maxsize와 같으면 true, 아니면 false 반환 |
| 연산 | boolean isEmpty() |
데이터가 하나도 없으면 true, 있으면 false 반환 |
| 연산 | void push(ItemType item) |
스택 top에 데이터를 추가 |
| 연산 | ItemType pop() |
가장 최근에 추가된 데이터를 제거하고 반환 |
| 상태 | int top |
가장 최근에 추가된 데이터의 위치 인덱스 |
| 상태 | ItemType data[maxsize] |
스택의 데이터를 관리하는 배열, 최대 maxsize개 저장 |
ADT를 기준으로 push와 pop이 내부에서 어떻게 수행되는지 단계별로 확인한다.
push(3) 수행 과정
isFull()을 호출하여 스택이 가득 찼는지 확인
top을 1 증가 (-1 → 0)
data[top]에 해당하는 위치에 값 3을 저장
pop() 수행 과정
isEmpty()를 호출하여 빈 스택인지 확인
top을 1 감소 (0 → -1)
top은 실제로 데이터를 지우지 않는다.
인덱스를 감소시켜 논리적으로 비어있는 것으로 간주할 뿐이며,
다음 push가 그 자리를 덮어쓴다.
C++은 <stack> 헤더를 통해 스택을 기본 제공하므로 직접 구현할 필요가 없다.
주요 메서드와 시간 복잡도를 정리하면 아래와 같다.
| 메서드 | 동작 | 예시 | 시간 복잡도 |
|---|---|---|---|
top() |
top 요소 접근 (제거 안 함) | s.top() |
O(1) |
push(val) |
top에 요소 삽입 | s.push(10) |
O(1) |
pop() |
top 요소 제거 (반환값 없음) | s.pop() |
O(1) |
empty() |
스택이 비어 있는지 확인 | s.empty() |
O(1) |
size() |
스택 내 요소 개수 반환 | s.size() |
O(1) |
push_range(first, last) |
반복자 범위의 요소를 일괄 삽입 | s.push_range(v.begin(), v.end()) |
O(N) |
값을 꺼내야 한다면 반드시
top()으로 먼저 읽은 뒤 pop()을 호출해야 한다.
int x = s.pop();은 컴파일 에러가 발생한다.
#include <iostream> #include <stack> using namespace std; int main() { stack<int> s; s.push(10); s.push(20); s.push(30); cout << "스택의 top: " << s.top() << endl; // 30 s.pop(); cout << "pop 후 top: " << s.top() << endl; // 20 cout << "비어있나? " << (s.empty() ? "예" : "아니오") << endl; cout << "크기: " << s.size() << endl; // 2 // 올바른 값 추출 패턴 int val = s.top(); // 먼저 읽고 s.pop(); // 그 다음 제거 // int x = s.pop(); // ❌ 컴파일 에러 — pop()은 반환값 없음 return 0; }
문제 9 — 10진수를 2진수로 변환하기
정수 decimal을 2진수 문자열로 반환한다.
2로 나눈 나머지를 스택에 쌓은 뒤, 스택에서 순서대로 꺼내면 LIFO 특성에 의해
자연스럽게 올바른 2진수 순서(MSB → LSB)가 완성된다.
| decimal | result |
|---|---|
| 10 | "1010" |
| 27 | "11011" |
| 12345 | "11000000111001" |
#include <stack> #include <string> using namespace std; string solution(int decimal) { if (decimal == 0) return "0"; stack<int> st; while (decimal > 0) { st.push(decimal % 2); // 나머지를 스택에 쌓음 decimal /= 2; } string binary = ""; while (!st.empty()) { binary += to_string(st.top()); // LIFO → MSB부터 꺼내짐 st.pop(); } return binary; }
문제 12 — 주식 가격 (프로그래머스)
초 단위로 기록된 주식 가격 배열 prices가 주어질 때,
각 시점에서 가격이 떨어지지 않은 기간(초)을 반환한다.
스택에 인덱스를 저장하고 현재 가격이 이전 가격보다 낮을 때 pop하여 기간을 계산한다.
스택에 저장된 인덱스의 가격이 항상 현재 가격 이하를 유지하도록 관리한다. 현재 가격이 더 낮으면 스택을 pop하면서 그 시점의 지속 기간을
i - s.top()으로 계산한다.
순회 후 스택에 남은 인덱스는 끝까지 가격이 떨어지지 않은 경우다.
#include <vector> #include <stack> using namespace std; vector<int> solution(vector<int> prices) { vector<int> answer(prices.size()); stack<int> s; int n = prices.size(); for (int i = 0; i < n; i++) { while (!s.empty() && prices[s.top()] > prices[i]) { // 가격이 떨어진 시점 → 기간 계산 후 pop answer[s.top()] = i - s.top(); s.pop(); } s.push(i); } // 끝까지 가격이 떨어지지 않은 인덱스 처리 while (!s.empty()) { answer[s.top()] = n - s.top() - 1; s.pop(); } return answer; } // solution({1,2,3,2,3}) → {4,3,1,1,0}
문제 13 — 크레인 인형 뽑기 게임 (프로그래머스)
N×N 격자 보드에서 크레인이 지정된 열 순서(moves)로 인형을 뽑는다.
뽑은 인형을 바구니 스택에 쌓을 때, 스택 top과 같은 인형이 오면 두 인형이 제거된다.
최종적으로 사라진 인형의 총 개수를 반환한다.
#include <stack> #include <vector> using namespace std; int solution(vector<vector<int>> board, vector<int> moves) { // 각 열을 스택으로 모델링 (아래→위 순서로 push) stack<int> lanes[board[0].size()]; for (int i = board.size()-1; i >= 0; --i) for (int j = 0; j < board[0].size(); ++j) if (board[i][j]) lanes[j].push(board[i][j]); stack<int> bucket; int answer = 0; for (int m : moves) { if (lanes[m-1].size()) { int doll = lanes[m-1].top(); lanes[m-1].pop(); // 바구니 top과 같으면 둘 다 제거 (+2점) if (bucket.size() && bucket.top() == doll) { bucket.pop(); answer += 2; } else { bucket.push(doll); } } } return answer; }
| 새로 배운 것 |
스택의 LIFO 원리가 웹 브라우저 뒤로 가기, 함수 콜 스택 등 실생활과 직결되어 있다는 것을 코드로 직접 확인했다.
ADT 개념을 통해 push/pop 내부에서 top 인덱스가 어떻게 움직이는지 구체적으로 이해했다.
STL stack에서 pop()이 반환값이 없으므로 반드시 top()을 먼저 써야 한다는 점도 새롭게 정리됐다.
|
| 어려웠던 점 | 주식 가격 문제에서 단조 스택 패턴을 처음 접했을 때, 스택에 값이 아닌 인덱스를 저장한다는 발상이 직관적이지 않았다. 크레인 인형 뽑기 역시 보드를 열 단위 스택으로 모델링하는 아이디어를 떠올리는 데 시간이 걸렸다. |
| 기억할 핵심 |
"가장 최근 원소"가 키워드라면 스택을 의심하라. 값 대신 인덱스를 스택에 저장하면 구간 계산이 훨씬 쉬워진다.
top() → pop() 순서는 반드시 지킨다.
|
| 다음 목표 |
큐(Queue) 자료구조와 STL <queue> 활용법을 학습하고, 스택과 큐를 함께 사용하는 문제 유형까지 연습한다.
|