Implement Stack using Queues

Implement a last-in-first-out stack using only a queue (a FIFO structure). Support:

push(x) — push x onto the top.
pop() — remove and return the top element.
top() — return the top element without removing it.
empty() — return whether the stack is empty.

pop and top are only called on a non-empty stack. Use standard queue operations (enqueue at the back, dequeue from the front, peek front, size).

Hints

· Stuck? Reveal one nudge at a time.

A queue removes from the front, but a stack needs the newest element out first.

After pushing, rotate the queue so the new element sits at the front.

Then pop and top are just front-of-queue operations.

Common doubts

It keeps the invariant that the queue's front is the stack's top, so the front operations a queue offers directly implement pop and top.

Yes — a two-queue variant leaves push cheap and does the reordering during pop, moving all but the last element to a second queue.

Exactly size - 1: everything except the element you just enqueued, so that element ends up at the front.

Interview follow-ups

· What an interviewer asks next.

Push to a main queue; on pop, dequeue all but the last element into a second queue, return the last, then swap the queues.

They have the same amortized cost; choose based on whether pushes or pops dominate your workload.

Fun facts

Implementing one abstract structure with another is a classic reduction — it proves the two are equally expressive.
The rotation trick is the same 'rotate a ring' idea used in round-robin scheduling.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: push(1), push(2), top(), pop(), empty()
Output: 2, 2, false
top and pop both see 2 (the most recent); after popping, the stack still has 1, so empty is false.

Example 2

Input: push(5), pop(), empty()
Output: 5, true
Push then pop returns 5, leaving the stack empty.

Constraints

- 1 <= x <= 10^5 - At most 100 operations. - pop and top are only called on a non-empty stack.

A queue removes from the front, but a stack must remove the most recent element. The trick: after every push, rotate the queue so the newly added element sits at the front. Then the queue's front is always the stack's top, and pop/top are just front operations.

Prerequisites

Before you start

· Concepts used directly in the solution.

Queue operations. Enqueue at the back, dequeue from the front, peek the front.

Rotation. Moving front elements to the back to reorder the queue.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The contract

“Can I use a deque, or only a plain queue?”

Only queue operations — enqueue, dequeue, front, size — are assumed.

“Are pop and top ever called on an empty stack?”

No — they're guaranteed to be called only when the stack is non-empty.

The ideal opening — say it like this

A queue pops from the front, but a stack needs the newest element out first.

So after each push I rotate the queue: enqueue the new element, then move every earlier element behind it.

Now the front of the queue is always the stack top, so pop and top are front operations.

Understand the problem

Worked example — push 1, push 2, top, pop

push 1 -> queue [1]                (null)
push 2 -> enqueue 2 -> [1,2], rotate 1 -> [2,1]   (null)
top    -> front is 2               returns 2
pop    -> dequeue 2 -> [1]         returns 2

Key observations

1Aha

Keep the newest element at the front

By rotating after each push, the queue's front always holds the most recently pushed element — exactly the stack's top.

2Aha

Rotation reverses queue order into stack order

Moving the size - 1 older elements behind the new one flips FIFO into LIFO for that element, and inductively keeps the whole queue in stack order.

3Aha

Push is the expensive op

The rotation makes push O(n); pop, top, and empty are O(1). (A push-cheap variant does the rotation during pop instead.)

Summary

Key takeaway

Use one queue and keep its front as the stack top by rotating after each push: enqueue the new element, then move the older size - 1 elements behind it. Then pop/top are front operations. Push is O(n); the rest O(1).

push(x): enqueue x; repeat size-1 times: enqueue(dequeue())
pop():   return dequeue()
top():   return front()
empty(): return size == 0