All Notes
Code
Code – Stack And Queue
Stack And Queue – Theory
Queue Using Stacks - A Deep Dive with Python Examples

Working with data structures is fundamental to being a proficient developer. While many languages provide built-in implementations, understanding how they work under the hood – and how to build them from more primitive structures – deepens your knowledge significantly. One classic problem that often appears in interviews and helps solidify these concepts is implementing a Queue using two Stacks.

This post will break down the problem, walk through the logic, provide a complete Python implementation, and analyze its performance.

The Core Problem: Queue vs. Stack

Before we dive into the solution, let’s quickly recap the fundamental differences between a Queue and a Stack:

  • Stack (LIFO - Last-In, First-Out): Think of a stack of plates. You add (push) plates to the top, and you remove (pop) plates from the top. The last plate you put on is the first one you take off.
  • Queue (FIFO - First-In, First-Out): Imagine a line at a store. People join (enqueue) at the back, and the person at the front is served (dequeue) first. The first person to join the line is the first one to leave.

The challenge is to replicate FIFO behavior using LIFO data structures.

The Two-Stack Approach: The Brains of the Operation

The elegant solution involves using two stacks, often referred to as input_stack (or enqueue_stack) and output_stack (or dequeue_stack).

Here’s the fundamental idea:

  1. input_stack: This stack is primarily used for the enqueue operation. When you add an element, you simply push it onto this stack. This maintains the order of arrival.
  2. output_stack: This stack is used for dequeue and peek operations. It holds elements in the correct FIFO order.

The magic happens when you need to dequeue an element. Since input_stack is LIFO, its top element is the most recently added, not the least recently added (which is what we need for a queue). To get the least recently added element, we need to reverse the order. This is where the output_stack comes in.

The “Transfer” Operation: When you need to dequeue or peek an element:

  • First, check if the output_stack is empty.
  • If output_stack is empty, it means we need to transfer elements from input_stack to output_stack. We do this by popping elements one by one from input_stack and pushing them onto output_stack. This effectively reverses the order of elements. The first element popped from input_stack (which was the last one pushed onto input_stack) becomes the last one pushed onto output_stack, and vice-versa. So, the first element pushed onto input_stack will be the first one popped from output_stack after the transfer.
  • Once the transfer is complete (or if output_stack was already not empty), you can now safely pop/peek from output_stack to get the true front element of the queue.

Let’s illustrate with an example:

  1. Enqueue 1, 2, 3:

    • input_stack: [1, 2, 3] (top is 3)
    • output_stack: []

  2. Dequeue:

    • output_stack is empty.
    • Transfer from input_stack to output_stack:
      • Pop 3 from input_stack, push 3 to output_stack. input_stack: [1, 2], output_stack: [3]
      • Pop 2 from input_stack, push 2 to output_stack. input_stack: [1], output_stack: [3, 2]
      • Pop 1 from input_stack, push 1 to output_stack. input_stack: [], output_stack: [3, 2, 1] (top is 1)
    • Now, output_stack has [3, 2, 1]. Pop from output_stack -> returns 1.
    • input_stack: []
    • output_stack: [3, 2]

This mechanism ensures that the element at the top of output_stack is always the oldest element that was enqueued, thus mimicking FIFO behavior.

Implementing QueueUsingStacks in Python

We’ll use Python lists as our underlying stack implementation, as they support append() for push and pop() for pop efficiently.

1. Initializing the Queue

We’ll start with a class structure and initialize our two stacks.

class QueueUsingStacks:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []
        print("Queue initialized with two empty stacks.")

# Example Usage:
my_queue = QueueUsingStacks()
Queue initialized with two empty stacks.

2. enqueue(item): Adding an Element

This is the straightforward part. Just push the new item onto the input_stack.

class QueueUsingStacks:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def enqueue(self, item):
        self.input_stack.append(item)
        print(f"Enqueued: {item}. input_stack: {self.input_stack}, output_stack: {self.output_stack}")

# Example Usage:
my_queue = QueueUsingStacks()
my_queue.enqueue(10)
my_queue.enqueue(20)
my_queue.enqueue(30)
Queue initialized with two empty stacks.
Enqueued: 10. input_stack: [10], output_stack: []
Enqueued: 20. input_stack: [10, 20], output_stack: []
Enqueued: 30. input_stack: [10, 20, 30], output_stack: []

