스택과 큐: 원형 큐 구현과 덱

스택(Stack)

LIFO(Last In First Out) 구조이다. 자료를 정해진 한 방향으로만 쌓을 수 있다.

• top을 통해서만 접근할 수 있고, top은 가장 최근에 추가된 자료를 가리킨다.
• 사용 예시: 브라우저 방문 기록의 뒤로 가기, 실행 취소

배열로 구현한 스택의 push는 정말 O(1)인가

배열로 스택을 구현하면 push와 pop이 O(1)이라고 한다. 그런데 배열이 꽉 차면 더 큰 배열을 새로 할당해 전체를 복사해야 한다. 이 경우에는 O(n)이 아닐까?

그 한 번의 push만 보면 O(n)이 맞다. 하지만 배열 크기를 두 배씩 늘리면 재할당은 드물게 일어나고, n번의 push에 든 전체 복사 비용을 합쳐도 O(n)이다. 이를 push 한 번당으로 나누면 평균 O(1)이 되며, 이렇게 계산한 것을 분할 상환(amortized) O(1) 이라고 한다.

큐(Queue)

FIFO(First In First Out) 구조이다. 한쪽에서는 삽입이, 다른 한쪽에서는 삭제가 이루어진다.

• 프론트(Front): 삭제 연산만 일어나는 곳
• 리어(Rear): 삽입 연산만 일어나는 곳
• 인큐(enQueue): 리어에서 일어나는 삽입 연산
• 디큐(deQueue): 프론트에서 일어나는 삭제 연산
• 사용 예시: 들어온 순서대로 처리해야 하는 작업

원형 큐(Circular Queue)

원형 큐는 선형 큐의 단점을 보완한 자료구조이다.

배열로 만든 선형 큐에서는 rear가 배열의 마지막 인덱스에 도달하면, 앞쪽에 디큐로 생긴 빈 공간이 있어도 활용할 수 없다. 원형 큐는 배열의 끝과 처음을 이어 붙여 이 공간을 다시 사용한다.

• 핵심은 index % max_size로 front와 rear의 인덱스를 조정하는 것이다.
• 크기가 고정되어 있으므로 가득 차면 더 넣을 수 없다.

구현

LeetCode 622번(Design Circular Queue) 문제를 《파이썬 알고리즘 인터뷰》를 참고해 배열로 구현했다.

가장 막혔던 부분은 isEmpty와 isFull의 조건이다. 두 경우 모두 front_idx == rear_idx가 되므로 인덱스만으로는 구분할 수 없다. 그 위치의 값이 None인지까지 확인해야 비어 있는 상태와 가득 찬 상태를 구분할 수 있다.

class MyCircularQueue:

    def __init__(self, k: int):
        self.max_size = k
        self.array = [None] * k
        self.front_idx = 0
        self.rear_idx = 0

    def enQueue(self, value: int) -> bool:
        if self.array[self.rear_idx] is None:
            self.array[self.rear_idx] = value
            self.rear_idx = (self.rear_idx + 1) % self.max_size
            return True
        else:
            return False

    def deQueue(self) -> bool:
        if self.array[self.front_idx] is None:
            return False
        else:
            self.array[self.front_idx] = None
            self.front_idx = (self.front_idx + 1) % self.max_size
            return True

    def Front(self) -> int:
        if self.array[self.front_idx] is None:
            return -1
        else:
            return self.array[self.front_idx]

    def Rear(self) -> int:
        if self.array[self.rear_idx - 1] is None:
            return -1
        else:
            return self.array[self.rear_idx - 1]

    def isEmpty(self) -> bool:
        return self.front_idx == self.rear_idx and self.array[self.front_idx] is None

    def isFull(self) -> bool:
        return self.front_idx == self.rear_idx and self.array[self.front_idx] is not None

덱(Deque)

Double-Ended Queue의 줄임말로, 양쪽 끝 모두에서 삽입과 삭제가 가능한 자료구조이다.

C++ deque의 임의 접근이 O(1)인 이유

덱을 이중 연결 리스트로 구현하면 임의 접근(Random Access)이 O(n)이지만, 동적 배열 기반으로 구현하면 O(1)에 가능하다.

C++의 std::deque는 데이터를 여러 개의 작은 고정 크기 배열에 나누어 저장하고, 앞이나 뒤에 공간이 필요해지면 작은 배열을 추가로 할당한다. 그리고 각 작은 배열을 가리키는 포인터들을 별도의 동적 배열로 관리한다.

인덱스가 주어지면 “몇 번째 작은 배열의 몇 번째 칸인지”를 계산으로 바로 구할 수 있으므로 O(1)에 접근할 수 있다.

Reference

• 파이썬 알고리즘 인터뷰
• Double-ended queue: Implementations - Wikipedia