스택 2개로 큐 구현하기 (자료구조 응용)

소프트웨어 엔지니어링 면접이나 알고리즘 코딩 테스트에서 가장 빈번하게 등장하는 고전적인 문제 중 하나는 "스택(Stack) 두 개를 사용하여 큐(Queue)를 구현하시오"입니다. 얼핏 보면 단순한 자료구조 변환 문제처럼 보이지만, 이 질문의 이면에는 데이터의 흐름 제어와 시간 복잡도의 분할 상환 분석(Amortized Analysis)에 대한 깊은 이해가 깔려 있습니다. 후입선출(LIFO)의 성질을 가진 스택을 조합하여 어떻게 선입선출(FIFO)의 큐를 만들어낼 수 있을까요? 이 글에서는 그 논리적 배경과 구현 방법, 그리고 성능 분석까지 상세히 다룹니다.

1. 문제의 핵심: LIFO를 FIFO로 역전시키기

이 문제의 핵심은 자료구조의 입출력 순서를 뒤집는 것입니다.

스택(Stack): 나중에 들어온 데이터가 먼저 나갑니다. (Last-In, First-Out)
큐(Queue): 먼저 들어온 데이터가 먼저 나갑니다. (First-In, First-Out)

스택은 데이터를 넣고 빼면 순서가 역순이 됩니다. 그렇다면, 역순이 된 데이터를 다시 한 번 역순으로 뒤집으면 어떻게 될까요? 바로 원래의 순서(FIFO)가 됩니다. 즉, 두 개의 스택을 사용하여 '뒤집기'를 두 번 수행하는 것이 이 알고리즘의 핵심 원리입니다.

2. 알고리즘 동작 원리: In-Stack과 Out-Stack

두 개의 스택에 각각 역할을 부여하여 데이터를 관리합니다. 편의상 데이터를 입력받는 스택을 stack_in, 데이터를 출력하는 스택을 stack_out이라고 명명하겠습니다.

2-1. Enqueue (삽입) 연산

삽입 연산은 매우 단순합니다. 큐에 데이터가 들어오면 무조건 stack_in에 Push 합니다. 이때는 별도의 연산이 필요 없으므로 시간 복잡도는 O(1)입니다.

2-2. Dequeue (삭제) 연산

삭제 연산이 이 알고리즘의 하이라이트입니다. 큐에서 데이터를 뺄 때는 가장 먼저 들어온 데이터가 필요합니다.

만약 stack_out이 비어있지 않다면, stack_out에서 Pop 하여 반환합니다. (이미 순서가 뒤집혀 있으므로 큐의 맨 앞 데이터와 같습니다.)
만약 stack_out이 비어있다면, stack_in에 있는 모든 데이터를 꺼내서(Pop) stack_out으로 옮겨 담습니다(Push).
이 '옮겨 담기' 과정에서 데이터의 순서가 역전되어, stack_out의 맨 위(Top)에는 가장 먼저 들어왔던 데이터가 위치하게 됩니다.
이제 stack_out에서 Pop을 수행합니다.

3. 시간 복잡도 심층 분석 (Amortized Analysis)

많은 입문자가 Dequeue 연산에서 데이터를 옮기는 과정 때문에 시간 복잡도를 O(N)으로 오해하곤 합니다. 하지만 정확히 말하면 분할 상환 시간 복잡도(Amortized Time Complexity)는 O(1)입니다.

3-1. 왜 O(1)인가?

데이터 하나가 큐를 통과하는 과정을 추적해 봅시다.

stack_in에 Push 됩니다 (1회).
stack_in에서 Pop 되어 stack_out으로 이동합니다 (1회).
stack_out에 Push 됩니다 (1회).
stack_out에서 Pop 되어 최종 반환됩니다 (1회).

즉, 어떤 데이터든 큐에 들어와서 나갈 때까지 총 4번의 연산만 수행됩니다. 데이터가 N개일 때 총연산 횟수는 4N이며, 이를 평균 내면 상수 시간인 O(1)에 수렴하게 됩니다. 가끔 발생하는 '옮겨 담기' 비용은 전체적으로 분산되어 무시할 수 있는 수준이 됩니다.

4. 파이썬(Python) 구현 코드

리스트(List)를 스택처럼 사용하여 구현한 QueueUsingTwoStacks 클래스입니다.


class QueueUsingTwoStacks:
    def __init__(self):
        # 두 개의 스택 초기화
        self.stack_in = []
        self.stack_out = []

    def enqueue(self, item):
        # 들어오는 데이터는 무조건 stack_in에 저장
        self.stack_in.append(item)

    def dequeue(self):
        # 만약 stack_out이 비어있다면
        if not self.stack_out:
            # stack_in이 비어있는지 확인 (둘 다 비었으면 큐가 빈 것)
            if not self.stack_in:
                return None  # 또는 예외 발생
            
            # stack_in의 모든 요소를 stack_out으로 이동
            # 이 과정에서 순서가 LIFO -> FIFO 형태로 반전됨
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        
        # stack_out의 top 요소를 반환
        return self.stack_out.pop()

# 사용 예시
q = QueueUsingTwoStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

print(q.dequeue())  # 1 출력 (FIFO)
print(q.dequeue())  # 2 출력
q.enqueue(4)
print(q.dequeue())  # 3 출력
print(q.dequeue())  # 4 출력

[핵심 요약 : 스택 2개로 큐 만들기]
1. 원리: Input Stack과 Output Stack 두 개를 이용해, 데이터를 옮길 때 순서를 뒤집어 FIFO를 구현합니다.
2. 성능: Dequeue 시 데이터 이동이 발생하지만, 분할 상환 분석에 따르면 평균 시간 복잡도는 O(1)로 매우 효율적입니다.
3. 의의: 제한된 환경(스택만 사용 가능한 경우)에서 자료구조를 유연하게 변형하여 사용하는 응용 능력을 보여줍니다.

kguidebook0001 님의 블로그