Implement Stack using Queues
Understanding the Problem
We need to simulate a stack (LIFO) using only queues (FIFO). The two structures order their elements in opposite directions. A stack returns the most recently added element first; a queue returns the oldest element first.
The whole problem reduces to one question: how do we rearrange elements so a FIFO queue can serve them in LIFO order? Every solution shifts that rearranging cost to a different operation. We can pay it on every push (rearrange immediately so the front of the queue is always the newest element), or pay it on every pop (move elements aside to reach the newest one at retrieval time). The same idea also works with a single queue by rotating it after each push.
Key Constraints:
- At most
100calls across all operations. An O(n) operation runs at most 100 elements deep, so even quadratic total work is fine here. This is why we can freely pick the simplest correct rearrangement rather than optimizing for asymptotic balance. - All
popandtopcalls are valid, so we never have to handle an empty stack.
Approach 1: Two Queues (Push O(n), Pop O(1))
Intuition
Keep the queue in stack order at all times. If the front of the queue always holds the most recently pushed element, then pop and top reduce to reading the front.
To maintain that, we use two queues. When we push a new element, we put it into the empty secondary queue first, then move everything from the main queue behind it, one element at a time. This places the new element at the front, with all older elements lined up behind it in reverse order. We then swap the two queues so the secondary becomes the main.
The trade-off: every push costs O(n) because we move all existing elements, but pop and top are O(1) since the answer is always at the front.
Algorithm
- Maintain two queues:
q1(main) andq2(helper). - Push(x): Enqueue
xintoq2. Then dequeue every element fromq1and enqueue it intoq2. Nowq2has elements in stack order withxat the front. Swapq1andq2. - Pop(): Dequeue from the front of
q1and return it. - Top(): Peek at the front of
q1and return it. - Empty(): Return whether
q1is empty.
Example Walkthrough
Code
- Time Complexity: push: O(n), we move all n existing elements from q1 to q2. pop: O(1). top: O(1). empty: O(1).
- Space Complexity: O(n). We store all n elements across the two queues.
This approach makes push expensive and pop cheap. The next approach reverses that, delaying all rearranging until a pop happens.
Approach 2: Two Queues (Push O(1), Pop O(n))
Intuition
Instead of paying the cost during push, we defer it to pop. Push enqueues the element into q1 and does no rearranging.
The work happens during pop. The most recently pushed element sits at the back of the queue, so we dequeue all elements except the last one and move them into q2. The single element left in q1 is the one we return. We then swap q1 and q2 so the remaining elements are ready for the next operation.
This is the mirror image of Approach 1, and it wins when pushes far outnumber pops.
Elements enter q1 in push order, oldest at the front and newest at the back. A pop removes everything except the last element, and that last element is the newest one, which is what a stack returns. The elements moved to q2 keep their original relative order, so the next pop again finds the newest at the back.
The topElement variable avoids an O(n) scan on top. Push sets it to the new element. During pop, the loop assigns it the last value moved to q2, which is the second-to-last element of q1 and therefore the new top after the current top is removed.
Algorithm
- Maintain two queues:
q1(main) andq2(helper). Also track thetopElementfor O(1) top queries. - Push(x): Enqueue
xintoq1. UpdatetopElement = x. - Pop(): Dequeue all elements from
q1except the last one, moving them toq2. Track the second-to-last element as the newtopElement. Dequeue the final element fromq1(this is the stack's top). Swapq1andq2. Return the final element. - Top(): Return
topElement. - Empty(): Return whether
q1is empty.
Example Walkthrough
Code
- Time Complexity: push: O(1), enqueue and update topElement. pop: O(n), we move n-1 elements from q1 to q2. top: O(1). empty: O(1).
- Space Complexity: O(n). All n elements are stored across the two queues.
Both approaches so far use two queues. The follow-up asks for a single-queue solution, which the next approach achieves by rotating one queue in place.
Approach 3: Single Queue (Push O(n), Pop O(1))
Intuition
The second queue is unnecessary. After pushing a new element to the back of a single queue, rotate the queue by dequeuing from the front and re-enqueuing at the back. Doing this exactly size - 1 times moves the new element to the front.
A circular conveyor belt is a useful picture. You place a new item at the end, then rotate the belt until that item reaches the front, while the older items keep their relative order behind it.
This single-queue rotation is the answer to the follow-up.
The invariant is that the queue is always in stack order: front holds the newest element, back holds the oldest. A push appends x to the back, temporarily breaking the invariant, then rotates size - 1 times. Each rotation moves one of the older elements from front to back, so after size - 1 rotations every older element sits behind x, and the queue is back in stack order. Because push restores the invariant every time, pop and top read the correct element straight from the front.
Algorithm
- Maintain a single queue
q. - Push(x): Enqueue
xat the back ofq. Then rotate: dequeue from the front and enqueue to the back, repeatedsize - 1times. Nowxis at the front. - Pop(): Dequeue from the front of
qand return it. - Top(): Peek at the front of
qand return it. - Empty(): Return whether
qis empty.
Example Walkthrough
Code
- Time Complexity: push: O(n), we rotate n-1 elements after each push. pop: O(1). top: O(1). empty: O(1).
- Space Complexity: O(n). Only one queue holding all n elements.