205. Implement Stack using Queues
Build a last-in-first-out stack whose only internal storage is one or more standard queues — you may enqueue at the back, dequeue from the front, peek the front, and ask for size/emptiness, and nothing else (no indexing into the middle, no double-ended tricks).
Implement a class MyStack with four methods:
push(x)— put integerxon top of the stack.pop()— remove and return the value on top.top()— return the value on top without removing it.empty()— return whether the stack holds no elements.
The judge feeds your class a sequence of operations from stdin and prints each returned value. pop and top are only ever called on a non-empty stack.
The puzzle: a queue hands elements back in the opposite order a stack needs. How do you flip it?
Example 1:
Input: push(1), push(2), top(), pop(), empty()
Output: 2, 2, false
Explanation: After pushing 1 then 2, the top is 2. Popping removes the 2, and one element (the 1) is still inside, so empty() is false.
Example 2:
Input: push(4), pop(), empty()
Output: 4, true
Explanation: The only element is pushed and immediately popped, leaving an empty stack.
Constraints:
- 1 ≤ q ≤ 10⁴ operations
- -10⁹ ≤ x ≤ 10⁹
- pop and top are never called on an empty stack
- Use only standard queue operations: enqueue to the back, dequeue/peek at the front, size, and empty.
Hints:
A queue preserves arrival order, so after pushing 1, 2, 3 the front is 1 — but a stack must surface 3. Something has to reorder the elements; the only question is whether you pay for it on push or on pop.
Pay on pop: keep one main queue, and to pop, drain all but the last element into a helper queue. The straggler is the newest element — return it and swap the queues.
Pay on push: after enqueueing the new element, rotate the queue by dequeuing and re-enqueueing everything that was already there. The queue's front is then always the stack's top, making pop, top, and empty one-liners on a single queue.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: push(1), push(2), top(), pop(), empty()
Expected output: 2, 2, false