Course4all

Implement Queue using Stacks

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Stack.

Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two his stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Easy

Examples

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

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

Intuition

To make a stack behave like a queue, the oldest entered elements must be kept at the top of the stack. For every newly pushed element, we can move all elements to a temporary stack, push the new element to the bottom, and move everything back.
⏱ O(N) for push operation, O(1) for pop and peek.💾 O(N) to store elements.
java
class MyQueue {
    java.util.Stack<Integer> s1 = new java.util.Stack<>();
    java.util.Stack<Integer> s2 = new java.util.Stack<>();
    public void push(int x) {
        while (!s1.isEmpty()) s2.push(s1.pop());
        s1.push(x);
        while (!s2.isEmpty()) s1.push(s2.pop());
    }
    public int pop() { return s1.pop(); }
    public int peek() { return s1.peek(); }
    public boolean empty() { return s1.isEmpty(); }
}
Approach 2

Level II: Recursive (One Stack)

Intuition

We can implement the 'pop' or 'peek' operation using a single stack and recursion. The function call stack acts as the second stack. To pop the bottom element, we pop the top, recurse to the bottom, and then push the popped element back as we return. This is less efficient than two stacks but insightful.
⏱ O(N) for pop/peek💾 O(N) recursion depth
java
import java.util.Stack;

class MyQueue {
    private Stack<Integer> s = new Stack<>();
    public void push(int x) { s.push(x); }
    public int pop() {
        int top = s.pop();
        if (s.isEmpty()) return top;
        int res = pop();
        s.push(top);
        return res;
    }
    public int peek() {
        int top = s.pop();
        if (s.isEmpty()) { s.push(top); return top; }
        int res = peek();
        s.push(top);
        return res;
    }
    public boolean empty() { return s.isEmpty(); }
}
Approach 3

Level III: Amortized O(1) with Two Stacks

Use an input stack to handle pushes and an output stack for peeks/pops. When the output stack is empty, transfer all elements from input to output. This reverses the order to FIFO.
⏱ O(1) amortized💾 O(N)

Detailed Dry Run

OperationValuein_stackout_stackOutput
push1[1][]-
push2[1, 2][]-
peek-[][2, 1]1
pop-[][2]1
empty-[][2]false
java
import java.util.Stack;

class MyQueue {
    private Stack<Integer> in = new Stack<>(), out = new Stack<>();
    public void push(int x) { in.push(x); }
    public int pop() {
        peek();
        return out.pop();
    }
    public int peek() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.peek();
    }
    public boolean empty() { return in.isEmpty() && out.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 QuestionMin Stack
Next Question →Implement Stack using Queues