AlgoViz
HomeStack

Implement Queue using Stack

Easy

Two stacks, in and out

Problem

Implement a queue using two stacks.

In simple words

Pour one stack into another to flip the order, so the oldest comes out first.

The idea

Push onto an input stack; when you need to dequeue and the output stack is empty, pour everything across, which reverses the order and puts the oldest element on top. Each element moves between stacks at most once, so dequeue is amortised O(1).

The trick

  • Only transfer when the output stack is empty, or the ordering breaks.
  • Amortised O(1) per operation even though a single transfer is O(n).

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
0
1

Step 1 of 2. Here's the example — enqueue 1,2; dequeue Values: 1, 2.

1/2
Optimal
timeO(1) amortizedspaceO(n)
1in-stack for enqueue2dequeue: if out empty, pour all of in into out; pop out

Input

array
[1, 2]

Output

answer
—

Check yourself

1 quick question about this walkthrough. A wrong answer costs nothing.

Example

Input:
enqueue 1,2; dequeue
Output:
returns 1

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.