3. _transfer_elements(): The Helper for Dequeue/Peek

This private helper method handles moving elements from input_stack to output_stack when output_stack is empty.

class QueueUsingStacks:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def enqueue(self, item):
        self.input_stack.append(item)
        # print(f"Enqueued: {item}. input_stack: {self.input_stack}, output_stack: {self.output_stack}")

    def _transfer_elements(self):
        if not self.output_stack:  # Only transfer if output_stack is empty
            if not self.input_stack: # If both are empty, nothing to transfer
                return

            print("Transferring elements from input_stack to output_stack...")
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
            print(f"Transfer complete. input_stack: {self.input_stack}, output_stack: {self.output_stack}")

# Example Usage (demonstrating transfer):
my_queue = QueueUsingStacks()
my_queue.enqueue(1)
my_queue.enqueue(2)
my_queue.enqueue(3)
# Manually call transfer to see its effect
my_queue._transfer_elements()
my_queue.enqueue(4) # Adding more elements after a transfer
print(f"After enqueueing 4: input_stack: {my_queue.input_stack}, output_stack: {my_queue.output_stack}")
my_queue._transfer_elements() # Demonstrating a second transfer (only transfers 4)
Queue initialized with two empty stacks.
Transferring elements from input_stack to output_stack...
Transfer complete. input_stack: [], output_stack: [3, 2, 1]
After enqueueing 4: input_stack: [4], output_stack: [3, 2, 1]
Transferring elements from input_stack to output_stack...
Transfer complete. input_stack: [], output_stack: [3, 2, 1, 4]

4. dequeue(): Removing an Element

This method first ensures output_stack has elements (by calling _transfer_elements), and then pops from it.

class QueueUsingStacks:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def enqueue(self, item):
        self.input_stack.append(item)

    def _transfer_elements(self):
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())

    def dequeue(self):
        self._transfer_elements()
        if not self.output_stack:
            raise IndexError("Dequeue from empty queue")
        
        item = self.output_stack.pop()
        print(f"Dequeued: {item}. input_stack: {self.input_stack}, output_stack: {self.output_stack}")
        return item

# Example Usage:
my_queue = QueueUsingStacks()
my_queue.enqueue('A')
my_queue.enqueue('B')
my_queue.enqueue('C')
print(f"Initial state before dequeue: input_stack: {my_queue.input_stack}, output_stack: {my_queue.output_stack}")

my_queue.dequeue()
my_queue.dequeue()
my_queue.enqueue('D') # Add an element after some dequeues
print(f"State after some operations: input_stack: {my_queue.input_stack}, output_stack: {my_queue.output_stack}")
my_queue.dequeue()
my_queue.dequeue() # Dequeue the last element, will trigger transfer again
my_queue.dequeue() # This should raise an error
Queue initialized with two empty stacks.
Initial state before dequeue: input_stack: ['A', 'B', 'C'], output_stack: []
Dequeued: A. input_stack: [], output_stack: ['C', 'B']
Dequeued: B. input_stack: [], output_stack: ['C']
State after some operations: input_stack: ['D'], output_stack: ['C']
Dequeued: C. input_stack: ['D'], output_stack: []
Dequeued: D. input_stack: [], output_stack: []
Traceback (most recent call last):
  File "<stdin>", line 39, in <module>
  File "<stdin>", line 21, in dequeue
IndexError: Dequeue from empty queue

Note: The IndexError is expected when trying to dequeue from an empty queue, mimicking Python’s list pop() behavior on an empty list.

5. peek(): Looking at the Front Element

Similar to dequeue, but without removing the element.

class QueueUsingStacks:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def enqueue(self, item):
        self.input_stack.append(item)

    def _transfer_elements(self):
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())

    def peek(self):
        self._transfer_elements()
        if not self.output_stack:
            raise IndexError("Peek from empty queue")
        
        item = self.output_stack[-1] # Peek without popping
        print(f"Peeked: {item}. input_stack: {self.input_stack}, output_stack: {self.output_stack}")
        return item

