Implement Queue using Stack
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]
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; }}