Implement stack using queues

XXX. Implement Stack Using Queues

Queue

Design

Problem Statement:

Implement a last-in-first-out (LIFO) stack using only queues. The implemented stack should support the following operations:

• push(int x): Push element x onto the stack.
• pop(): Removes the element on top of the stack and returns it.
• top(): Get the top element.
• empty(): Return whether the stack is empty.

You must use only standard queue operations — add, poll, peek, and isEmpty. Implement the stack such that the top and pop operations have O(1) time complexity.

Algorithm:

To simulate a stack using a single queue:

1. For the push operation:
   • Add the new element to the queue.
   • Rotate the queue by moving the front elements to the back, keeping the new element at the front.
2. For the pop operation:
   • Remove the front element of the queue.
3. For the top operation:
   • Return the front element of the queue without removing it.
4. For the empty operation:
   • Check if the queue is empty.

Complexity:

Time Complexity:

• push: O(n), where n is the number of elements in the queue (due to rotation).
• pop: O(1), as removing the front element of the queue is constant time.
• top: O(1), as peeking the front element is constant time.
• empty: O(1), as checking if the queue is empty is constant time.

Space Complexity: O(n), where n is the number of elements in the stack (stored in the queue).

Java Implementation:

class MyStack {

    private Queue queue = new LinkedList<>();

    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        for (int i = 1; i < queue.size(); i++)
            queue.add(queue.remove());
    }

    /** Removes the element on top of the stack and returns it. */
    public int pop() {
        return queue.remove();
    }

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

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