# Example Usage:
my_queue = QueueUsingStacks()
my_queue.enqueue('X')
my_queue.enqueue('Y')
print(f"Current front: {my_queue.peek()}")
my_queue.enqueue('Z')
print(f"Current front after Z: {my_queue.peek()}") # Peek again, should still be X
my_queue.dequeue() # Remove X
print(f"Current front after dequeue: {my_queue.peek()}")
Queue initialized with two empty stacks.
Peeked: X. input_stack: [], output_stack: ['Y', 'X']
Peeked: X. input_stack: ['Z'], output_stack: ['Y', 'X']
Dequeued: X. input_stack: ['Z'], output_stack: ['Y']
Peeked: Y. input_stack: ['Z'], output_stack: ['Y']

6. is_empty(): Checking for Emptiness

A queue is empty if both its input_stack and output_stack are empty.

class QueueUsingStacks:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def enqueue(self, item):
        self.input_stack.append(item)

    def _transfer_elements(self):
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())

    def dequeue(self):
        self._transfer_elements()
        if not self.output_stack:
            raise IndexError("Dequeue from empty queue")
        return self.output_stack.pop()

    def peek(self):
        self._transfer_elements()
        if not self.output_stack:
            raise IndexError("Peek from empty queue")
        return self.output_stack[-1]

    def is_empty(self):
        return not self.input_stack and not self.output_stack

# Example Usage:
my_queue = QueueUsingStacks()
print(f"Is queue empty? {my_queue.is_empty()}")
my_queue.enqueue(100)
print(f"Is queue empty? {my_queue.is_empty()}")
my_queue.dequeue()
print(f"Is queue empty? {my_queue.is_empty()}")
Queue initialized with two empty stacks.
Is queue empty? True
Is queue empty? False
Dequeued: 100. input_stack: [], output_stack: []
Is queue empty? True

Complete QueueUsingStacks Implementation

Here’s the combined class:

class QueueUsingStacks:
    """
    Implements a Queue (FIFO) data structure using two internal Stacks (LIFO).
    """

    def __init__(self):
        """
        Initializes the queue with two empty lists to serve as stacks.
        """
        self.input_stack = []
        self.output_stack = []
        print("--- QueueUsingStacks Initialized ---")
        print(f"Current state: input_stack={self.input_stack}, output_stack={self.output_stack}")

    def _transfer_elements(self):
        """
        Private helper method to transfer elements from input_stack to output_stack.
        This reverses the order, preparing elements for FIFO retrieval.
        Only transfers if output_stack is empty to optimize performance.
        """
        if not self.output_stack:
            if self.input_stack: # Only print and transfer if input_stack has elements
                print(f"--- Transferring elements. input_stack={self.input_stack} -> output_stack ---")
                while self.input_stack:
                    self.output_stack.append(self.input_stack.pop())
                print(f"--- Transfer complete. input_stack={self.input_stack}, output_stack={self.output_stack} ---")
            else:
                print("--- Both stacks empty. No transfer needed. ---")

    def enqueue(self, item):
        """
        Adds an item to the back of the queue.
        Operation: Pushes the item onto the input_stack.
        Time Complexity: O(1)
        """
        self.input_stack.append(item)
        print(f"ENQUEUE: {item}. State: input_stack={self.input_stack}, output_stack={self.output_stack}")

    def dequeue(self):
        """
        Removes and returns the item from the front of the queue.
        If output_stack is empty, transfers elements from input_stack first.
        Raises IndexError if the queue is empty.
        Time Complexity: O(1) amortized (O(N) in worst case when transfer occurs)
        """
        self._transfer_elements() # Ensure output_stack is ready

        if not self.output_stack:
            raise IndexError("Cannot dequeue from an empty queue.")
        
        item = self.output_stack.pop()
        print(f"DEQUEUE: {item}. State: input_stack={self.input_stack}, output_stack={self.output_stack}")
        return item

    def peek(self):
        """
        Returns the item at the front of the queue without removing it.
        If output_stack is empty, transfers elements from input_stack first.
        Raises IndexError if the queue is empty.
        Time Complexity: O(1) amortized (O(N) in worst case when transfer occurs)
        """
        self._transfer_elements() # Ensure output_stack is ready

        if not self.output_stack:
            raise IndexError("Cannot peek from an empty queue.")
        
        item = self.output_stack[-1] # Access top element without popping
        print(f"PEEK: {item}. State: input_stack={self.input_stack}, output_stack={self.output_stack}")
        return item

    def is_empty(self):
        """
        Checks if the queue is empty.
        Time Complexity: O(1)
        """
        is_empty_status = not self.input_stack and not self.output_stack
        print(f"IS_EMPTY? {is_empty_status}. State: input_stack={self.input_stack}, output_stack={self.output_stack}")
        return is_empty_status

    def size(self):
        """
        Returns the total number of elements in the queue.
        Time Complexity: O(1)
        """
        current_size = len(self.input_stack) + len(self.output_stack)
        print(f"SIZE: {current_size}. State: input_stack={self.input_stack}, output_stack={self.output_stack}")
        return current_size

