스택 · Hong-Iron

요약

접시를 쌓으면 맨 위에 놓은 접시를 가장 먼저 꺼낸다. 스택은 이렇게 마지막에 넣은 것을 먼저 꺼내는 자료구조다. 이 규칙을 후입선출(LIFO)이라 부른다. “가장 최근 것과 짝 맞추기”나 “방금 한 일 되돌리기”에 딱 맞고, 넣기와 꺼내기가 한 번에 끝난다. 대신 맨 위만 볼 수 있어서, 중간에 있는 것을 찾으려면 느리다.

예시로 보기

괄호 문자열 "(()())"의 짝이 맞는지 본다. 여는 괄호를 만나면 쌓고, 닫는 괄호를 만나면 맨 위의 여는 괄호 하나를 꺼내 짝을 지운다.

읽은 글자	한 일	스택 (오른쪽이 맨 위)
(	넣기	(
(	넣기	( (
)	꺼내기	(
(	넣기	( (
)	꺼내기	(
)	꺼내기	(비었음)

끝났을 때 스택이 비었고, 중간에 빈 스택에서 꺼내려 한 적이 없으니 짝이 맞다. "())"라면 세 번째 글자에서 빈 스택을 꺼내려 해서 틀렸음을 안다.

닫는 괄호는 늘 가장 최근에 열린 괄호와 짝을 이룬다. “가장 최근 것”이 곧 스택의 맨 위라서 스택이 딱 맞는다.

쓰는 법

파이썬에서는 리스트의 끝을 스택의 맨 위로 쓴다¹.

스택의 일	파이썬 코드	비용
넣기 (push)	`st.append(x)`	$O(1)$ (평균)
꺼내기 (pop)	`st.pop()`	$O(1)$
맨 위 보기 (top)	`st[-1]`	$O(1)$
비었나	`not st`	$O(1)$
개수	`len(st)`	$O(1)$

지켜야 할 약속은 하나다. 넣고 빼는 일은 늘 리스트의 끝에서만 한다. st.pop(0)처럼 앞에서 빼면 스택이 아니라 큐가 되고, 속도도 $O(n)$으로 느려진다.

def balanced(s):
    st = []
    for ch in s:
        if ch == "(":
            st.append(ch)
        else:                  # ")"
            if not st:         # 짝지을 여는 괄호가 없다
                return False
            st.pop()
    return not st              # 남은 여는 괄호가 없어야 한다

검증: 괄호 검사를 “()를 더는 없앨 수 없을 때까지 지우는” 느린 방법과 길이 0~12의 모든 괄호 문자열(8,191개)에서 비교해 결과가 같았다. 예시 표와 확인 문제의 스택 상태도 실행해 확인했다 — 10_stack_impl.py

활용

괄호·태그 짝 맞추기, 되돌리기(Ctrl+Z), 웹 브라우저의 뒤로 가기, 연달아 같은 것 지우기, 쌓아 올리기 게임.
함수 호출도 스택이다. 함수가 다른 함수를 부르면 돌아올 자리를 쌓아 두고, 끝나면 맨 위부터 돌아온다. 그래서 재귀가 너무 깊으면 “스택이 넘쳤다”는 오류가 난다(재귀와 백트래킹).
다른 구조와 고르는 기준: 먼저 온 것을 먼저 처리해야 하면 큐를 쓴다(큐와 덱 문서). 스택은 가장 최근 것을 먼저 처리할 때 쓴다.
자주 하는 실수: 빈 스택에서 pop()이나 st[-1]을 하면 IndexError가 난다. 먼저 if st:로 확인한다.

연결

선수: 리스트와 문자열
대조: 큐와 덱은 먼저 넣은 것을 먼저 꺼낸다.
연습: 같은 숫자는 싫어, 크레인 인형뽑기 게임
balanced가 무엇을 확인하는지는 반복마다 늘 지켜지는 성질(루프 불변식)로 보인다. “i글자를 읽은 뒤 스택 크기는 앞 i글자의 여는 괄호 수 − 닫는 괄호 수다”가 매 바퀴 지켜진다는 것을 수학적 귀납법으로 증명한다. 그래서 이 함수는 “어느 앞부분에서도 닫는 괄호가 더 많지 않고, 끝에서 두 수가 같은가”를 검사한다.
(와 )만으로 된 문자열 가운데 balanced를 통과하는 것은 재귀적 정의와 구조적 귀납법에서 세 규칙(빈 문자열, (s), st)으로 만든 균형 괄호와 정확히 같다. 규칙으로 만든 문자열이 통과한다는 것은 구조적 귀납법으로 보인다. 거꾸로 통과한 문자열은 맨 앞 (와 그 짝으로 (A)B로 쪼갠 뒤, 길이에 대한 강한 귀납법으로 규칙에서 나온다는 것을 보인다.

과목별 관점

컴파일러 (3-2학기). 구문 분석기는 스택 하나로 돈다. 같은 스택인데 두 방식이 담는 것이 다르다.

위에서 내려오는 LL(1) 파서는 앞으로 봐야 할 기호를 쌓는다. 처음에 입력 끝 표시 $와 시작 기호를 넣는다. 맨 위를 꺼내 그것이 논터미널이면 표에서 고른 규칙의 오른쪽을 넣고, 터미널이면 입력의 다음 토큰과 맞춰 본다.
아래에서 올라가는 SLR 파서는 지금까지 본 것을 읽은 상태 번호를 쌓는다. 토큰을 읽으면 상태 하나를 넣는다. 규칙 $A \to \alpha$로 묶을 때는 $\alpha$의 기호 수만큼 꺼내고, 드러난 상태에서 $A$를 읽어 가는 상태 하나를 넣는다.

두 파서 모두 “가장 최근 것부터 처리한다”는 스택의 성질에 기댄다. 괄호 검사에서 닫는 괄호가 가장 최근에 열린 괄호와 짝을 이루듯, SLR 파서에서 묶이는 것은 늘 가장 최근에 쌓인 몇 칸이다. 한 예제 문법의 SLR 표로 id * id를 파싱하면 스택이 [1] → [1, 5] → [1, 3] → [1, 3, 6] → [1, 3, 6, 5] → [1, 3, 6, 3] → [1, 3, 6, 8] → [1, 2]로 바뀐다. 일곱째에서 여덟째로 갈 때 $E \to T * E$의 기호 수 3만큼 8, 6, 3을 꺼내고 2를 넣었다².

자료구조 (1-2학기). 스택을 다섯 가지 연산으로 정한다. 위 쓰는 법의 표와 이렇게 짝이 된다.

연산	하는 일	파이썬 리스트로는
IsEmpty	비었으면 참	`not st`
IsFull	더 넣을 자리가 없으면 참	없다. 리스트는 알아서 늘어난다
Top	맨 위 원소를 돌려준다	`st[-1]`
Push	맨 위에 넣는다	`st.append(x)`
Pop	맨 위를 뺀다	`st.pop()`

C에는 append와 pop을 해 주는 리스트가 없어서 스택을 직접 만든다. 배열 하나와 맨 위 칸의 번호로 만들거나(배열로 만든 스택), 노드를 이어서 만든다(연결 리스트로 만든 스택). IsFull은 칸 수가 정해진 배열로 만들 때 생기는 연산이다.

괄호 검사도 한 걸음 더 나간다. 짝이 맞는지만 보지 않고, 위치 $u$의 여는 괄호와 위치 $v$의 닫는 괄호가 짝일 때마다 $(u, v)$를 찍는다. 그러려면 여는 괄호 글자 대신 그 위치를 쌓는다. (a+b))*((c+d)에서는 (0, 4)를 찍고, 5번 닫는 괄호는 꺼낼 것이 없어 짝이 없다고 알리고, (8, 12)를 찍고, 끝까지 남은 7번 여는 괄호도 짝이 없다고 알린다. 풀이는 스택 응용 연습에 있다.

스택을 큐로 바꿀 수 없는 쓰임은 괄호 짝 찾기, 하노이 탑, 스위치박스 배선(switchbox routing), 함수 호출과 복귀, try-catch-throw다. 큐로 바꿔도 되는 쓰임은 미로의 쥐다. 큐로 바꾸면 출구까지 가장 짧은 길을 찾는다. 괄호 짝 찾기에 큐를 쓰면 (a(b)c)에서 (0, 4)와 (2, 6)이라는 엇갈린 짝이 나온다³.

확인 문제

C1 빈 스택에 넣기 1, 넣기 2, 꺼내기, 넣기 3, 넣기 4, 꺼내기를 차례로 했다. 꺼낸 값들과 남은 스택은?

답: 꺼낸 값은 2, 4이고, 남은 스택은 [1, 3](3이 맨 위)이다. 꺼낼 때마다 그때 맨 위의 것이 나온다.

C2 괄호 짝 검사에 스택이 알맞은 까닭은?

답: 닫는 괄호는 아직 닫히지 않은 여는 괄호 중 가장 최근 것과 짝을 이뤄야 한다. 스택은 가장 최근에 넣은 것을 맨 위에 두므로, 닫는 괄호가 올 때마다 맨 위를 꺼내면 된다.

C3 (가) 은행 창구에서 번호표 순서대로 부르기, (나) 문서 편집기의 되돌리기. 각각 스택과 큐 중 무엇인가?

답: (가)는 큐다. 먼저 온 손님을 먼저 부른다. (나)는 스택이다. 가장 최근에 한 일을 먼저 되돌린다.

C4 어떤 파서의 스택이 [1, 3, 6, 8](8이 맨 위)이다. 기호 3개짜리 규칙으로 묶으면서 “셋을 꺼내고, 드러난 맨 위 상태에서 갈 상태 2를 넣는다”를 했다. 스택은 어떻게 되는가? 꺼낸 값은 어떤 차례로 나오는가?

답: 8, 6, 3이 이 차례로 나오고 맨 위가 1이 된다. 거기에 2를 넣어 [1, 2]가 된다. 가장 나중에 넣은 8이 가장 먼저 나온다.

C5 식 ((a+b)*(c-d)를 왼쪽부터 읽는다. 여는 괄호를 만나면 그 위치(0부터 센다)를 스택에 넣고, 닫는 괄호를 만나면 하나 꺼내 (꺼낸 위치, 지금 위치)를 찍는다. 찍히는 쌍과, 다 읽은 뒤 스택에 남는 것을 써라.

답: (1, 5)와 (7, 11)이 찍히고 스택에 0이 남는다. 0번 여는 괄호는 짝이 없다.
이유: 0과 1을 넣은 뒤 5번 글자에서 맨 위의 1을 꺼낸다. 7을 넣고 11번 글자에서 7을 꺼낸다. 0은 끝까지 꺼내지지 않는다³.

Python 3 공식 튜토리얼 5.1.1 “Using Lists as Stacks”(append와 인자 없는 pop으로 스택을 쓴다). 스택의 정의와 연산은 Cormen·Leiserson·Rivest·Stein, Introduction to Algorithms 3판, 10.1 “Stacks and queues”. ↩
스택 변화는 28_slr-stack-parser_impl.py로 확인했다. ↩
13_stack-applications-practice_p1.c로 확인했다. ↩ ↩²

스택의 일	파이썬 코드	비용
넣기 (push)	`st.append(x)`	\(O(1)\) (평균)
꺼내기 (pop)	`st.pop()`	\(O(1)\)
맨 위 보기 (top)	`st[-1]`	\(O(1)\)
비었나	`not st`	\(O(1)\)
개수	`len(st)`	\(O(1)\)