225. Implement Stack using Queues

Published on May 9, 2023

Question

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).

Algorithm

The question is asked to use two queues, we could implement as the 232, use the other queue as a container.

But we could save memory by only use one queue. Each time a new element comes we put it the top of the queue. The reason we can do this is that queue has two side opened which give us the flexibility.

Code

class MyStack {
    Queue<Integer> queue1;

    public MyStack() {
        queue1 = new LinkedList<>();
    }
    
    public void push(int x) {
        queue1.offer(x);
        int size = queue1.size();
        for (int i = 0; i < size - 1; i++) {
            queue1.offer(queue1.poll());
        }
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */