AlgoMaster Logo

Implement Stack using Queues

Last Updated: March 29, 2026

easy

Understanding the Problem

We need to simulate a stack (LIFO) using only queues (FIFO). The fundamental challenge is that these two data structures have opposite ordering. A stack gives you the most recently added element first, while a queue gives you the oldest element first.

So the core question is: how do we rearrange elements so that a queue can serve them in stack order? There are a few ways to think about this, and each one shifts the "cost" to a different operation. We can either pay the price when pushing (rearrange immediately so the front of the queue is always the newest element), or pay the price when popping (dig through the queue to find the newest element at retrieval time). There is also a clever single-queue approach that handles everything with just one queue.

Key Constraints:

  • 1 <= x <= 9 → Values are tiny single-digit integers. No overflow concerns.
  • At most 100 calls → Performance is a non-issue. Even O(n) per operation is fine for n up to 100.
  • All pop and top calls are valid → No need to handle empty stack errors.

Approach 1: Two Queues (Push O(n), Pop O(1))

Intuition

The most natural first attempt is to figure out how to 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 become trivial -- just read from the front.

To achieve this, we use two queues. When we push a new element, we put it into the empty secondary queue first, and then move everything from the main queue into the secondary queue, one by one. This places the new element at the front, with all older elements lined up behind it in reverse order. Then we swap the two queues so the secondary becomes the main.

The trade-off is clear: every push costs O(n) because we move all existing elements, but pop and top are O(1) since the answer is always sitting at the front.

Algorithm

  1. Maintain two queues: q1 (main) and q2 (helper).
  2. Push(x): Enqueue x into q2. Then dequeue every element from q1 and enqueue it into q2. Now q2 has elements in stack order with x at the front. Swap q1 and q2.
  3. Pop(): Dequeue from the front of q1 and return it.
  4. Top(): Peek at the front of q1 and return it.
  5. Empty(): Return whether q1 is empty.

Example Walkthrough

1Initial state: q1 = [], q2 = []
Front
Rear
1/6

Code

This approach makes push expensive and pop cheap. What if we flipped the trade-off and delayed the rearranging until someone actually asks for the top element?

Approach 2: Two Queues (Push O(1), Pop O(n))

Intuition

Instead of paying the cost upfront during push, we can flip the trade-off. Push is dead simple: just enqueue the element into q1. We don't rearrange anything.

The work happens during pop. To find the most recently pushed element (which is at the back of the queue), we dequeue all elements except the last one and move them into q2. The last element remaining in q1 is the one we want to return. Then we swap q1 and q2 so the remaining elements are ready for next time.

This approach is the mirror image of Approach 1. It is better when pushes are far more frequent than pops.

Algorithm

  1. Maintain two queues: q1 (main) and q2 (helper). Also track the topElement for O(1) top queries.
  2. Push(x): Enqueue x into q1. Update topElement = x.
  3. Pop(): Dequeue all elements from q1 except the last one, moving them to q2. Track the second-to-last element as the new topElement. Dequeue the final element from q1 (this is the stack's top). Swap q1 and q2. Return the final element.
  4. Top(): Return topElement.
  5. Empty(): Return whether q1 is empty.

Example Walkthrough

1Initial state: q1 = [], topElement = -1
Front
Rear
1/6

Code

Both approaches so far use two queues. The follow-up asks if we can do it with just one. Can we eliminate the second queue entirely by reusing the same queue with a rotation trick?

Approach 3: Single Queue (Push O(n), Pop O(1))

Intuition

Here is the clever insight: we don't actually need a second queue. After pushing a new element to the back of a single queue, we can rotate the entire queue by dequeuing elements from the front and re-enqueuing them at the back. If we do this exactly size - 1 times, the new element ends up at the front.

Think of it like a circular conveyor belt. You put a new item at the end, then rotate the belt until that item reaches the front. All the older items maintain their relative order behind it.

This is the most elegant solution and the one interviewers usually hope to see for the follow-up.

Algorithm

  1. Maintain a single queue q.
  2. Push(x): Enqueue x at the back of q. Then rotate: dequeue from the front and enqueue to the back, repeated size - 1 times. Now x is at the front.
  3. Pop(): Dequeue from the front of q and return it.
  4. Top(): Peek at the front of q and return it.
  5. Empty(): Return whether q is empty.

Example Walkthrough

1Initial state: q = []
Front
Rear
1/7

Code