[자료구조 05] 스택, 마지막에 넣은 걸 먼저 꺼내기

접시를 차곡차곡 쌓아 두었다가 위에서부터 하나씩 꺼내 쓰는 모습을 떠올려 보세요. 가장 나중에 올려 둔 접시가 가장 먼저 나옵니다. 이렇게 마지막에 넣은 것을 가장 먼저 꺼내는 방식으로 데이터를 다루는 자료구조를 스택(stack, 쌓아 올린 더미)이라고 합니다. 영어 첫 글자를 따서 후입선출(LIFO, Last In First Out)이라 부르기도 합니다. 파이썬에서는 따로 준비된 도구 없이 리스트만으로 스택을 바로 쓸 수 있습니다. 하나씩 손으로 쳐 보며 감을 잡아 보겠습니다.

05.1 스택은 한쪽 끝만 씁니다

스택의 규칙은 단순합니다. 데이터를 넣을 때도 맨 위에 올리고, 꺼낼 때도 맨 위에서 내립니다. 중간이나 바닥에는 손을 대지 않습니다. 넣는 동작을 푸시(push, 밀어 넣기), 꺼내는 동작을 팝(pop, 꺼내기)이라고 부릅니다.

파이썬 리스트에서 맨 끝은 append로 붙이고 pop으로 뺍니다. 리스트의 끝이 곧 스택의 맨 위인 셈입니다. 리스트는 끝을 다루는 동작이 가장 빠르기 때문에, 끝만 쓰는 스택과 잘 어울립니다.

우리 주변에도 스택이 많습니다. 웹 브라우저의 뒤로 가기 버튼은 방문한 페이지를 차곡차곡 쌓았다가 가장 최근 페이지부터 되돌아갑니다. 함수가 다른 함수를 부르고 그 함수가 또 다른 함수를 부를 때, 컴퓨터는 나중에 부른 함수부터 끝내고 돌아옵니다. 이 모두가 후입선출입니다. "가장 최근 것을 먼저 처리한다"는 상황이 보이면 스택을 떠올리면 됩니다.

05.2 쌓고 꺼내 보기

가장 기본이 되는 동작부터 확인하겠습니다. a, b, c를 순서대로 쌓은 뒤 하나를 꺼내 보겠습니다.

stack = []

stack.append("a")

stack.append("b")

stack.append("c")

print(stack)

print(stack.pop())

print(stack)

['a', 'b', 'c']

c

['a', 'b']

a, b, c 순서로 쌓았는데 꺼낼 때는 가장 나중에 넣은 c가 먼저 나왔습니다. pop은 맨 끝 값을 빼면서 그 값을 돌려줍니다. 그래서 print(stack.pop())이 c를 찍었고, 스택에는 a와 b만 남았습니다. 이 "나중에 넣은 것이 먼저 나온다"가 스택의 전부입니다.

넣고 빼는 곳이 모두 끝이라 push와 pop은 각각 O(1)입니다. 데이터가 아무리 많이 쌓여 있어도 맨 위 하나만 건드리므로 걸리는 시간이 일정합니다.

꺼내지 않고 맨 위에 무엇이 있는지 확인만 하고 싶을 때는 stack[-1]을 봅니다. 리스트의 마지막 원소를 뜻하는 표기로, 값을 빼지 않고 들여다보기만 합니다. 이렇게 맨 위를 살짝 확인하는 동작을 픽(peek, 엿보기)이라고 부릅니다. 다만 pop과 달리 스택에서 값이 사라지지는 않습니다.

05.3 괄호가 짝이 맞는지 검사하기

스택이 실제로 빛나는 대표 예가 괄호 검사입니다. 코드 편집기나 수식 검사기는 여는 괄호와 닫는 괄호가 올바르게 짝을 이루는지 늘 확인합니다. 여는 괄호가 나오면 스택에 쌓아 두고, 닫는 괄호가 나오면 가장 최근에 쌓은 여는 괄호와 짝이 맞는지 보면 됩니다.

def balanced(s):

stack = []

pairs = {')': '(', ']': '[', '}': '{'}

for ch in s:

if ch in "([{":

stack.append(ch)

elif ch in ")]}":

if not stack or stack.pop() != pairs[ch]:

