Implement Queue using Stacks

Explanation & Solution

Description

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:

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

Notes:

You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

Examples

Example 1:

Input:

["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], [], [], []]

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

null

false

Explanation:

MyQueue myQueue = new MyQueue();

myQueue.push(1); // queue is: [1]

myQueue.push(2); // queue is: [1, 2]

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 the calls to pop and peek are valid

Approach

Stacks pattern

1. Two Stacks

inStack: receives all push operations
outStack: serves all pop and peek operations

2. Push Operation

Simply push the element onto inStack — O(1)

3. Transfer (Lazy)

When pop or peek is called and outStack is empty:
Transfer all elements from inStack to outStack by popping and pushing
This reverses the order, making the oldest element on top of outStack
If outStack already has elements, skip the transfer

4. Pop and Peek

After ensuring outStack has elements (via transfer), pop or peek from outStack

Key Insight

Each element is moved between stacks at most once, giving amortized O(1) per operation
The two stacks together maintain FIFO order: inStack holds newer elements, outStack holds older elements in reversed order
This is a classic design pattern interview question

Solution Code

Car Fleet

Removing Stars From a String