Course4all

Implement Stack using Queues

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Stack.

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(); }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionImplement Queue using Stacks
Next Question →Evaluate Reverse Polish Notation