# --- Comprehensive Demonstration ---
print("\n--- Starting QueueUsingStacks Demonstration ---")
q = QueueUsingStacks()

print("\n--- Enqueueing Elements ---")
q.enqueue('Apple')
q.enqueue('Banana')
q.enqueue('Cherry')
q.size()
q.is_empty()

print("\n--- Dequeueing and Peeking ---")
q.peek() # Should trigger transfer
q.dequeue() # Should be 'Apple'
q.size()
q.peek() # Should be 'Banana'
q.dequeue() # Should be 'Banana'
q.size()
q.is_empty()

print("\n--- Enqueueing More, Then Dequeueing ---")
q.enqueue('Date')
q.enqueue('Elderberry')
q.size()
q.peek() # Should be 'Cherry' (no transfer needed yet)
q.dequeue() # Should be 'Cherry'

print("\n--- Dequeueing remaining elements ---")
q.dequeue() # Should trigger transfer for 'Date', 'Elderberry'
q.size()
q.dequeue() # Should be 'Elderberry'
q.is_empty()
q.size()

print("\n--- Attempting to Dequeue from Empty Queue ---")
try:
    q.dequeue()
except IndexError as e:
    print(f"Caught expected error: {e}")

print("\n--- Attempting to Peek from Empty Queue ---")
try:
    q.peek()
except IndexError as e:
    print(f"Caught expected error: {e}")

print("\n--- End of Demonstration ---")
--- Starting QueueUsingStacks Demonstration ---
--- QueueUsingStacks Initialized ---
Current state: input_stack=[], output_stack=[]

--- Enqueueing Elements ---
ENQUEUE: Apple. State: input_stack=['Apple'], output_stack=[]
ENQUEUE: Banana. State: input_stack=['Apple', 'Banana'], output_stack=[]
ENQUEUE: Cherry. State: input_stack=['Apple', 'Banana', 'Cherry'], output_stack=[]
SIZE: 3. State: input_stack=['Apple', 'Banana', 'Cherry'], output_stack=[]
IS_EMPTY? False. State: input_stack=['Apple', 'Banana', 'Cherry'], output_stack=[]

--- Dequeueing and Peeking ---
--- Transferring elements. input_stack=['Apple', 'Banana', 'Cherry'] -> output_stack ---
--- Transfer complete. input_stack=[], output_stack=['Cherry', 'Banana', 'Apple'] ---
PEEK: Apple. State: input_stack=[], output_stack=['Cherry', 'Banana', 'Apple']
DEQUEUE: Apple. State: input_stack=[], output_stack=['Cherry', 'Banana']
SIZE: 2. State: input_stack=[], output_stack=['Cherry', 'Banana']
PEEK: Banana. State: input_stack=[], output_stack=['Cherry', 'Banana']
DEQUEUE: Banana. State: input_stack=[], output_stack=['Cherry']
SIZE: 1. State: input_stack=[], output_stack=['Cherry']
IS_EMPTY? False. State: input_stack=[], output_stack=['Cherry']

--- Enqueueing More, Then Dequeueing ---
ENQUEUE: Date. State: input_stack=['Date'], output_stack=['Cherry']
ENQUEUE: Elderberry. State: input_stack=['Date', 'Elderberry'], output_stack=['Cherry']
SIZE: 3. State: input_stack=['Date', 'Elderberry'], output_stack=['Cherry']
PEEK: Cherry. State: input_stack=['Date', 'Elderberry'], output_stack=['Cherry']
DEQUEUE: Cherry. State: input_stack=['Date', 'Elderberry'], output_stack=[]

