Implementing a Stack Using Two Queues

In the study of data structures, Stacks and Queues represent two fundamental ways of organizing linear data, yet they op

In the study of data structures, Stacks and Queues represent two fundamental ways of organizing linear data, yet they operate on diametrically opposed principles:

  • Stack: Follows the LIFO (Last-In, First-Out) principle. The last element added is the first one to be removed.
  • Queue: Follows the FIFO (First-In, First-Out) principle. The first element added is the first one to be removed.

A classic algorithmic challenge is to implement a Stack using only the operations available in a Queue. The difficulty arises from this inherent contradiction: how can we use a structure that prioritizes the "oldest" elements to simulate a structure that prioritizes the "newest" elements?

To resolve this, we must use a second queue as a buffer or "transfer station." By moving elements between the two queues, we can effectively reorder them, ensuring that the most recently added element eventually resides at the "front" of our primary queue, mimicking the "top" of a stack.

Implementation Strategies

There are two primary ways to approach this problem. While both achieve the same functional result, they distribute the computational "cost" differently between the push and pop operations.

Strategy 1: Push-Heavy (O(n) Push, O(1) Pop)

In this approach, we perform the heavy lifting during the push operation. Every time a new element is added, we rearrange the entire queue so that the newest element is always at the front. This makes the pop, top, and empty operations extremely efficient.

Strategy 2: Pop-Heavy (O(1) Push, O(n) Pop)

Here, we prioritize the push operation by simply adding the new element to the end of the queue. However, when a pop is requested, we must move all elements except the very last one into the auxiliary queue. The remaining element is our "stack top." This makes push very fast but makes pop and top computationally expensive.

Detailed Implementation (Strategy 1)

Below is a Python implementation of Strategy 1, which ensures that the pop operation remains $O(1)$. We use collections.deque to represent our queues.

from collections import deque

class MyStack:
    def __init__(self):
        # q1 acts as our main storage where the front is the stack top
        self.q1 = deque()  
        # q2 serves as an auxiliary buffer for reordering
        self.q2 = deque()  

    def push(self, x: int) -> None:
        # 1. Add the new element to the empty auxiliary queue
        self.q2.append(x)
        
        # 2. Move all existing elements from q1 to q2
        # This places the new element at the front of the sequence
        while self.q1:
            self.q2.append(self.q1.popleft())
            
        # 3. Swap the names of q1 and q2 so q1 always holds the data
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        # Since q1 is maintained such that the front is the stack top
        return self.q1.popleft()

    def top(self) -> int:
        # Return the element at the front of the queue
        return self.q1[0]

    def empty(self) -> bool:
        # Return True if the main queue is empty
        return not self.q1

Execution Walkthrough

Let's trace the state of the queues through a sequence of operations: push(1), push(2), and push(3).

  1. push(1):
    • q2 receives 1. q1 is empty, so no elements are moved.
    • After swapping, q1 = [1], q2 = [].
  2. push(2):
    • q2 receives 2.
    • We move 1 from q1 to q2. Now q2 = [2, 1].
    • After swapping, q1 = [2, 1], q2 = [].
  3. push(3):
    • q2 receives 3.
    • We move 2 and then 1 from q1 to q2. Now q2 = [3, 2, 1].
    • After swapping, q1 = [3, 2, 1], q2 = [].

At this point, the front of q1 is 3, which was the last element pushed. This perfectly simulates the LIFO behavior. If we call pop(), we get 3; if we call top(), we see 3.

Complexity Analysis

Operation Strategy 1 (Push-Heavy) Strategy 2 (Pop-Heavy)
Push $O(n)$ $O(1)$
Pop $O(1)$ $O(n)$
Top $O(1)$ $O(n)$
Empty $O(1)$ $O(1)$
Space $O(n)$ $O(n)$

Which one should you choose?

  • If your application involves frequent reads/pops but infrequent writes, Strategy 1 is superior.
  • If your application is write-intensive and you only occasionally need to access the top element, Strategy 2 provides better amortized performance for the push operation.

Beyond the Basics: Further Optimizations

While the two-queue approach is the standard solution, it is worth noting a few advanced insights:

  • The Single Queue Optimization: It is actually possible to implement a stack using only one queue. After performing a standard enqueue operation, you can determine the current size of the queue ($n$) and perform $n-1$ "rotate" operations (dequeuing an element and immediately enqueuing it back). This effectively moves the newest element to the front of the queue, achieving the same result as Strategy 1 without the need for a second physical queue.
  • The Symmetric Problem: A common follow-up question is: "How do you implement a Queue using two Stacks?" The logic is mirrored—one stack handles incoming data, and the second stack handles outgoing data, transferring elements only when the second stack is empty.

Mastering these transformations is not just about memorizing code; it is about understanding how different data structures can be composed to manipulate the flow of information. This conceptual flexibility is the foundation for working with more complex structures like Deques (Double-Ended Queues) and Priority Queues.