스택이란
스택은 LIFO(Last In, First Out) 원칙으로 동작하는 자료구조다. 마지막에 넣은 것이 가장 먼저 나온다.
실생활 비유로는 접시 쌓기가 대표적인 비유다. 접시를 위에 쌓고, 꺼낼 때도 맨 위에서부터 꺼낸다. 브라우저의 뒤로가기도 같은 원리다. 방문한 페이지를 스택에 쌓고, 뒤로가기를 누르면 가장 최근 페이지부터 꺼낸다.
push → [ ] → [A] → [A, B] → [A, B, C]
pop ← ← [A, B] ← top: C프로그래밍에서 스택이 가장 핵심적으로 쓰이는 곳은 콜 스택이다. 함수를 호출하면 해당 함수의 실행 정보(지역 변수, 반환 주소 등)가 스택 프레임으로 쌓인다. 함수가 반환하면 해당 프레임이 꺼지고, 이전 함수가 이어서 실행된다. 재귀 호출을 반복하면 스택 프레임이 계속 쌓이다가 한도를 초과하면 스택 오버플로가 발생한다. Python의 기본 재귀 한도는 sys.getrecursionlimit()으로 확인할 수 있고, 기본값은 1000이다.
import sys
print(sys.getrecursionlimit())Python에서 스택 구현하기
리스트(list)로 구현
Python의 list는 스택으로 바로 사용할 수 있다. append()로 넣고, pop()으로 꺼낸다.
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
top = stack.pop()
print(top)
print(stack)출력:
3
[1, 2]pop()은 인덱스를 지정하지 않으면 마지막 요소를 꺼낸다. 리스트의 끝에서 삽입/삭제하는 연산은 O(1)이라 스택 용도로 충분하다.
collections.deque로 구현
코딩 테스트에서는 collections.deque를 사용하는 것이 더 안전하다.
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
top = stack.pop()
print(top)
print(stack)리스트도 pop()은 O(1)이라 스택 용도에서 성능 차이는 거의 없다. 그런데 나중에 큐로 확장할 때 popleft()를 바로 사용할 수 있어서, 처음부터 deque를 사용하는 습관을 들이는 편이 낫다.
성능 차이의 근거는 내부 구현에 있다. list는 동적 배열로 구현되어 있어서 끝에서의 삽입·삭제는 O(1)이지만, 앞에서의 삽입·삭제는 나머지 요소를 전부 이동시켜야 해서 O(n)이다. deque는 이중 연결 리스트 기반으로 양쪽 끝 모두 O(1)을 보장한다. 스택 용도에서는 끝만 사용하므로 둘 사이에 성능 차이가 없다. 그러나 큐로 확장해 앞에서 꺼내야 할 때 deque를 쓰면 popleft()로 O(1)이 되고, list를 쓰면 pop(0)으로 O(n)이 된다.
클래스로 직접 구현 (연결 리스트 기반)
면접이나 구현 문제에서는 연결 리스트 기반 스택을 직접 만들어야 할 수 있다.
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
def __init__(self):
self.top = None
self.size = 0
def push(self, value):
new_node = Node(value)
new_node.next = self.top
self.top = new_node
self.size += 1
def pop(self):
if self.is_empty():
raise IndexError("스택이 비어 있습니다")
popped = self.top.value
self.top = self.top.next
self.size -= 1
return popped
def peek(self):
if self.is_empty():
raise IndexError("스택이 비어 있습니다")
return self.top.value
def is_empty(self):
return self.top is None새 노드를 추가할 때 기존 top을 new_node.next에 연결하고 top을 새 노드로 교체한다. 꺼낼 때는 반대로 top을 다음 노드로 옮긴다.
스택의 주요 연산과 시간 복잡도
| 연산 | 설명 | 시간 복잡도 |
|---|---|---|
| push | 맨 위에 삽입 | O(1) |
| pop | 맨 위 제거 및 반환 | O(1) |
| peek | 맨 위 조회 (제거 안 함) | O(1) |
| is_empty | 비어 있는지 확인 | O(1) |
| 탐색 | 특정 값 찾기 | O(n) |
스택의 삽입과 삭제는 항상 맨 위에서만 일어나기 때문에 O(1)이다. 특정 값을 찾으려면 스택 전체를 순회해야 하므로 O(n)이 된다.
스택 활용 패턴
괄호 검증
열린 괄호가 나오면 스택에 쌓고, 닫힌 괄호가 나오면 스택에서 꺼내 매칭하는 패턴이다.
괄호 문제에서 스택이 적합한 이유는 괄호의 구조 자체에 있다. 가장 최근에 열린 괄호가 가장 먼저 닫혀야 한다. ([가 순서대로 나왔다면, 다음에 닫히는 것은 반드시 ]여야 한다. "마지막에 열린 것이 가장 먼저 닫혀야 한다"는 성질이 LIFO와 정확히 일치한다.
스택 없이 이 문제를 풀려 하면 중첩된 괄호를 추적할 방법이 없다. ([{처럼 여러 종류의 괄호가 겹쳤을 때, 어떤 순서로 닫혀야 하는지를 기억할 구조 없이는 올바르게 검증하지 못한다.
코드에서 matching 딕셔너리는 닫힌 괄호를 키로, 대응하는 열린 괄호를 값으로 저장한다. ')': '('는 "닫힌 괄호 )가 나왔을 때 스택 맨 위에 (가 있어야 한다"는 매칭 규칙이다.
입력 "([)]"이 False가 되는 과정을 한 단계씩 따라가면 다음과 같다.
'(' → 열린 괄호, 스택에 추가 스택: ['(']
'[' → 열린 괄호, 스택에 추가 스택: ['(', '[']
')' → 닫힌 괄호, matching[')'] = '(' 스택 맨 위: '[' → 일치하지 않음 → False 반환[가 닫히기 전에 )가 나왔기 때문에 잘못된 괄호 순서로 판정한다.
def is_valid_parentheses(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in '({[':
stack.append(char)
elif char in ')}]':
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
return len(stack) == 0print(is_valid_parentheses("()[]{}"))
print(is_valid_parentheses("([)]"))
print(is_valid_parentheses("{[]}"))출력:
True
False
True문자열을 순회하면서 닫힌 괄호가 나왔을 때 스택이 비어 있거나 가장 위 요소가 짝이 맞지 않으면 바로 False를 반환한다. 끝까지 순회했을 때 스택이 비어 있어야 모든 괄호가 쌍을 이룬 것이다.
후위 표기식 변환 (중위 → 후위)
사람이 읽는 3 + 4 * 2 같은 중위 표기식을 컴퓨터가 계산하기 편한 3 4 2 * + 형태의 후위 표기식으로 변환할 때 스택을 사용한다.
중위 표기식은 연산자가 피연산자 사이에 위치하는 방식이다. 사람이 수식을 쓸 때 사용하지만, 괄호와 연산자 우선순위를 고려해야 한다. 후위 표기식은 연산자가 피연산자 뒤에 오는 방식이다.
컴퓨터는 후위 표기식이 편하다. 왼쪽부터 순서대로 읽다가 연산자가 나오면 바로 앞의 두 숫자에 적용하면 된다. 연산자 우선순위를 별도로 판단하지 않아도 된다.
스택이 필요한 이유는 연산자 우선순위 처리 때문이다. 3 + 4 * 2를 처리할 때, +를 만나자마자 출력하면 안 된다. *가 +보다 먼저 계산되어야 하기 때문이다. 우선순위가 낮은 연산자는 스택에 보류해두고, 우선순위가 더 높은 연산자가 처리된 다음에 꺼낸다. "나중에 들어온 높은 우선순위 연산자를 먼저 꺼내는" 이 동작이 LIFO다.
3 + 4 * 2를 변환하는 과정을 한 단계씩 따라가면 다음과 같다.
3 → 숫자, 결과에 추가 결과: ['3'] 스택: []
+ → 스택 비어 있음, 스택에 추가 결과: ['3'] 스택: ['+']
4 → 숫자, 결과에 추가 결과: ['3', '4'] 스택: ['+']
* → 스택 맨 위 '+'보다 우선순위 높음, 스택에 추가 결과: ['3', '4'] 스택: ['+', '*']
2 → 숫자, 결과에 추가 결과: ['3', '4', '2'] 스택: ['+', '*']
끝 → 스택 전부 꺼내기 결과: ['3', '4', '2', '*', '+']3 4 2 * +를 계산하면 4 * 2 = 8을 먼저 처리하고, 이어서 3 + 8 = 11이 나온다.
def infix_to_postfix(expression):
priority = {'+': 1, '-': 1, '*': 2, '/': 2}
stack = []
result = []
for token in expression.split():
if token.lstrip('-').isdigit():
result.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
result.append(stack.pop())
stack.pop()
else:
while stack and stack[-1] != '(' and priority.get(stack[-1], 0) >= priority[token]:
result.append(stack.pop())
stack.append(token)
while stack:
result.append(stack.pop())
return ' '.join(result)연산자가 나오면 스택 안에 우선순위가 같거나 높은 연산자가 있는 동안 꺼내서 결과에 추가하고, 그다음 현재 연산자를 스택에 넣는다.
단조 스택 (Monotone Stack)
단조 스택은 스택 안의 원소가 항상 오름차순 또는 내림차순을 유지하는 스택이다. 배열에서 각 원소에 대해 "다음으로 큰 원소"나 "이전으로 작은 원소" 같은 정보를 O(n)에 구할 때 사용한다.
"다음으로 큰 원소" 문제는 배열의 각 위치에서 오른쪽으로 처음 만나는 더 큰 값을 구하는 것이다. [2, 1, 5, 3, 6]에서 2의 다음으로 큰 원소는 5이고, 6은 오른쪽에 더 큰 원소가 없어서 -1이 된다.
이중 for문으로 풀면 각 원소마다 오른쪽을 전부 순회해야 한다. n개의 원소에 대해 n번씩 확인하므로 O(n^2)이다. n이 10만이면 100억 번 연산이 필요하다.
단조 스택은 이 문제를 O(n)에 해결한다. "아직 답을 찾지 못한 원소의 인덱스"를 스택에 보관하다가, 더 큰 값이 나타나면 해당 인덱스를 꺼내며 답을 기록한다. 각 원소는 스택에 정확히 한 번 들어가고 한 번 나오므로 전체 연산 횟수는 O(n)이다.
[2, 1, 5, 3, 6]으로 스택 상태 변화를 한 단계씩 따라가면 다음과 같다.
i=0, num=2 → 스택: [0] result: [-1, -1, -1, -1, -1]
i=1, num=1 → 1 < nums[0]=2, 스택: [0, 1] result: [-1, -1, -1, -1, -1]
i=2, num=5 → 5 > nums[1]=1, pop(1) → result[1]=5, 스택: [0]
→ 5 > nums[0]=2, pop(0) → result[0]=5, 스택: []
→ 스택: [2] result: [5, 5, -1, -1, -1]
i=3, num=3 → 3 < nums[2]=5, 스택: [2, 3] result: [5, 5, -1, -1, -1]
i=4, num=6 → 6 > nums[3]=3, pop(3) → result[3]=6, 스택: [2]
→ 6 > nums[2]=5, pop(2) → result[2]=6, 스택: []
→ 스택: [4] result: [5, 5, 6, 6, -1]
끝 → 스택에 남은 인덱스 4는 오른쪽에 더 큰 원소가 없으므로 그대로 -1def next_greater_element(nums):
result = [-1] * len(nums)
stack = []
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
idx = stack.pop()
result[idx] = num
stack.append(i)
return resultprint(next_greater_element([2, 1, 5, 3, 6]))출력:
[5, 5, 6, 6, -1]스택에 인덱스를 넣고, 새 원소가 스택 맨 위 인덱스의 값보다 크면 해당 인덱스의 "다음으로 큰 원소"를 찾은 것이다. 쇠막대기(백준 10799) 같은 문제가 이 패턴의 응용이다.
DFS (깊이 우선 탐색)
DFS는 스택의 대표적인 활용이다. 재귀로 구현하는 것이 직관적이지만, 재귀 깊이가 깊어지면 콜 스택 한도를 초과할 수 있다. 명시적 스택을 사용하면 재귀 없이 동일한 탐색을 수행할 수 있다.
그래프는 노드(정점)와 간선으로 이루어진 구조다. 그래프 탐색은 시작 노드에서 출발해 연결된 모든 노드를 방문하는 것이다.
DFS는 미로 탐색에 비유할 수 있다. 갈림길에서 한 방향을 선택해 막힐 때까지 직진한다. 막히면 가장 최근의 갈림길로 돌아와서 아직 시도하지 않은 다른 방향을 선택한다. "가장 최근 갈림길로 돌아가기"가 LIFO 동작이다.
재귀 DFS와 명시적 스택 DFS가 동일한 이유는 재귀 호출 자체가 콜 스택을 사용하기 때문이다. 함수를 호출하면 현재 상태가 콜 스택에 쌓이고, 함수가 반환되면 꺼진다. 명시적 스택 DFS는 이 과정을 프로그래머가 직접 제어하는 방식이다.
def dfs_iterative(graph, start):
visited = set()
stack = [start]
order = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return order재귀 DFS는 함수 호출 자체가 내부적으로 콜 스택을 사용한다. 명시적 스택 DFS는 같은 원리를 프로그래머가 직접 제어하는 방식으로, 입력 크기가 커서 재귀 한도(기본 1000)를 초과할 위험이 있을 때 사용한다. 큐 파일의 BFS가 FIFO로 층위별 탐색을 보장하듯, DFS는 스택의 LIFO로 깊이 방향 탐색을 수행한다.
연습 문제
초급
| 번호 | 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|---|
| 10828 | 스택 | 브론즈 2 | https://www.acmicpc.net/problem/10828 | 명령어 파싱 후 리스트로 스택 구현 |
| 9012 | 괄호 | 실버 4 | https://www.acmicpc.net/problem/9012 | (는 push, )는 pop 후 매칭 확인 |
| 1874 | 스택 수열 | 실버 2 | https://www.acmicpc.net/problem/1874 | 1부터 n까지 순서대로 push, 목표 수열과 비교하며 pop |
중급
| 번호 | 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|---|
| 10799 | 쇠막대기 | 실버 1 | https://www.acmicpc.net/problem/10799 | 레이저(())를 만나면 현재 스택 크기만큼 조각 추가 |
| 2504 | 괄호의 값 | 골드 5 | https://www.acmicpc.net/problem/2504 | 닫힐 때 괄호 종류에 따라 곱하거나 합산 |
| 1918 | 후위 표기식 | 골드 2 | https://www.acmicpc.net/problem/1918 | 연산자 우선순위 기반 스택 관리로 중위→후위 변환 |
'CodingTest > 자료구조-알고리즘' 카테고리의 다른 글
| [DFS & BFS] (0) | 2026.03.31 |
|---|---|
| [재귀 & 완전 탐색] & [백트래킹] (0) | 2026.03.24 |
| 해시 (Hash) (1) | 2026.03.17 |
| 큐 (Queue) (1) | 2026.03.17 |
| 연결 리스트 (Linked List) (0) | 2026.03.16 |