스택과 큐 - 되돌리기와 줄 서기

이 장에서 배우는 것

앞 장에서 연결 리스트의 노드를 이어 자료의 순서를 표현했다. 이번에는 자료를 어디에 놓는가보다 어떤 순서로 꺼내는가에 집중한다. 마지막에 넣은 것을 먼저 꺼내면 스택이고, 먼저 넣은 것을 먼저 꺼내면 큐다. 같은 배열을 사용해도 넣고 꺼내는 규칙에 따라 서로 다른 자료구조가 된다.

《논리로 푸는 알고리즘》이 자료구조를 사용해 문제를 푸는 쪽이라면, 이 책은 그 도구를 직접 만드는 쪽이다. 괄호 검사와 실행 취소를 구현하면서, 원하는 동작을 가능하게 하는 저장 위치와 상태 정보를 확인한다.

• 고정 크기 배열 위에 스택을 만들고 넣기와 꺼내기의 비용을 센다.
• 원형 큐의 시작 위치와 원소 수로 빈 상태와 가득 찬 상태를 구분한다.
• 양쪽 끝을 사용하는 덱의 동작을 직접 구현한다.
• 괄호 검사와 실행 취소에서 스택이 필요한 이유를 설명한다.
• 직접 만든 구현과 내장 구현의 결과를 비교하고, 측정한 횟수의 범위를 구분한다.

문제 상황

간단한 수식 편집기를 만든다고 하자. 사용자는 수식에 괄호를 입력하고, 잘못 입력한 내용은 실행 취소로 되돌린다. 저장 요청은 도착한 순서대로 처리한다. 화면은 하나지만 필요한 순서는 두 가지다. 실행 취소는 가장 최근 변경부터 되돌려야 하고, 저장 요청은 가장 먼저 도착한 요청부터 처리해야 한다.

변경 기록을 앞에서 꺼내면 오래전 상태부터 돌아가므로 실행 취소의 의미가 달라진다. 저장 요청을 뒤에서 꺼내면 나중 요청이 앞선 요청을 계속 추월할 수 있다. 자료를 넣고 꺼내는 규칙은 화면의 실제 동작과 연결된다.

여기서는 저장 요청 자체를 실행하는 대신 정수로 된 요청 번호를 사용한다. 큐의 용량을 세 칸으로 정하고, 두 요청을 처리한 뒤 새 요청을 넣어 배열 앞부분을 재사용한다. 실행 취소에서는 문자열 전체를 이전 상태로 저장한다. 긴 문서의 변경분을 저장하는 설계는 별도 문제이며, 여기서는 순서가 맞는지 확인하는 데 집중한다.

배열 스택: 마지막 기록부터 되돌리기

스택(stack)은 마지막에 넣은 원소를 먼저 꺼내는 자료구조다. 전공 수업에서는 이 규칙을 후입선출(LIFO)이라고 부른다. 넣는 연산은 push, 꺼내는 연산은 pop이라고 한다. 가장 위의 원소를 꺼내지 않고 읽는 연산은 peek라고 한다.

용량이 네 칸인 배열에 원소를 두 개 넣었다면, 사용 중인 구간은 인덱스 0부터 1까지다. 원소 수를 size로 저장하면 다음에 넣을 위치는 size이고, 꺼낼 위치는 size - 1이다. 원소를 넣거나 꺼낼 때 다른 원소를 옮길 필요가 없다.

배열의 실제 칸 수를 용량(capacity)이라고 한다. 용량과 원소 수는 다르다. 용량이 네 칸이어도 원소 수는 0부터 4까지 바뀐다. 이번 구현은 가득 찼을 때 배열을 늘리지 않고 예외를 발생시킨다. 예외는 정상적으로 작업을 마칠 수 없음을 호출한 쪽에 알리는 장치다.

실행 취소에서는 변경 직전의 상태를 스택에 넣는다. 빈 문자열에서 A로 바꾸기 전에 빈 문자열을 넣고, A에서 AB로 바꾸기 전에 A를 넣는다. 한 번 꺼내면 A로 돌아가고, 다시 꺼내면 빈 문자열로 돌아간다. 가장 최근에 저장한 상태가 가장 먼저 필요하기 때문이다.

