두 개의 스택으로 큐(Queue) 구현하기: 실전 면접에서 마주한 낯선 자료구조 문제

최근 실전 면접 라이브 코딩에서 "두 개의 스택으로 큐를 구현하라"는 문제를 처음 접했습니다. 평소에는 백준, 프로그래머스 등에서 알고리즘 문제만 풀어왔기에, 이렇게 직접 자료구조를 구현하는 문제는 예상치 못해 당황스러웠습니다. 이 글에서는 그때의 경험을 바탕으로, 문제의 개념과 구현 방법, 그리고 느낀 점을 정리합니다.

---

문제 소개: 알고리즘 문제만 풀다가 만난 직접 구현 과제

자료구조 면접에서 "스택(Stack)과 큐(Queue)의 차이"는 종종 등장하지만, 실제로 스택 두 개로 큐를 직접 구현하라는 문제는 저에게도 처음이었습니다. 단순히 개념을 아는 것과, 직접 코드를 짜는 것은 완전히 다르다는 점을 실감했습니다.

• 스택(Stack): LIFO(Last-In-First-Out, 후입선출)
• 큐(Queue): FIFO(First-In-First-Out, 선입선출)

비유: 스택은 접시를 쌓는 것, 큐는 줄 서서 차례를 기다리는 것과 비슷합니다.

---

핵심 아이디어: 스택 두 개로 큐의 동작을 흉내내기

큐는 먼저 들어온 데이터가 먼저 나가야(FIFO) 하지만, 스택은 반대입니다. 이 차이를 극복하기 위해 두 개의 스택을 사용합니다.

• in_stack: 데이터를 넣는 용도 (enqueue)
• out_stack: 데이터를 꺼내는 용도 (dequeue)

동작 원리

1. enqueue(x): in_stack에 데이터를 push
2. dequeue(): out_stack이 비어 있으면 in_stack의 모든 데이터를 pop해서 out_stack에 push (순서가 뒤집힘)
3. out_stack에서 pop하여 반환 (FIFO가 됨)

연산	동작 설명
enqueue	in_stack에 push
dequeue	out_stack이 비어 있으면 in_stack → out_stack
	out_stack에서 pop

---

파이썬 코드 예시: QueueUsingTwoStacks 클래스

class QueueUsingTwoStacks:
  def __init__(self):
    self.in_stack = []
    self.out_stack = []

  def enqueue(self, x):
    self.in_stack.append(x)

  def dequeue(self):
    if not self.out_stack:
      while self.in_stack:
        self.out_stack.append(self.in_stack.pop())
    if self.out_stack:
      return self.out_stack.pop()
    else:
      raise IndexError("dequeue from empty queue")

  def peek(self):
    if not self.out_stack:
      while self.in_stack:
        self.out_stack.append(self.in_stack.pop())
    if self.out_stack:
      return self.out_stack[-1]
    else:
      raise IndexError("peek from empty queue")

  def is_empty(self):
    return not self.in_stack and not self.out_stack

---

시간 복잡도 분석

• enqueue: O(1)
• dequeue: 평균적으로 O(1) (최악의 경우 O(n), 하지만 전체적으로 암ortized O(1))
• peek: dequeue와 동일

실전 팁: dequeue 시 in_stack의 모든 원소를 옮기는 작업은 한 번에 몰아서 일어나므로, 전체적으로 보면 각 원소당 한 번씩만 이동합니다.

---

실생활 예시로 이해하기

• in_stack: 새로 들어오는 손님이 줄을 서는 대기열
• out_stack: 실제로 서비스를 받는 손님이 나가는 출구
• 출구가 비어 있으면, 대기열의 손님을 한 번에 모두 출구로 이동시켜 차례대로 내보냅니다.

---

마무리: 왜 이 문제를 연습해야 할까?

• 자료구조의 본질을 이해하고, 면접에서 자주 나오는 패턴을 익힐 수 있습니다.
• 스택과 큐의 차이를 코드로 직접 구현하며 체감할 수 있습니다.
• 암ortized 시간 복잡도 개념을 자연스럽게 익힐 수 있습니다.

---

결론 및 인사이트

두 개의 스택으로 큐를 구현하는 문제는 단순한 코딩 테스트를 넘어, 자료구조의 동작 원리와 효율성까지 묻는 좋은 문제입니다. 실제 면접에서 당황하지 않으려면, 직접 구현해보고 동작 원리를 설명할 수 있도록 연습해보세요.