개념
LIFO (Last In First Out) 구조의 자료구조
가장 마지막에 들어온 데이터가 가장 먼저 나감 (후입선출)
시간복잡도
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| push | O(1) | 스택 맨 위에 데이터 추가 |
| pop | O(1) | 스택 맨 위의 데이터 제거 |
| peek/top | O(1) | 스택 맨 위의 데이터 조회 |
| isEmpty | O(1) | 스택이 비었는지 확인 |
특징
장점
- 단순하고 빠름: 모든 연산이
O(1) - 메모리 효율: 필요한 만큼만 사용
- 함수 호출 추적: 재귀 호출, 백트래킹에 유용
단점
- 제한된 접근: 맨 위 요소만 접근 가능
- 크기 제한: 배열 기반 구현 시 크기 제한 존재
활용 분야
- 함수 호출 스택 (Call Stack)
- 괄호 검사, 수식 계산
- 웹 브라우저 뒤로 가기
- 텍스트 에디터의 실행 취소(Undo)
Python 구현
1. 리스트로 구현 (가장 간단)
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
return None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# 사용 예시
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop()) # 3
print(stack.peek()) # 2
print(stack.size()) # 22. Python 내장 기능 활용
# 리스트를 스택으로 사용
stack = []
stack.append(1) # push
stack.append(2)
stack.append(3)
print(stack.pop()) # 3
print(stack[-1]) # peek → 2
# collections.deque 사용 (더 효율적)
from collections import deque
stack = deque()
stack.append(1) # push
stack.append(2)
stack.append(3)
print(stack.pop()) # 3
print(stack[-1]) # peek → 23. 연결 리스트로 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
self.count = 0
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node
self.count += 1
def pop(self):
if self.is_empty():
return None
data = self.top.data
self.top = self.top.next
self.count -= 1
return data
def peek(self):
if self.is_empty():
return None
return self.top.data
def is_empty(self):
return self.top is None
def size(self):
return self.count자주 나오는 문제 유형
1. 괄호 검사 (Valid Parentheses)
문제: 괄호가 올바르게 열리고 닫혔는지 확인
def is_valid_parentheses(s):
stack = []
pairs = {'(': ')', '{': '}', '[': ']'}
for char in s:
if char in pairs: # 여는 괄호
stack.append(char)
else: # 닫는 괄호
if not stack or pairs[stack.pop()] != char:
return False
return len(stack) == 0
# 테스트
print(is_valid_parentheses("()[]{}")) # True
print(is_valid_parentheses("([)]")) # False
print(is_valid_parentheses("{[()]}")) # True
# 시간복잡도: O(n)
# 공간복잡도: O(n)핵심: 여는 괄호는 push, 닫는 괄호는 pop하여 매칭 확인
2. 후위 표기법 계산 (Postfix Evaluation)
문제: 후위 표기법(Postfix)으로 작성된 수식 계산
def eval_postfix(expression):
stack = []
for token in expression.split():
if token in ['+', '-', '*', '/']:
# 연산자: 두 개의 피연산자를 pop
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
stack.append(a / b)
else:
# 숫자: push
stack.append(int(token))
return stack[0]
# 테스트
print(eval_postfix("2 3 + 4 *")) # (2 + 3) * 4 = 20
print(eval_postfix("5 1 2 + 4 * + 3 -")) # 5 + ((1 + 2) * 4) - 3 = 14
# 시간복잡도: O(n)
# 공간복잡도: O(n)핵심: 숫자는 push, 연산자를 만나면 두 개 pop하여 계산 후 push
3. 일일 온도 (Daily Temperatures)
문제: 각 날의 온도보다 더 따뜻한 날이 며칠 후인지 계산
def daily_temperatures(temperatures):
n = len(temperatures)
answer = [0] * n
stack = [] # (인덱스, 온도) 저장
for i, temp in enumerate(temperatures):
# 현재 온도가 스택의 온도보다 높으면
while stack and temperatures[stack[-1]] < temp:
prev_index = stack.pop()
answer[prev_index] = i - prev_index
stack.append(i)
return answer
# 테스트
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]
# 시간복잡도: O(n)
# 공간복잡도: O(n)핵심: 스택에 인덱스를 저장하고, 더 큰 값을 만나면 pop하여 차이 계산
4. 최소값을 반환하는 스택 (Min Stack)
문제: O(1) 시간에 최소값을 반환하는 스택 구현
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [] # 최소값 추적
def push(self, val):
self.stack.append(val)
# 최소값 갱신
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if self.stack:
val = self.stack.pop()
# 최소값이 pop되면 min_stack도 pop
if val == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1] if self.stack else None
def get_min(self):
return self.min_stack[-1] if self.min_stack else None
# 테스트
min_stack = MinStack()
min_stack.push(3)
min_stack.push(5)
print(min_stack.get_min()) # 3
min_stack.push(2)
print(min_stack.get_min()) # 2
min_stack.pop()
print(min_stack.get_min()) # 3핵심: 보조 스택을 사용하여 최소값을 추적
5. 스택으로 큐 구현 (Implement Queue using Stacks)
문제: 두 개의 스택으로 큐(FIFO) 구현
class QueueWithStacks:
def __init__(self):
self.stack_in = [] # 입력용 스택
self.stack_out = [] # 출력용 스택
def enqueue(self, x):
self.stack_in.append(x)
def dequeue(self):
# stack_out이 비어있으면 stack_in에서 옮김
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop() if self.stack_out else None
def peek(self):
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out[-1] if self.stack_out else None
# 테스트
q = QueueWithStacks()
q.enqueue(1)
q.enqueue(2)
print(q.dequeue()) # 1
print(q.peek()) # 2
# 시간복잡도: enqueue O(1), dequeue 평균 O(1)핵심: 입력 스택과 출력 스택을 분리하여 순서 역전
추천 연습 문제
기초
중급
- LeetCode 20 - Valid Parentheses
- LeetCode 155 - Min Stack
- LeetCode 739 - Daily Temperatures
- 백준 1874번 - 스택 수열
고급
핵심 요약
| 개념 | 설명 |
|---|---|
| 원리 | LIFO (Last In First Out) |
| 연산 | push, pop, peek 모두 O(1) |
| 구현 | 리스트 또는 연결 리스트 |
| 활용 | 괄호 검사, 후위 표기법, 백트래킹 |
스택 vs 큐
| 특성 | 스택 (Stack) | 큐 (Queue) |
|---|---|---|
| 구조 | LIFO (후입선출) | FIFO (선입선출) |
| 삽입 | push (맨 위) | enqueue (뒤) |
| 삭제 | pop (맨 위) | dequeue (앞) |
| 활용 | 함수 호출, 괄호 검사 | BFS, 작업 대기열 |
주의사항
1. 빈 스택 체크
# pop/peek 전에 체크
if stack:
value = stack.pop()2. Python 리스트 vs deque
# 리스트: 충분히 빠름
stack = []
stack.append(x) # O(1)
stack.pop() # O(1)
# deque: 양방향 필요시
from collections import deque
stack = deque()3. 스택 오버플로우
# 재귀 깊이 제한
import sys
sys.setrecursionlimit(10**6)