괄호 검사도 같은 순서를 사용한다. 여는 괄호를 만나면 저장하고, 닫는 괄호를 만나면 가장 최근 여는 괄호와 짝을 맞춘다. 예를 들어 ([)]에서는 )를 만났을 때 가장 최근 여는 괄호가 [이므로 올바르지 않다. 여는 괄호와 닫는 괄호의 개수만 같다고 충분하지 않다.

원형 큐: 빈 앞칸을 다시 사용하기

큐(queue)는 먼저 넣은 원소를 먼저 꺼내는 자료구조다. 전공 수업에서는 선입선출(FIFO)이라고 부른다. 뒤에 넣는 연산은 enqueue, 앞에서 꺼내는 연산은 dequeue라고 한다. 배열의 맨 앞을 꺼낼 때마다 나머지를 한 칸씩 당기면 원소가 많을수록 이동도 많아진다.

원형 큐(circular queue)는 배열 끝 다음을 배열 처음으로 취급한다. 실제 배열이 둥글게 배치되는 것은 아니다. 위치를 계산하는 규칙이 순환할 뿐이다. 이 구현은 맨 앞 원소의 위치 head와 현재 원소 수 size를 저장한다. 다음 삽입 위치는 두 값으로 계산한다.

원형 큐의 위치와 상태를 결정하는 규칙

대상	규칙	의미
다음 삽입 위치	(head + size) % capacity	현재 원소들의 바로 다음 칸
꺼낸 뒤 시작 위치	(head + 1) % capacity	다음 원소가 새 맨 앞이 됨
빈 상태	size == 0	꺼낼 원소가 없음
가득 찬 상태	size == capacity	새 원소를 넣을 칸이 없음

%는 나머지를 구하는 연산자다. 용량이 3일 때 3 % 3은 0이고, 4 % 3은 1이다. 계산한 위치가 끝을 넘어가도 유효한 인덱스로 돌아온다. Python에서는 (-1) % 3도 2이므로 앞쪽으로 한 칸 돌아가는 계산에도 사용할 수 있다.

10, 20, 30을 넣고 두 번 꺼내면 head는 2이고 size는 1이다. 다음 삽입 위치는 (2 + 1) % 3이므로 0이다. 40과 50을 넣으면 실제 배열의 값은 앞에서부터 40, 50, 30이지만, 큐에서 꺼내는 순서는 30, 40, 50이다. 물리적인 배열 순서와 논리적인 대기 순서는 다를 수 있다.

이처럼 연산 전후에 계속 지켜야 하는 조건을 전공 수업에서는 불변식(invariant)이라고 부른다. 여기서는 0 ≤ size ≤ capacity이고, head가 항상 유효한 인덱스이며, 앞에서 i번째 원소가 (head + i) % capacity에 있다는 조건이다. 코드가 짧더라도 이 조건이 무너지면 큐의 순서가 깨진다.

덱과 연산 횟수의 기준

덱(deque)은 양쪽 끝에서 넣고 꺼낼 수 있는 자료구조다. 원형 큐에 앞쪽 삽입과 뒤쪽 제거를 추가하면 된다. 앞에 넣을 때는 head를 한 칸 뒤로 돌리고 그 칸에 기록한다. 뒤에서 꺼낼 때는 (head + size - 1) % capacity 위치를 읽는다. 중간 원소를 이동할 필요는 없다.

이 장에서는 배열 칸을 한 번 읽거나 쓰는 것을 칸 접근 한 번으로 센다. 원소를 넣으면 쓰기 한 번이다. 원소를 꺼내면 읽기 한 번과 비우기 한 번으로 두 번이다. 인덱스 계산, 정수 비교, 속성 접근, 함수 호출은 이 수에 포함하지 않는다. 실제 실행 시간을 재는 대신 원소 수에 따라 늘어날 수 있는 핵심 작업을 관찰하는 기준이다.

시간 복잡도는 입력 크기가 커질 때 작업량이 어떻게 늘어나는지를 나타낸다. 전공 수업에서 쓰는 O(1)은 원소 수와 관계없이 작업량이 일정한 범위에 머문다는 뜻이다. O(n)은 길이 n에 비례해 작업량이 늘어난다는 뜻이다. O(1)이 명령을 정확히 한 번 실행한다는 의미는 아니다.

완성 코드에서는 성공한 넣기와 꺼내기의 칸 접근을 누적하고, 검사기는 읽은 문자 수도 센다. 반복문이 없는 끝 연산은 인덱스 계산과 상태 변경도 일정한 횟수로 끝난다. 다만 이 설명은 용량과 인덱스를 보통의 고정 비용 정수 연산으로 다루는 모델을 따른다.

내장 구현과의 비교에서는 두 수를 구분한다. 공개된 메서드를 몇 번 호출했는지는 직접 셀 수 있지만, 내부에서 배열을 몇 번 읽었는지는 이 프로그램으로 알 수 없다. 따라서 내장 구현의 내부 접근 횟수를 추정해서 출력하지 않는다.

완성 코드

다음을 main.py로 저장한다. 직접 구현하는 부분에서는 고정 크기 리스트를 배열 저장소로만 사용한다. append, pop, insert, 슬라이싱으로 저장소 크기를 바꾸지 않는다. 마지막 비교 부분에서만 내장 리스트와 표준 라이브러리의 덱을 사용한다. 난수를 사용하지 않아 실행할 때마다 결과가 같다.

class ArrayStack:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("용량은 양수여야 한다")
        self.data = [None] * capacity
        self.capacity = capacity
        self.size = 0
        self.accesses = 0

    def push(self, value):
        if self.size == self.capacity:
            raise OverflowError("스택이 가득 찼다")
        self.data[self.size] = value
        self.accesses += 1
        self.size += 1

    def pop(self):
        if self.size == 0:
            raise IndexError("스택이 비었다")
        self.size -= 1
        value = self.data[self.size]
        self.data[self.size] = None
        self.accesses += 2
        return value

    def peek(self):
        if self.size == 0:
            raise IndexError("스택이 비었다")
        self.accesses += 1
        return self.data[self.size - 1]


class RingQueue:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("용량은 양수여야 한다")
        self.data = [None] * capacity
        self.capacity = capacity
        self.head = 0
        self.size = 0
        self.accesses = 0

    def enqueue(self, value):
        if self.size == self.capacity:
            raise OverflowError("큐가 가득 찼다")
        tail = (self.head + self.size) % self.capacity
        self.data[tail] = value
        self.accesses += 1
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("큐가 비었다")
        value = self.data[self.head]
        self.data[self.head] = None
        self.accesses += 2
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return value

    def peek(self):
        if self.size == 0:
            raise IndexError("큐가 비었다")
        self.accesses += 1
        return self.data[self.head]


class RingDeque(RingQueue):
    def appendleft(self, value):
        if self.size == self.capacity:
            raise OverflowError("덱이 가득 찼다")
        self.head = (self.head - 1) % self.capacity
        self.data[self.head] = value
        self.accesses += 1
        self.size += 1

    def popright(self):
        if self.size == 0:
            raise IndexError("덱이 비었다")
        tail = (self.head + self.size - 1) % self.capacity
        value = self.data[tail]
        self.data[tail] = None
        self.accesses += 2
        self.size -= 1
        return value


def is_pair(opening, closing):
    return (
        (opening == "(" and closing == ")")
        or (opening == "[" and closing == "]")
        or (opening == "{" and closing == "}")
    )


def check_brackets(text):
    stack = ArrayStack(max(1, len(text)))
    scanned = 0
    for index, char in enumerate(text):
        scanned += 1
        if char in "([{":
            stack.push(char)
        elif char in ")]}":
            if stack.size == 0:
                return False, index, scanned, stack.accesses
            if not is_pair(stack.pop(), char):
                return False, index, scanned, stack.accesses
    if stack.size != 0:
        return False, len(text), scanned, stack.accesses
    return True, -1, scanned, stack.accesses


def queue_demo():
    queue = RingQueue(3)
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    first = queue.dequeue()
    second = queue.dequeue()
    queue.enqueue(40)
    queue.enqueue(50)
    try:
        queue.enqueue(60)
    except OverflowError:
        print("가득 찬 큐: 거부")
    third = queue.dequeue()
    fourth = queue.dequeue()
    fifth = queue.dequeue()
    try:
        queue.dequeue()
    except IndexError:
        print("빈 큐: 거부")
    result = (first, second, third, fourth, fifth)
    print("큐 순서:", *result)
    print("큐 칸 접근:", queue.accesses)
    print("큐 성공 연산:", 10)
    return result


def undo_demo():
    history = ArrayStack(2)
    state = ""
    history.push(state)
    state = "A"
    history.push(state)
    state = "AB"
    print("현재 문서:", repr(state))
    state = history.pop()
    print("실행 취소:", repr(state))
    state = history.pop()
    print("실행 취소:", repr(state))
    print("스택 칸 접근:", history.accesses)


def deque_demo():
    deck = RingDeque(3)
    deck.enqueue(20)
    deck.appendleft(10)
    deck.enqueue(30)
    back = deck.popright()
    front = deck.dequeue()
    remaining = deck.dequeue()
    print("덱 꺼내기:", back, front, remaining)
    print("덱 칸 접근:", deck.accesses)


def boundary_demo():
    stack = ArrayStack(1)
    stack.push(None)
    value = stack.peek()
    removed = stack.pop()
    print("None 스택:", value is None, removed is None, stack.size)
    print("스택 조회 포함 접근:", stack.accesses)
    queue = RingQueue(1)
    queue.enqueue(None)
    value = queue.peek()
    removed = queue.dequeue()
    print("None 큐:", value is None, removed is None, queue.size)
    print("큐 조회 포함 접근:", queue.accesses)


# 여기부터는 결과 비교를 위한 내장 구현이다.
def builtin_check(text):
    stack = []
    calls = 0
    for index, char in enumerate(text):
        if char in "([{":
            stack.append(char)
            calls += 1
        elif char in ")]}":
            if not stack:
                return False, index, calls
            opening = stack.pop()
            calls += 1
            if not is_pair(opening, char):
                return False, index, calls
    if stack:
        return False, len(text), calls
    return True, -1, calls


def builtin_queue_demo(expected):
    from collections import deque

    queue = deque()
    calls = 0

    def put(value):
        nonlocal calls
        queue.append(value)
        calls += 1

    def take():
        nonlocal calls
        value = queue.popleft()
        calls += 1
        return value

    put(10)
    put(20)
    put(30)
    first = take()
    second = take()
    put(40)
    put(50)
    result = (first, second, take(), take(), take())
    print("내장 큐 결과 일치:", result == expected)
    print("내장 큐 성공 연산:", calls)
    print("내장 큐 내부 칸 접근: 측정하지 않음")


def bracket_demo():
    samples = ("([])", "([)]", "a+b]", "((x)")
    for text in samples:
        valid, position, scanned, accesses = check_brackets(text)
        other_valid, other_position, calls = builtin_check(text)
        same = valid == other_valid and position == other_position
        print(
            "괄호:", text,
            "정상:", valid,
            "위치:", position,
            "문자:", scanned,
            "칸:", accesses,
            "내장 호출:", calls,
            "일치:", same,
        )


def main():
    expected = queue_demo()
    undo_demo()
    deque_demo()
    boundary_demo()
    builtin_queue_demo(expected)
    bracket_demo()


if __name__ == "__main__":
    main()

줄별 해설

저장소와 스택의 경계

각 생성자의 첫 조건문은 용량이 0 이하인 경우를 거부한다. 원형 위치 계산에서 0으로 나누는 문제를 막고, 저장소가 최소 한 칸이라는 전제를 세운다. self는 현재 객체를 가리킨다. self.size처럼 저장한 값은 메서드 호출이 끝나도 객체에 남는다.

[None] * capacity는 지정한 개수의 칸을 만든다. None은 값이 없음을 표현할 때 사용하는 객체다. 다만 이 구현은 None도 정상 원소로 저장할 수 있다. 비었는지는 칸의 내용이 아니라 size로 판정하기 때문이다. boundary_demo가 용량 한 칸에서 이 동작을 확인한다.

push는 가득 찼는지 먼저 확인한 뒤 size 위치에 기록하고 원소 수를 늘린다. pop은 비었는지 확인한 뒤 원소 수를 먼저 줄인다. 줄인 값이 기존 맨 위 원소의 위치다. 읽은 칸을 None으로 바꾸면 저장소가 꺼낸 객체를 계속 참조하지 않는다. 이미 반환할 값을 지역 변수 value에 보관했으므로 반환에는 문제가 없다.

peek는 size를 바꾸지 않고 한 칸만 읽는다. boundary_demo에서는 넣기 한 번, 조회 한 번, 꺼내기 한 번을 수행한다. 따라서 칸 접근은 1 + 1 + 2로 4회다. 예외를 발생시키는 경로는 저장소에 접근하기 전에 끝나므로 칸 접근은 0회다. 조건을 검사하는 작업까지 없다는 뜻은 아니다.

큐와 덱의 위치 계산

enqueue의 tail은 이번 호출에서만 사용하는 삽입 위치다. 별도의 뒤쪽 위치를 객체에 저장하지 않으므로 head, 뒤쪽 위치, size 세 값을 동시에 맞출 필요가 없다. dequeue는 head의 값을 읽고 비운 뒤 head를 순환시킨다. 나머지 원소는 이동하지 않는다.

마지막 원소를 꺼낸 뒤 head를 0으로 되돌리지는 않는다. size가 0이면 현재 head가 어디든 빈 큐다. 다음 enqueue는 그 위치에서 다시 시작한다. 빈 상태를 특정 인덱스 하나에만 묶지 않는 설계다.

class RingDeque(RingQueue)는 큐의 저장소와 메서드를 물려받는다. 이런 코드 재사용을 상속(inheritance)이라고 한다. 여기서는 앞에서 꺼내기와 뒤에 넣기를 그대로 사용하고, appendleft와 popright만 추가한다. 덱에서 뒤를 꺼낼 때 head는 바뀌지 않는다. 맨 앞 원소의 위치가 그대로이기 때문이다.

queue_demo는 다섯 번 넣고 다섯 번 꺼낸다. 성공한 넣기의 칸 접근은 합계 5회이고, 꺼내기의 칸 접근은 합계 10회다. 가득 찬 상태와 빈 상태의 실패는 이 합계에 포함되지 않는다. deque_demo는 세 번 넣고 세 번 꺼내므로 3 + 6으로 9회다.

괄호 검사와 비교 코드

is_pair는 두 문자가 같은 종류의 여는 괄호와 닫는 괄호인지 판정한다. and는 두 조건이 모두 참인지, or는 연결한 조건 중 참이 있는지 검사한다. 조건의 개수는 입력 길이와 무관하게 고정되어 있다.

check_brackets는 길이만큼의 저장소를 한 번 만든다. 모든 문자가 여는 괄호여도 넘치지 않는 크기다. 빈 문자열은 저장소를 한 칸만 만들고 정상으로 처리한다. enumerate는 문자와 함께 0부터 시작하는 위치를 제공한다. 괄호가 아닌 문자는 읽은 문자 수에만 반영한다.

반환값은 정상 여부, 오류 위치, 읽은 문자 수, 칸 접근 수를 묶은 튜플(tuple)이다. 튜플은 여러 값을 일정한 순서로 묶는 Python 문법이며, 여기서는 스택이나 큐 저장소로 사용하지 않는다. 정상일 때 위치는 -1이다. 닫는 괄호에서 오류를 찾으면 그 문자의 인덱스를 반환한다. 끝까지 읽었는데 여는 괄호가 남으면 문자열 끝인 len(text)를 반환한다.

문자를 n개 읽는 동안 각 문자는 스택에 최대 한 번 들어가고 한 번 나온다. 따라서 칸 접근은 최대 3n회이며, 검사 반복문은 O(n)이다. 생성자가 n칸을 만드는 작업도 O(n)이므로, 중간에서 오류를 발견해도 이 구현의 전체 호출 비용에는 저장소 초기화가 포함된다. 추가 저장 공간도 O(n)이다.

builtin_queue_demo는 같은 성공 연산을 내장 덱에 수행한다. nonlocal은 안쪽 함수가 바깥 함수의 calls 값을 바꾼다는 선언이다. 내장 덱은 이번 비교에서 용량 제한 없이 사용하므로 가득 찼을 때의 정책은 비교하지 않는다. 내장 덱에 최대 길이를 주면 가득 찼을 때 반대편 원소를 버릴 수 있으므로, 예외를 내는 우리 큐와 같은 정책이라고 생각하면 안 된다.

builtin_check는 내장 리스트의 끝에 넣고 끝에서 꺼낸다. 직접 구현과 정상 여부 및 오류 위치를 비교한다. 내장 호출 수에는 append와 pop만 포함한다. 직접 구현의 칸 접근 수와 측정 단위가 다르다. 예를 들어 정상 괄호 두 쌍은 넣기 두 번과 꺼내기 두 번이므로 내장 호출은 4회이고 직접 구현의 칸 접근은 6회다.

실행 결과

macOS 또는 Linux의 터미널에서 main.py가 있는 디렉터리로 이동한 뒤 실행한다. 첫 명령은 소스를 실행하지 않고 문법을 컴파일해 확인한다. 정상이라면 출력이 없다. 파일을 추가로 만들지 않는 검사이기도 하다.

python3 -W error -c 'from pathlib import Path; compile(Path("main.py").read_text(encoding="utf-8"), "main.py", "exec")'
python3 main.py

예상 출력은 다음과 같다. 괄호 오류 위치는 사람이 세는 첫째, 둘째가 아니라 0부터 시작하는 인덱스다.

가득 찬 큐: 거부
빈 큐: 거부
큐 순서: 10 20 30 40 50
큐 칸 접근: 15
큐 성공 연산: 10
현재 문서: 'AB'
실행 취소: 'A'
실행 취소: ''
스택 칸 접근: 6
덱 꺼내기: 30 10 20
덱 칸 접근: 9
None 스택: True True 0
스택 조회 포함 접근: 4
None 큐: True True 0
큐 조회 포함 접근: 4
내장 큐 결과 일치: True
내장 큐 성공 연산: 10
내장 큐 내부 칸 접근: 측정하지 않음
괄호: ([]) 정상: True 위치: -1 문자: 4 칸: 6 내장 호출: 4 일치: True
괄호: ([)] 정상: False 위치: 2 문자: 3 칸: 4 내장 호출: 3 일치: True
괄호: a+b] 정상: False 위치: 3 문자: 4 칸: 0 내장 호출: 0 일치: True
괄호: ((x) 정상: False 위치: 4 문자: 4 칸: 4 내장 호출: 3 일치: True

a+b]에서는 저장한 여는 괄호가 없으므로 스택 칸을 읽지 않고 실패한다. ((x)에서는 여는 괄호 두 개를 넣고 하나만 꺼내므로 접근 횟수가 1 + 1 + 2로 4회다. 남은 괄호를 알아내는 데는 size만 확인하면 된다.

실무에서 자주 틀리는 것

빈 상태를 칸의 값으로 판정한다

다음 코드는 정상 원소로 넣은 None을 빈 상태로 오해한다. 저장된 값과 구조의 상태를 분리해야 한다.

# 틀린 코드
if self.data[self.head] is None:
    raise IndexError("큐가 비었다")

# 고친 코드
if self.size == 0:
    raise IndexError("큐가 비었다")

완성 코드의 boundary_demo처럼 None을 넣고 조회하고 꺼내 보면 차이를 확인할 수 있다. 반환값이 None이라는 사실만으로 실패를 나타내는 설계도 같은 혼동을 만들 수 있다. 여기서는 실패를 예외로 알린다.

배열 끝에서 위치를 순환시키지 않는다

head를 계속 증가시키면 아직 저장된 원소가 있어도 배열 범위를 벗어난다. size가 아니라 capacity를 기준으로 순환해야 한다. size는 꺼낼 때마다 달라지는 값이기 때문이다.

# 틀린 코드
self.head += 1

# 고친 코드
self.head = (self.head + 1) % self.capacity

queue_demo의 세 번째 꺼내기는 인덱스 2를 읽는다. 그다음 head가 0으로 돌아가야 40을 읽는다. 배열 앞부분을 재사용하는 사례가 빠지면 이 오류를 놓치기 쉽다.

괄호 개수만 맞추고 종류와 순서를 무시한다

닫는 괄호를 볼 때 아무 여는 괄호나 하나 꺼내는 것만으로는 부족하다. ([)]는 총개수가 같지만 올바른 중첩이 아니다. 중첩은 한 쌍 안에 다른 쌍이 들어가는 관계다.

# 틀린 코드: 비었는지는 이미 확인했다고 가정한다.
stack.pop()

# 고친 코드
opening = stack.pop()
if not is_pair(opening, char):
    return False, index, scanned, stack.accesses

또한 반복문을 마쳤다는 이유만으로 성공을 반환하면 안 된다. 남은 여는 괄호가 없는지 확인해야 한다. 완성 코드의 ((x)가 그 경우를 확인한다.

꺼내기 전에 모든 원소를 앞으로 옮긴다

다음 반복문은 값을 꺼낼 때마다 남은 원소 수에 비례한 작업을 만든다. n개가 있다면 읽기와 쓰기가 각각 n - 1회 추가된다.

# 틀린 코드: 원형 큐에서 불필요한 이동
for i in range(1, self.size):
    self.data[i - 1] = self.data[i]

# 고친 코드: 맨 앞 칸을 읽고 비운 다음 위치만 바꾼다.
self.head = (self.head + 1) % self.capacity
self.size -= 1

고친 부분은 dequeue의 뒷부분이며, 앞에서 수행하는 값 읽기와 칸 비우기도 필요하다. 원소를 옮기는 구현이 항상 잘못된 결과를 내는 것은 아니지만, 여기서 목표로 삼은 O(1) 꺼내기를 만족하지 못한다.

한눈에 보기

직접 구현한 연산의 칸 접근 수와 시간 복잡도

연산	칸 접근	시간	조건 또는 이유
스택 push	1회	O(1)	빈 한 칸에 기록
스택 pop	2회	O(1)	맨 위 읽기와 비우기
스택·큐 peek	1회	O(1)	상태를 바꾸지 않고 조회
큐 enqueue	1회	O(1)	삽입 위치 계산 후 기록
큐 dequeue	2회	O(1)	맨 앞 읽기와 비우기
덱 appendleft	1회	O(1)	head를 옮긴 뒤 기록
덱 popright	2회	O(1)	맨 뒤 읽기와 비우기
괄호 검사	최대 3n회	O(n)	길이 n의 저장소 초기화 포함

표의 단일 연산 횟수는 성공한 경우의 값이다. 가득 참 또는 비어 있음으로 실패한 연산은 칸 접근이 0회이며 시간은 O(1)이다. 용량 c인 스택·큐·덱의 생성은 c칸을 준비하므로 시간과 저장 공간이 O(c)다. 생성 비용과 생성 후 한 번의 연산 비용을 나누어 읽어야 한다.

실행 취소에는 스택의 순서가, 도착 순서 처리에는 큐의 순서가 맞는다. 양쪽 끝에서 자료를 다뤄야 하면 덱을 고려한다. 배열에 값이 놓인 모양만 보는 대신, 어떤 상태 정보가 사용 중인 구간을 결정하는지 함께 확인한다.

연습 문제

1. 용량 4인 원형 큐에 7, 8, 9를 넣고 두 번 꺼낸다. 이어서 10, 11, 12를 넣는다. head, size, 다음 꺼내기 순서와 전체 칸 접근 수를 구하라.
2. ArrayStack의 peek를 두 번 호출해도 원소 수가 유지되는지 확인하는 함수를 작성하라. 넣을 값은 5로 하고, 마지막에 한 번 꺼낸 뒤 칸 접근 수를 출력하라.
3. 괄호 검사기에 빈 문자열, {a[()]}, ]를 넣었을 때 반환되는 네 값을 예측하고 코드로 확인하라. 검사 대상은 괄호의 짝이며, 문자열 따옴표나 주석 문법은 해석하지 않는다고 가정한다.
4. 용량 3인 덱의 앞에 2를 넣고 다시 앞에 1을 넣는다. 뒤에 3을 넣은 뒤 앞, 뒤, 앞 순서로 꺼내는 코드를 작성하라. 꺼낸 순서와 칸 접근 수를 확인하라.

정답과 해설

1. 순환한 뒤의 논리적 순서

두 번 꺼낸 뒤 head는 2다. 이후 삽입은 head를 바꾸지 않으므로 최종 head도 2이고 size는 4다. 다음 순서는 9, 10, 11, 12다. 이 상태까지 넣기 여섯 번과 꺼내기 두 번을 했으므로 칸 접근은 6 + 4로 10회다. 남은 원소를 모두 꺼내면 8회가 추가된다.

def exercise_one():
    queue = RingQueue(4)
    for value in (7, 8, 9):
        queue.enqueue(value)
    queue.dequeue()
    queue.dequeue()
    for value in (10, 11, 12):
        queue.enqueue(value)
    print(queue.head, queue.size, queue.accesses)
    while queue.size:
        print(queue.dequeue())
    print(queue.accesses)

# exercise_one()의 출력:
# 2 4 10
# 9
# 10
# 11
# 12
# 18

2. 조회와 제거의 차이

peek는 값을 읽기만 하므로 두 번 호출한 뒤에도 size는 1이다. 넣기 한 번, 조회 두 번, 꺼내기 한 번을 합치면 칸 접근은 5회다.

def exercise_two():
    stack = ArrayStack(1)
    stack.push(5)
    print(stack.peek(), stack.peek(), stack.size)
    print(stack.pop(), stack.size, stack.accesses)

# exercise_two()의 출력:
# 5 5 1
# 5 0 5

3. 읽은 문자와 저장소 접근

빈 문자열에는 맞지 않는 괄호가 없으므로 정상이다. {a[()]}는 문자 일곱 개를 읽고 괄호 세 쌍을 처리한다. ]는 첫 문자에서 실패하며 저장소를 읽지 않는다. 이 검사기는 문장 속 모든 괄호를 검사하므로 프로그래밍 언어 전체의 문법 검사기로 사용할 수는 없다.

def exercise_three():
    for text in ("", "{a[()]}", "]"):
        print(check_brackets(text))

# exercise_three()의 출력:
# (True, -1, 0, 0)
# (True, -1, 7, 9)
# (False, 0, 1, 0)

4. 덱의 양쪽 끝

앞에 2를 넣고 다시 앞에 1을 넣으면 논리적 순서는 1, 2다. 뒤에 3을 넣은 뒤 앞, 뒤, 앞에서 꺼내면 1, 3, 2가 나온다. 세 번 기록하고 세 번 읽고 비우므로 칸 접근은 9회다. 각 해답 함수는 완성 코드의 main 호출 앞에 추가한 뒤 함수 이름으로 호출하면 실행할 수 있다.

def exercise_four():
    deck = RingDeque(3)
    deck.appendleft(2)
    deck.appendleft(1)
    deck.enqueue(3)
    first = deck.dequeue()
    second = deck.popright()
    third = deck.dequeue()
    print(first, second, third)
    print(deck.accesses)

# exercise_four()의 출력:
# 1 3 2
# 9