return False

return not stack

print(balanced("(a[b]{c})"))

print(balanced("(a[b)]"))

print(balanced("(("))

print(balanced(""))

True

False

False

True

첫 번째 문자열은 모든 괄호가 알맞게 닫혀 True입니다. 두 번째는 대괄호가 열린 상태에서 소괄호가 닫히려 하니 짝이 어긋나 False입니다. 세 번째는 여는 괄호만 두 개 남아 끝까지 닫히지 않았으니 False입니다. 마지막 빈 문자열은 검사할 괄호가 없어 처음부터 균형이 맞으므로 True입니다.

pairs는 닫는 괄호를 키로, 그에 맞는 여는 괄호를 값으로 담아 둔 딕셔너리입니다. 닫는 괄호 ch가 나오면 pairs[ch]로 짝이 되는 여는 괄호가 무엇인지 바로 알아냅니다. 그리고 stack.pop()으로 가장 최근에 쌓아 둔 여는 괄호를 꺼내 둘이 같은지 비교합니다. 스택이 이미 비어 있는데 닫는 괄호가 나오거나(not stack), 꺼낸 괄호가 짝이 아니면 곧바로 False를 돌려줍니다.

핵심은 마지막 줄 return not stack입니다. 문자열을 다 훑고 나서 스택이 비어 있어야 모든 여는 괄호가 제 짝을 만난 것입니다. 여는 괄호가 남아 있다면 아직 닫히지 않았다는 뜻이지요. 문자를 한 번씩만 훑으므로 복잡도는 O(n)입니다.

05.4 문자열을 거꾸로 뒤집기

스택의 성질을 그대로 보여 주는 또 다른 예가 문자열 뒤집기입니다. 글자를 하나씩 쌓았다가 다시 꺼내면 순서가 저절로 반대가 됩니다.

def reverse(s):

st = list(s)

out = ""

while st:

out += st.pop()

return out

print(reverse("hello"))

olleh

list(s)는 "hello"를 ['h', 'e', 'l', 'l', 'o']로 만듭니다. while st는 스택이 빌 때까지 반복하라는 뜻입니다. 빈 리스트는 거짓으로 취급되어, 값이 다 빠지면 반복이 저절로 멈춥니다. pop으로 맨 끝 o부터 차례로 꺼내 이어 붙이니 olleh가 됩니다. 나중에 넣은 것이 먼저 나오는 성질이 곧 순서 뒤집기가 되는 것입니다. 참고로 파이썬에서는 s[::-1]로도 문자열을 간단히 뒤집을 수 있지만, 스택으로 직접 해 보면 그 원리가 눈에 들어옵니다. 글자 수만큼 반복하므로 O(n)입니다.

05.5 실행 취소도 스택입니다

문서 편집기의 Ctrl+Z(실행 취소)도 스택으로 만듭니다. 작업을 할 때마다 그 기록을 차곡차곡 쌓아 두고, 되돌릴 때는 가장 최근 작업부터 하나씩 취소하기 때문입니다.

history = []

history.append("문서1")

history.append("문서1+글자")

print(history.pop()) # 마지막 동작 취소

print(history[-1]) # 되돌린 상태

문서1+글자

문서1

글자를 더한 상태가 가장 최근 기록이라 pop으로 먼저 취소됩니다. 그 결과 history[-1]이 가리키는 현재 상태는 다시 "문서1"로 돌아왔습니다. 가장 최근 것을 먼저 되돌린다는 점에서 실행 취소가 스택과 정확히 맞아떨어집니다. 쌓고 빼는 동작이라 O(1)입니다.

05.6 정리

스택은 마지막에 넣은 것을 먼저 꺼내는 후입선출 구조이고, 파이썬에서는 리스트의 append와 pop만으로 충분합니다. 넣기와 꺼내기가 모두 끝에서 일어나 각각 O(1)로 빠릅니다. 괄호 검사, 문자열 뒤집기, 실행 취소처럼 "가장 최근 것"을 먼저 다뤄야 하는 문제에서 스택을 떠올리면 코드가 훨씬 단순해집니다. 오늘 본 네 예제를 직접 쳐 보며 값이 쌓이고 빠지는 순서를 눈으로 따라가 보시기 바랍니다.