13.9 Implement Stack Using Queues

13.9.1 Problem Metadata

Platform: Interview Prep
Problem ID: Stack via Queue
Difficulty: Easy
URL: N/A
Tags:
Techniques: Queue, Stack, Design

13.9.2 Description

Design a stack that supports push, pop, top, and empty using only standard queue operations.

13.9.3 Examples

MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // 2
stack.pop(); // 2
stack.empty(); // false

13.9.4 Constraints

Use only queue operations: enqueue, dequeue, size, isEmpty

13.9.5 Solution - Single Queue Rotation

13.9.5.1 Walkthrough

Maintain a single queue. For push(x) enqueue x, then rotate the previous elements to the back by dequeuing and enqueuing size - 1 times, so that x becomes the front. pop and top are queue front operations.

13.9.5.2 Analysis

Time Complexity: push O(n), others O(1)
Space Complexity: O(n)

13.9.5.3 Implementation Steps

push(x): enqueue x, then loop size-1 times moving front to back.
pop(): dequeue front.
top(): peek front.
empty(): check queue emptiness.

13.9.5.4 Code - Java

class MyStack {
    private final Queue<Integer> queue = new LinkedList<>();

    public void push(int x) {
        queue.offer(x);
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}