Queues & Design · 138Easy
Implement Queue using Stacks
Implement a FIFO queue using only two stacks. Support push(x), pop(), peek() and empty(). You may only use standard stack operations. Each operation should be O(1) AMORTIZED.
Constraints
- 1 <= x <= 9
- At most 100 calls are made.
- pop and peek are only called on a non-empty queue.
- API
- new MyQueue() initialize an empty queue
- push(x) -> void push x to the back of the queue
- pop() -> number remove and return the element at the front
- peek() -> number return the element at the front without removing it
- empty() -> boolean return true if the queue is empty
Examples
const q = new MyQueue(); q.empty() -> true // nothing pushed yet q.push(1); q.push(2); q.peek() -> 1 q.pop() -> 1 q.empty() -> false q.push(3); q.pop() -> 2 // FIFO survives an interleaved push q.pop() -> 3
Edge cases
- All calls are guaranteed valid, so pop and peek are never called on an empty queue.
Show the target complexity (spoiler)
- Naive
- O(n) per operation — shuttle all elements between the stacks on every push or pop.
- Target
- O(1) amortized — an input stack for pushes and an output stack for pops, refilled only when it runs empty.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/17-queues-and-design/138-implement-queue-using-stacks.js ./practice c 138