Implement Queue using Stack

Easy

Problem

Implement a FIFO queue with push, pop, peek and empty, using only two stacks. Every operation should be O(1) amortised.

Example 1

Input:  push(1), push(2), peek(), pop(), empty()
Output: 1, 1, false

Also asked as: implement queue using stacks

Test cases

Case 1

Input:    new MyQueue()
.push(1)
.push(2)
.peek()
.pop()
.empty()
.pop()
.empty()
Expected: [null,null,1,1,false,2,true]

Case 2

Input:    new MyQueue()
.push(1)
.pop()
.push(2)
.push(3)
.pop()
.peek()
Expected: [null,1,null,null,2,3]

Case 3

Input:    new MyQueue()
.empty()
.push(9)
.peek()
.empty()
Expected: [true,null,9,false]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Two stacks, lazy transfer

Time O(1) amortisedSpace O(n)

Push onto `inbox`. To dequeue, if `outbox` is empty pour `inbox` into it (reversing order), then pop. Amortised O(1).

class MyQueue {
constructor() { this.inbox = []; this.outbox = []; }
push(x) { this.inbox.push(x); }
pop() { this.peek(); return this.outbox.pop(); }
peek() {
if (!this.outbox.length) while (this.inbox.length) this.outbox.push(this.inbox.pop());
return this.outbox[this.outbox.length - 1];
}
empty() { return !this.inbox.length && !this.outbox.length; }
}