--- Dequeueing remaining elements ---
--- Transferring elements. input_stack=['Date', 'Elderberry'] -> output_stack ---
--- Transfer complete. input_stack=[], output_stack=['Elderberry', 'Date'] ---
DEQUEUE: Date. State: input_stack=[], output_stack=['Elderberry']
SIZE: 1. State: input_stack=[], output_stack=['Elderberry']
DEQUEUE: Elderberry. State: input_stack=[], output_stack=[]
IS_EMPTY? True. State: input_stack=[], output_stack=[]
SIZE: 0. State: input_stack=[], output_stack=[]

--- Attempting to Dequeue from Empty Queue ---
--- Both stacks empty. No transfer needed. ---
Caught expected error: Cannot dequeue from an empty queue.

--- Attempting to Peek from Empty Queue ---
--- Both stacks empty. No transfer needed. ---
Caught expected error: Cannot peek from an empty queue.

--- End of Demonstration ---

Time and Space Complexity Analysis

Understanding the performance characteristics is key to choosing the right data structure.

Time Complexity:

  • enqueue(item): O(1)
    • Adding an element to input_stack is a constant time operation (Python’s list.append()).
  • dequeue(): O(1) Amortized
    • Worst Case: If output_stack is empty, all N elements from input_stack must be transferred. This involves N pops and N pushes, making it O(N) for that specific dequeue call.
    • Best Case / Average Case: If output_stack is not empty, it’s a simple pop, which is O(1).
    • Amortized Analysis: Consider a sequence of K enqueue and K dequeue operations. Each element is enqueued once (1 push to input_stack), transferred once (1 pop from input_stack and 1 push to output_stack), and dequeued once (1 pop from output_stack). This is a total of 4 operations per element over its lifetime in the queue. Thus, K operations cost 4K (roughly), making the amortized cost per operation O(1).
  • peek(): O(1) Amortized
    • The logic is identical to dequeue regarding the transfer, so its complexity is also O(1) amortized.
  • is_empty(): O(1)
    • Checking if two lists are empty is a constant time operation.
  • size(): O(1)
    • Summing lengths of two lists is constant time.

Space Complexity:

  • O(N)
    • Where N is the total number of elements currently in the queue. At any given time, all N elements will reside in either input_stack or output_stack (or be in the process of transferring). Therefore, the space required grows linearly with the number of elements.

Why Bother with This? Use Cases and Importance

  1. Interview Questions: This is a very common interview question designed to test your understanding of fundamental data structures, your ability to think algorithmically, and your grasp of concepts like amortized analysis.
  2. Deepening Understanding: Implementing a queue with stacks forces you to think about how data structures work beyond their abstract definitions. It clarifies the implications of LIFO vs. FIFO.
  3. Constraint-Based Programming: While high-level languages usually provide optimized queue implementations, imagine a scenario where you only have access to stack-like primitives (e.g., in a highly constrained embedded environment or when working with a specific API that only exposes stack operations). In such cases, this pattern becomes incredibly useful.
  4. Learning About Trade-offs: It highlights that while enqueue is always fast, dequeue/peek can occasionally be slow due to the transfer, but over time, they are efficient. This introduces the concept of amortized analysis, which is important for many algorithms (e.g., dynamic arrays like Python lists).

Conclusion

Implementing a Queue using two Stacks is a clever solution to a common data structure problem. It elegantly uses the LIFO property of stacks to achieve FIFO behavior, offering a practical example of how one Abstract Data Type (ADT) can be built from another. Understanding this pattern not only bolsters your algorithmic thinking but also provides valuable insights into time complexity analysis, especially amortized costs. It’s a testament to the power of thoughtful design in computer science.

Happy coding!

How Spotify Uses Shuffling Algorithms (It’s Not Really Random)
Jun 17, 2025
Learning Transformers by Building One
Jun 17, 2025
Linux Commands That Feel Like Superpowers
Jun 17, 2025
Greedy Algorithms In Graphs - A Developers Guide with Examples
Jun 18, 2025
Understanding Minimum Spanning Trees (MSTs) for Developers
Jun 18, 2025
Better Bash Scripts From Ugly Hacks to Elegant Tools
Jun 17, 2025
Last updated on
Share this post: Twitter Facebook LinkedIn
Introduction to Stacks - LIFO, Call Stacks, and Practical UsesThe Circular Queue Efficient Data Handling with a Twist