Implement Queue using Stacks

Description

232. Implement Queue using Stacks

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

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Example 1:

Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:
[null, null, null, 1, 1, false]

Explanation:

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek();  // return 1
myQueue.pop();   // return 1, queue is [2]
myQueue.empty(); // return false
 

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All calls to pop and peek are valid.

Follow-up: Can you implement the queue such that each operation is amortized $O(1)$ time complexity?

---

Approach 1: Two Stacks (Push $O(N)$, Pop $O(1)$)

Intuition

To make pop and peek operations $O(1)$, we keep the front of the queue always at the top of the primary stack s1.

When pushing x:

1. Move all elements from s1 to s2.
2. Push x into s1.
3. Move all elements back from s2 to s1.

import java.util.Stack;
 
class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
 
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new 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();
    }
}
 

Complexity

• Time Complexity:
  • push: $O(N)$ — Moves all elements back and forth twice.
  • pop, peek, empty: $O(1)$ — Direct operations on top of s1.
• Space Complexity: $O(N)$ — Stores all elements across two stacks.

---

Most Optimized Solution: Two Stacks (Amortized $O(1)$)

Intuition

Instead of moving elements back and forth on every single push, use two distinct stacks:

1. inStack: Used solely for receiving newly pushed elements (push).
2. outStack: Used solely for popping/peeking elements (pop / peek).

When pop() or peek() is called:

• If outStack is empty, move all elements from inStack into outStack. This reverses their order, making the oldest element sit at the top of outStack.
• If outStack is not empty, directly read or pop from outStack.

import java.util.Stack;
 
class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;
 
    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        peek(); // Ensure outStack has elements
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}
 

Complexity

• Time Complexity:
  • push: $O(1)$ — Always pushes directly into inStack.
  • pop, peek: Amortized $O(1)$ — Each element is pushed to inStack once and popped to outStack once across its entire lifetime.
  • empty: $O(1)$ — Checks if both stacks are empty.
• Space Complexity: $O(N)$ — Stores elements distributed between inStack and outStack.

---

Easy Memory Rule

“Push into inStack. Pop from outStack. If outStack is empty, dump inStack into outStack to reverse order.”