Implement a stack using queues

Easy

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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; }
}