문제 설명

Implement Queue using Stacks - LeetCode

해설

두 개의 스택을 사용하여 큐(Queue)를 구현하는 문제입니다.
큐는 FIFO (First-In-First-Out, 선입선출) 원칙을 따릅니다.
즉, 먼저 들어간 요소가 먼저 나와야 합니다.

✅ 구현해야 할 기능

  1. push(x): 요소 x를 큐의 뒤쪽(enqueue) 에 추가
  2. pop(): 큐의 앞쪽(dequeue) 요소를 제거하고 반환
  3. peek(): 큐의 앞쪽 요소를 조회(제거 없이 확인)
  4. empty(): 큐가 비어 있는지 확인

접근 방법 (Two Stack Approach)

큐를 구현하기 위해 두 개의 스택 (stack1, stack2) 을 사용합니다.

📌 주요 아이디어

  1. stack1: 요소를 추가(Enqueue)하는 용도
  2. stack2: 요소를 제거(Dequeue)하는 용도

✅ Push(삽입 연산)

  • 새 요소를 stack1에 그대로 추가

✅ Pop(제거 연산)

  • stack2가 비어 있다면, stack1의 모든 요소를 stack2로 이동
  • stack2에서 최상단(top) 요소를 꺼내서 반환

✅ Peek(조회 연산)

  • stack2에 요소가 있으면, 최상단(top) 요소 반환
  • stack2가 비어 있다면, stack1의 모든 요소를 stack2로 이동한 후 최상단 요소 반환

✅ Empty(빈 큐 확인)

  • stack1과 stack2가 모두 비어 있으면 True, 아니면 False

시간 복잡도 분석

연산시간 복잡도
push(x)O(1) (스택1에 추가)
pop()O(1) ~ O(N) (스택2에 요소가 있다면 O(1), 없다면 스택1에서 O(N) 이동)
peek()O(1) ~ O(N) (스택2에 요소가 있다면 O(1), 없다면 O(N) 이동)
empty()O(1) (스택 길이 확인)

📌 평균적으로 O(1) 연산이 가능하지만, pop()이나 peek()에서 stack1 → stack2로 이동할 때 O(N)이 발생할 수 있음

최적화 및 대체 방법

✅ Deque 활용

  • Python의 collections.deque 를 사용하면 O(1) 에 pop(0) 이 가능하여 더 효율적
  • collections.deque 는 양방향 큐를 지원

✅ 스택을 하나만 사용하는 방법

  • pop()을 호출할 때마다 재귀적으로 처리하는 방식 가능
  • 하지만, push() 시 O(N) 연산이 필요할 수 있어 성능 저하

💡 정리

✔ 큐의 동작(FIFO)을 두 개의 스택을 사용하여 구현
✔ push()는 stack1에 저장, pop()과 peek()은 stack2를 사용
✔ stack2가 비어 있으면 stack1에서 데이터를 옮겨 활용
✔ 일반적인 큐보다는 성능이 떨어지지만, 스택만으로 큐를 구현할 때 유용

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class MyQueue:
    def __init__(self):
        self.stack1 = []  # 입력 스택 (push 용도)
        self.stack2 = []  # 출력 스택 (pop 용도)

    def push(self, x: int) -> None:
        """ 요소를 큐의 뒤쪽에 삽입 """
        self.stack1.append(x)

    def pop(self) -> int:
        """ 큐의 앞쪽 요소를 제거하고 반환 """
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    def peek(self) -> int:
        """ 큐의 앞쪽 요소를 조회 (제거하지 않음) """
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]

    def empty(self) -> bool:
        """ 큐가 비어 있는지 확인 """
        return not self.stack1 and not self.stack2

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class MyQueue {
    constructor() {
        this.stack1 = []; // 입력 스택 (push 용도)
        this.stack2 = []; // 출력 스택 (pop 용도)
    }

    push(x) {
        // 요소를 큐의 뒤쪽에 삽입
        this.stack1.push(x);
    }

    pop() {
        // 큐의 앞쪽 요소를 제거하고 반환
        if (this.stack2.length === 0) {
            while (this.stack1.length > 0) {
                this.stack2.push(this.stack1.pop());
            }
        }
        return this.stack2.pop();
    }

    peek() {
        // 큐의 앞쪽 요소를 조회 (제거하지 않음)
        if (this.stack2.length === 0) {
            while (this.stack1.length > 0) {
                this.stack2.push(this.stack1.pop());
            }
        }
        return this.stack2[this.stack2.length - 1];
    }

    empty() {
        // 큐가 비어 있는지 확인
        return this.stack1.length === 0 && this.stack2.length === 0;
    }
}

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform