Stack • Design Problems

Implement Queue using Stacks

Design a First-In-First-Out (FIFO) queue using only two standard Last-In-First-Out (LIFO) stacks. This is a classic FAANG interview question.

Try Interactive Simulator

The Two Stacks

We designate `s1` as the Input Stack and `s2` as the Output Stack. Enqueuing is dead simple: just push to `s1`!

The Dequeue Trick

When someone calls dequeue, we need the OLDEST element. But `s1` holds the NEWEST element on top. So, we pop everything from `s1` and push it to `s2`. This completely reverses the order!

Amortized O(1)

Transferring elements takes O(N) time. BUT, we only transfer when `s2` is totally empty. Most dequeue calls will just pop directly from `s2` in O(1) time. Over time, it averages out to O(1).

S1 (Input)

S2 (Output)

Code Tracker

:::

1function enqueue(val) {

2 s1.push(val);

3}

4

5function dequeue() {

6 if (s2.length === 0) {

7 while (s1.length > 0) {

8 s2.push(s1.pop());

9 }

10 }

11 return s2.pop();

12}

Queue Using Stacks

Queue Using Stacks

Implement Queue using Stacks

The Two Stacks

The Dequeue Trick

Amortized O(1)

Implement Queue using Stacks

The Two Stacks

The Dequeue Trick

Amortized O(1)