Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Example 1:

Input [“MyStack”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2], [], [], []] Output [null, null, null, 2, 2, false]

Explanation MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // return 2 myStack.pop(); // return 2 myStack.empty(); // return False

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

Follow-up: Can you implement the stack using only one queue?

Approach: Single Queue with Rotation (Optimal Solution)

Algorithm

1. Use a single queue to store the elements
2. push(x): add x to the queue, then rotate the queue so x moves to the front
3. pop(): remove the front of the queue
4. top(): peek the front of the queue
5. empty(): check whether the queue is empty

Key Insight

A queue is FIFO, but a stack is LIFO. By rotating the queue after each push (moving the new element to the front), the queue’s front always represents the top of the stack. This satisfies the follow-up using only one queue.

Time & Space Complexity

• Time Complexity: O(n) for push (rotation), O(1) for pop, top, and empty
• Space Complexity: O(n) - queue stores n elements

Java Implementation

import java.util.LinkedList;
import java.util.Queue;

public class MyStack {

    private Queue<Integer> queue;

    /** Initialize the stack. */
    public MyStack() {
        queue = new LinkedList<>();
    }

    /** Push element x onto the stack. */
    public void push(int x) {
        int size = queue.size();
        queue.offer(x);
        // Rotate: move all previous elements behind x
        for (int i = 0; i < size; i++) {
            queue.offer(queue.poll());
        }
    }

    /** Remove and return the top element. */
    public int pop() {
        return queue.poll();
    }

    /** Return the top element. */
    public int top() {
        return queue.peek();
    }

    /** Return whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }

    // Test method
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        System.out.println("top(): " + stack.top());       // Expected: 2
        System.out.println("pop(): " + stack.pop());       // Expected: 2
        System.out.println("empty(): " + stack.empty());   // Expected: false
    }
}

Example Walkthrough

For the sequence push(1), push(2), top(), pop(), empty():

1. push(1): queue=[1]
2. push(2): add 2 → [1,2], rotate once → [2,1]
3. top(): peek front → 2
4. pop(): remove front → 2. queue=[1]
5. empty(): false

The rotation keeps the newest element at the front, matching stack LIFO behavior.

Alternative Approach: Two Queues

import java.util.LinkedList;
import java.util.Queue;

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

    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        // Swap the queues
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

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

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

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

The two-queue approach transfers all elements into the second queue on push, then swaps, achieving the same O(n) push cost.

Key Insights

1. Rotation Trick: Rotating after push keeps the newest element at the queue’s front
2. Single Queue Follow-up: The rotation approach answers the follow-up using only one queue
3. Queue-Only Operations: Only uses offer, poll, peek, size, and isEmpty
4. Trade-off: Push is O(n) while pop and top are O(1); this is an acceptable trade given the constraints

The single-queue rotation approach is the optimal solution, satisfying the follow-up requirement.