3 / 14강

스택과 되돌리기

글을 쓰다가 실행 취소를 누르면 가장 최근 작업부터 되돌립니다. 스택은 마지막에 넣은 것을 먼저 꺼내는 자료형입니다. 이 규칙을 LIFO(Last In, First Out)라고 합니다.

한쪽 끝에서만 넣고 빼기

• push: 맨 위에 항목을 넣습니다.
• pop: 맨 위 항목을 꺼냅니다.
• peek: 꺼내지 않고 맨 위 항목을 봅니다.

A 넣기 → B 넣기 → C 넣기 → 한 번 꺼내기를 하면 C가 나옵니다. 남은 항목은 아래부터 A, B 순서입니다. Python 리스트에서는 append()와 pop()으로 구현할 수 있습니다. 비어 있는 리스트에서 pop()을 하면 오류가 나므로 먼저 확인해야 합니다.

괄호 짝 맞추기

(()())처럼 중첩된 괄호는 가장 나중에 열린 괄호가 먼저 닫혀야 합니다. 스택을 쓰기 좋은 규칙입니다. 아래 예제는 소괄호만 검사하고 나머지 문자는 건너뜁니다.

def balanced(text):
    stack = []
    for char in text:
        if char == "(":
            stack.append(char)
        elif char == ")":
            if not stack:
                return False
            stack.pop()
    return not stack

print(balanced("(()())"))
print(balanced(")("))

첫 결과는 True, 두 번째는 False입니다. )(는 여는 괄호와 닫는 괄호의 수는 같지만 순서가 틀렸습니다. 닫는 괄호를 읽을 때 짝이 될 여는 괄호가 스택에 있어야 합니다.

문자마다 한 번씩 확인하므로 시간은 O(n)입니다. 여는 괄호만 계속 나오면 전부 저장하므로 추가 공간은 최악에 O(n)입니다.

함수 호출도 쌓입니다

함수가 다른 함수를 호출하면 원래 실행하던 위치를 기억해야 합니다. 호출이 끝나면 가장 최근 위치로 돌아옵니다. 1강에서 본 재귀도 이 호출 스택을 사용합니다. 재귀가 깊어질수록 기억할 호출이 늘어납니다.

확인 문제

빈 스택에 1, 2를 넣고 하나를 꺼냈습니다. 이어서 3을 넣고 두 번 꺼내면 어떤 순서로 나올까요?