1. 스택이 없으면 불편한 점
편집기의 되돌리기 기능을 생각해 보면, 되돌릴 대상은 항상 가장 최근에 한 작업입니다. 수식의 괄호 짝을 맞출 때도 닫는 괄호는 가장 최근에 열린 괄호와 짝을 이룹니다.
이런 일을 리스트로 처리하면 "지금 가장 최근 원소가 몇 번 인덱스인지"를 직접 관리해야 하고, 실수로 중간 원소를 건드릴 여지도 생깁니다. 처리 순서가 "나중에 들어온 것 먼저"로 정해져 있다면, 아예 그 순서로만 넣고 뺄 수 있게 막아 두는 편이 안전합니다.
2. 정의와 연산
스택은 한쪽 끝(top)에서만 삽입과 삭제가 일어나는 자료구조입니다. 나중에 넣은 것을 먼저 꺼내므로 LIFO(Last In First Out)라고 합니다.
삽입 연산은 push, 삭제 연산은 pop입니다.
실제로 쓰려면 보조 연산 몇 개가 더 필요합니다. 맨 위 원소를 꺼내지 않고 확인하는 top, 비었는지 확인하는 is_empty, 원소 개수를 반환하는 len입니다.
3. 동작
before: push(9)
| |
+-----+
top -> | 5 |
+-----+
| 3 |
+-----+after
top -> | 9 | <- 새로 올라감
+-----+
| 5 |
+-----+
| 3 |
+-----+pop()은 이 반대로, 맨 위의 9를 떼어 내 반환하고 top이 다시 5를 가리킵니다.
파이썬 list의 맨 뒤를 top으로 쓰면 그대로 구현됩니다. append와 pop()은 O(1)이기 때문입니다.
class Stack:
def __init__(self):
self.items = []
def push(self, x):
self.items.append(x)
def pop(self):
if self.is_empty():
raise IndexError("빈 스택")
return self.items.pop()
def top(self):
return self.items[-1]
def is_empty(self):
return len(self.items) == 0맨 앞을 top으로 잡으면 insert(0, x)와 pop(0)을 써야 해서 매번 O(n)이 됩니다. 어느 끝을 top으로 삼느냐가 성능을 가릅니다.
4. 시간복잡도
| 연산 | 평균 | 최악 |
|---|---|---|
push | O(1) (amortized) | O(n) (용량 확장 시) |
pop | O(1) | O(1) |
top | O(1) | O(1) |
is_empty, len | O(1) | O(1) |
push의 최악 O(n)은 스택 자체가 아니라 파이썬 list의 dynamic array 확장에서 오는 비용입니다.
5. 응용: 계산기
사람은 3 + 4 * 2처럼 연산자를 피연산자 사이에 쓰는 중위 표기를 씁니다. 그런데 이 표기는 연산자 우선순위와 괄호를 따져야 해서 컴퓨터가 왼쪽부터 한 번에 읽어 계산하기 어렵습니다. 그래서 연산자를 피연산자 뒤에 두는 후위 표기로 바꾼 뒤 계산하는데, 두 단계 모두 스택을 씁니다.
후위 표기 계산. 숫자는 push하고, 연산자를 만나면 두 개를 pop해 계산한 결과를 다시 push합니다.
수식: 3 4 2 * + (= 3 + 4 * 2)
읽은 것 스택 (오른쪽이 top)
3 [3]
4 [3, 4]
2 [3, 4, 2]
* [3, 8] 4 * 2
+ [11] 3 + 8중위에서 후위로 변환. 피연산자는 바로 출력하고, 연산자는 스택에 쌓아 두다가 우선순위가 같거나 높은 연산자가 스택 위에 있으면 먼저 꺼내 출력합니다.
def to_postfix(tokens):
prec = {'+': 1, '-': 1, '*': 2, '/': 2}
S, out = Stack(), []
for t in tokens:
if t is 피연산자:
out.append(t)
elif t == '(':
S.push(t)
elif t == ')':
while S.top() != '(':
out.append(S.pop())
S.pop() # '(' 버림
else: # 연산자
while (not S.is_empty() and S.top() != '('
and prec[S.top()] >= prec[t]):
out.append(S.pop())
S.push(t)
while not S.is_empty():
out.append(S.pop())
return out토큰마다 push와 pop이 최대 한 번씩이라 변환과 계산 모두 O(n)입니다.
