Course4all
Join us on telegram
Home/dsa/Stack/Implement Stack using Queues

Implement Stack using Queues

Master this topic with zero to advance depth.

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

Easy

Examples

Input: ["MyStack", "push", "push", "top", "pop", "empty"]\n[[], [1], [2], [], [], []]
Output: [null, null, null, 2, 2, false]
Approach 1

Level I: Two Queues (Push O(N))

Intuition

When a new element arrives, enqueue it to a secondary empty queue. Then, dequeue all elements from the main queue and enqueue them after the new element. Finally, swap the main and secondary queues. The newest element is now at the front.

⏱ O(N) for push operation, O(1) for pop and top.💾 O(N) to store elements.
java
import java.util.*;

class MyStack {
    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();
    public void push(int x) {
        q2.add(x);
        while (!q1.isEmpty()) q2.add(q1.remove());
        Queue<Integer> temp = q1; q1 = q2; q2 = temp;
    }
    public int pop() { return q1.remove(); }
    public int top() { return q1.peek(); }
    public boolean empty() { return q1.isEmpty(); }
}
Approach 2

Level III: One Queue (Optimize Space)

When pushing an element, add it to the queue, and then rotate the queue (pop and re-add) N-1 times so the newly added element is now at the front. This avoids needing a second queue temporarily.

⏱ O(N) for push, O(1) for others💾 O(N)

Detailed Dry Run

OperationValueQueue StateAction
push1[1]Add 1
push2[1, 2] -> [2, 1]Add 2, rotate 1 element
pop-[1]Pop front (2)
empty-[1]Check if empty
java
import java.util.*;

class MyStack {
    private Queue<Integer> q = new LinkedList<>();
    public void push(int x) {
        q.add(x);
        for (int i = 0; i < q.size() - 1; i++) q.add(q.remove());
    }
    public int pop() { return q.remove(); }
    public int top() { return q.peek(); }
    public boolean empty() { return q.isEmpty(); }
}
← Previous QuestionImplement Queue using Stacks
Next Question →Evaluate Reverse Polish Notation