Implement a stack using queues
Problem
Implement a LIFO stack with push, pop, top and empty using only queue operations (enqueue to the back, dequeue from the front, size).
Example 1
Input: push(1), push(2), top(), pop(), empty() Output: 2, 2, false
Also asked as: Implement Stack using Queue · Implement Stack using Deque
Test cases
Case 1
Input: new StackViaQueue() .push(1) .push(2) .top() .pop() .empty() Expected: [null,null,2,2,false]
Case 2
Input: new StackViaQueue() .push(1) .push(2) .push(3) .pop() .pop() .top() Expected: [null,null,null,3,2,1]
Case 3
Input: new StackViaQueue() .empty() .push(3) .pop() .empty() Expected: [true,null,3,true]
View solutionHide solution1 approach
1. Single queue, rotate on push
Time push O(n), pop O(1)Space O(n)
After enqueueing x, rotate the queue so x is at the front (dequeue and re-enqueue the previous elements). push O(n), pop/top O(1).
class StackViaQueue { #q = []; push(x) { this.#q.push(x); for (let i = 0; i < this.#q.length - 1; i++) this.#q.push(this.#q.shift()); } pop() { return this.#q.shift(); } top() { return this.#q[0]; } empty() { return this.#q.length === 0; }}