Course4all
Join us on telegram
Home/dsa/Stack/Implement Queue using Stacks

Implement Queue using Stacks

Master this topic with zero to advance depth.

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(); }
}
← Previous QuestionMin Stack
Next Question →Implement Stack using Queues