DSA problem
Implement Stack using Queues
Implement a last-in-first-out (LIFO) stack using only one queue. The implemented stack should support all the functions of a normal stack: push, top, pop, and empty. You may use only the standard queue operations — push to back, peek/pop from front, size, and is-empty.
MyStack() initializes the empty stack. push(x) pushes element x to the top of the stack. pop() removes the element on the top of the stack and returns it. top() returns the element on the top of the stack. empty() returns true if the stack is empty, false otherwise.
The elegant single-queue trick makes push expensive while keeping pop and top O(1). On push(x), first enqueue x at the tail. Then rotate the queue size - 1 times by repeatedly dequeuing the front and enqueuing it back at the tail. After this rotation, the freshly pushed x sits at the very front of the queue, exactly where the next pop/top will read it. Every previously pushed element shifts back by one position relative to the front.
This gives push an O(n) cost (with n the current size) and pop/top/empty an O(1) cost — a different cost profile than the two-queue variant but using only one queue total. The two-queue alternative makes pop expensive and push cheap; pick the variant that suits the workload.
Examples
["MyStack","push","push","top","pop","empty"]
[[],[1],[2],[],[],[]][null,null,null,2,2,false]["MyStack","push","push","push","pop","top"]
[[],[1],[2],[3],[],[]][null,null,null,null,3,2]["MyStack","push","pop","empty"]
[[],[7],[],[]][null,null,7,true]Constraints
- 1 <= x <= 9
- At most 100 calls will be made to push, pop, top, and empty.
- All the calls to pop and top are valid (the stack is not empty when called).
- You must use only standard queue operations.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.