스택 2개로 큐를, 큐 2개로 스택을 만드는 방법과, 그 시간복잡도에 대해 설명해 주세요.

두 자료구조의 순서 방향이 반대임을 이용해, 한 자료구조를 두 번 뒤집어 다른 자료구조를 구현하는 방식입니다.

스택 2개로 큐 구현

inbox 스택에 넣고, outbox 스택으로 옮겨 순서를 역전시킵니다.

enqueue(1,2,3):          dequeue():
inbox                    inbox → outbox로 이동
[3] ← top               outbox
[2]                      [1] ← top  (순서 역전!)
[1]                      [2]
                         [3]
                         → poll() : 1 반환 O

class QueueUsingStacks {
    Deque<Integer> inbox  = new ArrayDeque<>(); // 입력용
    Deque<Integer> outbox = new ArrayDeque<>(); // 출력용

    void enqueue(int data) {
        inbox.push(data);   // O(1)
    }

    int dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty())
                outbox.push(inbox.pop()); // inbox → outbox 이동
        }
        return outbox.pop();
    }
}

시간복잡도

연산복잡도이유
enqueueO(1)inbox에 바로 push
dequeueO(1) 분할상환각 요소는 평생 1번씩만 이동
dequeue 최악O(n)outbox 비었을 때 전체 이동

분할상환(Amortized): n번 연산의 총 비용이 O(n)이므로 평균 O(1)

큐 2개로 스택 구현

매 pop 시 요소를 다른 큐로 옮겨 마지막 요소를 꺼냅니다.

push(1,2,3):          pop():
q1                    q1 → q2로 (n-1)개 이동
[1, 2, 3]             q1: [3]  ← 마지막 요소 반환
                      q2: [1, 2]
                      이후 q1, q2 swap

class StackUsingQueues {
    Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> q2 = new LinkedList<>();

    void push(int data) {
        q1.offer(data);     // O(1)
    }

    int pop() {             // O(n)
        // q1의 마지막 요소만 남기고 q2로 이동
        while (q1.size() > 1)
            q2.offer(q1.poll());

        int result = q1.poll(); // 마지막 요소 = top

        // q1, q2 swap
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;

        return result;
    }
}

시간복잡도

연산복잡도이유
pushO(1)큐에 바로 삽입
popO(n)매번 n-1개 요소 이동

최종 비교

구현push/enqueuepop/dequeue
스택 2개 → 큐O(1)O(1) 분할상환
큐 2개 → 스택O(1)O(n)

큐 2개로 스택을 만들면 pop이 항상 O(n)으로, 효율적인 구현이 어렵습니다. 반면 스택 2개로 큐를 만들면 분할상환 O(1)로 실용적인 구현이 가능합니다.

CSLOG에서 보기