Implement Stack Using Queues

Problem Description

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 only push to back, peek/pop from front, size and is empty operations are valid.

Examples

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.

Queue Rotation During Push

To simulate a LIFO stack using a FIFO queue, we can rotate the queue during insertion. When pushing a new element x:

1. Push x to the back of the queue.
2. For each existing element in the queue (excluding the new element x), pop it from the front and immediately push it back to the rear of the queue. This reverses the order of elements so that the newest element is always at the front of the queue, allowing pop and top operations to run in O(1) time.

Solution 1: Single Queue Rotation

Rotate queue elements on each push operation to maintain LIFO ordering at the front.

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

class MyStack {
    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        queue.add(x);
        int size = queue.size();
        // Rotate all previous elements to the back of the queue
        for (int i = 0; i < size - 1; i++) {
            queue.add(queue.remove());
        }
    }

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

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

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

from collections import deque

class MyStack:
    def __init__(self):
        self.queue = deque()

    def push(self, x: int) -> None:
        self.queue.append(x)
        # Rotate all previous elements to the back of the queue
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self) -> int:
        return self.queue.popleft()

    def top(self) -> int:
        return self.queue[0]

    def empty(self) -> bool:
        return len(self.queue) == 0

#include <queue>

class MyStack {
private:
    std::queue<int> q;

public:
    MyStack() {}

    void push(int x) {
        q.push(x);
        int size = q.size();
        // Rotate all previous elements to the back of the queue
        for (int i = 0; i < size - 1; i++) {
            q.push(q.front());
            q.pop();
        }
    }

    int pop() {
        int val = q.front();
        q.pop();
        return val;
    }

    int top() {
        return q.front();
    }

    bool empty() {
        return q.empty();
    }
};

Complexity Analysis

• Time Complexity: push takes O(n) time due to queue rotations. pop, top, and empty take O(1) time.
• Space Complexity: O(n) auxiliary space to store elements in the queue.

Where It Breaks

If push operations are frequent and elements count is very high, the O(n) push cost becomes a bottleneck. In that case, we can make push O(1) and shift rotation cost to pop/top, but we cannot make both O(1) simultaneously using only a FIFO queue.

Common Mistakes

• Incorrect rotation count: Rotating the queue size times instead of size - 1 times, which moves the newly inserted element back to the end and breaks the LIFO sequence.
• Null pointer exception: Calling pop or top on an empty stack (though prevented by constraints here).

Frequently Asked Questions

Why does this require only one queue instead of two? By popping and immediately appending to the same queue, we can rotate elements in-place without needing a second temporary queue.

Is it possible to implement this with O(1) push? Yes, by simply adding to the queue. Pop operations would then require copying n-1 elements to a secondary queue, taking O(n) time.

← All Problems