Building a Stack from Queues - A Practical Deep Dive
As developers, we frequently interact with fundamental data structures like Stacks and Queues. A Stack operates on a Last-In, First-Out (LIFO) principle, where the last element added is the first one removed (think of a stack of plates). A Queue, on the other hand, follows a First-In, First-Out (FIFO) principle, where the first element added is the first one removed (think of a line at a store).
Normally, we’d use a dedicated array-based list or a linked list to implement a stack directly for optimal performance. So why would anyone try to build a Stack using Queues?
- Conceptual Understanding: It forces you to think deeply about the properties of LIFO and FIFO and how to transform one into the other. This significantly sharpens your data structure manipulation skills.
- Interview Questions: This is a classic interview question designed to test your problem-solving abilities, understanding of fundamental data structures, and ability to reason about complexity.
- Constraint-Based Scenarios: In rare, specialized environments, you might be provided with only a Queue interface (e.g., a message queue service) and need to simulate Stack behavior.
Let’s dive into how we can achieve this. We’ll explore a couple of common strategies, complete with Python implementations and complexity analysis.
For our queue implementations, we’ll use Python’s collections.deque, which provides efficient append() (enqueue) and popleft() (dequeue) operations, making it ideal for queue-like behavior.
Core Stack Operations We Need to Implement:
push(x): Adds elementxto the top of the stack.pop(): Removes and returns the element at the top of the stack.top()(orpeek): Returns the element at the top of the stack without removing it.is_empty(): Checks if the stack is empty.size(): Returns the number of elements in the stack.
Approach 1: Two Queues - O(1) Push, O(N) Pop
In this approach, the push operation is efficient (O(1)), but the pop operation takes more time (O(N), where N is the number of elements in the stack).
The Idea:
We’ll maintain two queues, let’s call them q1 (the main queue) and q2 (a helper queue).
push(x): Simply addxtoq1. This is straightforward.pop(): This is where the magic (and complexity) happens. To get the LIFO element from a FIFO queue, we need to move all elements fromq1except the very last one intoq2. The element left inq1will be the one we need to “pop.” After popping it, we swapq1andq2soq1is always our primary queue containing the “stack” elements in the correct (but reversed for a queue) order.top(): Similar topop(), but after identifying the top element, we move it back toq2along with the others, then swap, so the element is not removed.
Let’s trace an example:
Stack: []
push(10):q1 = [10],q2 = []push(20):q1 = [10, 20],q2 = []push(30):q1 = [10, 20, 30],q2 = []Stack conceptually: [10, 20, 30] (30 on top)
Now, pop():
- Move
10fromq1toq2:q1 = [20, 30],q2 = [10] - Move
20fromq1toq2:q1 = [30],q2 = [10, 20] q1now has only30. Dequeue30fromq1. Return30.q1 = [],q2 = [10, 20]- Swap
q1andq2:q1 = [10, 20],q2 = []Stack conceptually: [10, 20] (20 on top)
from collections import deque
class StackTwoQueuesPushO1:
"""
Implements a Stack using two queues where push is O(1) and pop is O(N).
"""
def __init__(self):
self.q1 = deque() # Main queue
self.q2 = deque() # Helper queue
def push(self, x: int) -> None:
"""Adds an element to the top of the stack."""
self.q1.append(x) # O(1)
def pop(self) -> int:
"""Removes and returns the element from the top of the stack."""
if self.is_empty():
raise IndexError("Stack is empty")
# Move all elements except the last one from q1 to q2
while len(self.q1) > 1:
self.q2.append(self.q1.popleft())
# The last element in q1 is the one to pop
popped_element = self.q1.popleft() # O(1)
# Swap q1 and q2 so q1 is always the main queue
self.q1, self.q2 = self.q2, self.q1 # O(1) operation on deque references
return popped_element
def top(self) -> int:
"""Returns the element at the top of the stack without removing it."""
if self.is_empty():
raise IndexError("Stack is empty")
# Similar to pop, but put the element back
# Move all elements except the last one to q2
while len(self.q1) > 1:
self.q2.append(self.q1.popleft())
top_element = self.q1[0] # Peek at the first element (which is the last pushed)
# Move the top element to q2 as well (so q1 becomes empty)
self.q2.append(self.q1.popleft())
# Swap q1 and q2. Now q1 is the main queue with all elements.
self.q1, self.q2 = self.q2, self.q1
return top_element
def is_empty(self) -> bool:
"""Checks if the stack is empty."""
return len(self.q1) == 0
def size(self) -> int:
"""Returns the number of elements in the stack."""
return len(self.q1)
# --- Usage Example for StackTwoQueuesPushO1 ---
print("--- Approach 1: Two Queues - O(1) Push, O(N) Pop ---")
my_stack = StackTwoQueuesPushO1()
print(f"Is empty initially? {my_stack.is_empty()}") # Expected: True
my_stack.push(10)
my_stack.push(20)
my_stack.push(30)
print(f"Pushed 10, 20, 30. Current size: {my_stack.size()}") # Expected: 3
print(f"Top element: {my_stack.top()}") # Expected: 30
print(f"Popped: {my_stack.pop()}") # Expected: 30
print(f"Top element after pop: {my_stack.top()}") # Expected: 20
my_stack.push(40)
print(f"Pushed 40. Top element: {my_stack.top()}") # Expected: 40
print(f"Popped: {my_stack.pop()}") # Expected: 40
print(f"Popped: {my_stack.pop()}") # Expected: 20
print(f"Current size: {my_stack.size()}") # Expected: 1
print(f"Is empty now? {my_stack.is_empty()}") # Expected: False
print(f"Popped: {my_stack.pop()}") # Expected: 10
print(f"Is empty finally? {my_stack.is_empty()}") # Expected: True
try:
my_stack.pop()
except IndexError as e:
print(f"Error when popping from empty stack: {e}") # Expected: Stack is empty--- Approach 1: Two Queues - O(1) Push, O(N) Pop ---
Is empty initially? True
Pushed 10, 20, 30. Current size: 3
Top element: 30
Popped: 30
Top element after pop: 20
Pushed 40. Top element: 40
Popped: 40
Popped: 20
Current size: 1
Is empty now? False
Popped: 10
Is empty finally? True
Error when popping from empty stack: Stack is emptyComplexity Analysis (Approach 1):
- Time Complexity:
push(): O(1) - Just anappendoperation.pop(): O(N) - We dequeue N-1 elements and enqueue them into the second queue.top(): O(N) - Similar to pop, we move N elements.is_empty(): O(1)size(): O(1)
- Space Complexity: O(N) - We store all N elements across the two queues.
Approach 2: Two Queues - O(N) Push, O(1) Pop
This approach flips the performance characteristics: push becomes O(N), but pop and top become O(1). This is often preferred in scenarios where pop operations are far more frequent than push operations.
The Idea:
The key here is to ensure that whenever a new element x is pushed, it immediately becomes the first element in our main queue (q1), effectively making it the next element to be popped.
push(x):- Add the new element
xtoq2(helper queue). - Move all elements from
q1toq2. After this,q2containsxfollowed by all previously existing elements fromq1in their original order. - Swap
q1andq2. Nowq1containsxat its front, followed by the rest of the elements in the correct LIFO order.
- Add the new element
pop(): Simplypopleft()fromq1. Sinceq1is always arranged such that its front is the stack’s top, this is O(1).top(): Simply peek at the front element ofq1(q1[0]). This is also O(1).
Let’s trace an example:
Stack: []
push(10):q2 = [10]q1is empty, nothing to move.- Swap
q1,q2:q1 = [10],q2 = []Stack conceptually: [10] (10 on top)
push(20):q2 = [20]- Move
10fromq1toq2:q1 = [],q2 = [20, 10] - Swap
q1,q2:q1 = [20, 10],q2 = []Stack conceptually: [10, 20] (20 on top)
push(30):q2 = [30]- Move
20,10fromq1toq2:q1 = [],q2 = [30, 20, 10] - Swap
q1,q2:q1 = [30, 20, 10],q2 = []Stack conceptually: [10, 20, 30] (30 on top)
Now, pop():
q1.popleft()-> returns30.q1 = [20, 10],q2 = []Stack conceptually: [10, 20] (20 on top)
from collections import deque
class StackTwoQueuesPopO1:
"""
Implements a Stack using two queues where push is O(N) and pop is O(1).
"""
def __init__(self):
self.q1 = deque() # The main queue, always holding elements in LIFO order
self.q2 = deque() # The helper queue
def push(self, x: int) -> None:
"""Adds an element to the top of the stack."""
# 1. Add the new element to q2
self.q2.append(x) # O(1)
# 2. Move all elements from q1 to q2.
# After this, q2 has [new_element, old_element_1, old_element_2, ...]
while self.q1:
self.q2.append(self.q1.popleft()) # N dequeues and N enqueues
# 3. Swap q1 and q2. Now q1 is the primary queue with the new element at its front.
self.q1, self.q2 = self.q2, self.q1 # O(1)
# Total for push: O(N)
def pop(self) -> int:
"""Removes and returns the element from the top of the stack."""
if self.is_empty():
raise IndexError("Stack is empty")
return self.q1.popleft() # O(1) operation
def top(self) -> int:
"""Returns the element at the top of the stack without removing it."""
if self.is_empty():
raise IndexError("Stack is empty")
return self.q1[0] # O(1) - Peek at the first element (which is the top of the stack)
def is_empty(self) -> bool:
"""Checks if the stack is empty."""
return len(self.q1) == 0
def size(self) -> int:
"""Returns the number of elements in the stack."""
return len(self.q1)
# --- Usage Example for StackTwoQueuesPopO1 ---
print("\n--- Approach 2: Two Queues - O(N) Push, O(1) Pop ---")
my_stack_optimized = StackTwoQueuesPopO1()
print(f"Is empty initially? {my_stack_optimized.is_empty()}") # Expected: True
my_stack_optimized.push(10)
my_stack_optimized.push(20)
my_stack_optimized.push(30)
print(f"Pushed 10, 20, 30. Current size: {my_stack_optimized.size()}") # Expected: 3
print(f"Top element: {my_stack_optimized.top()}") # Expected: 30
print(f"Popped: {my_stack_optimized.pop()}") # Expected: 30
print(f"Top element after pop: {my_stack_optimized.top()}") # Expected: 20
my_stack_optimized.push(40)
print(f"Pushed 40. Top element: {my_stack_optimized.top()}") # Expected: 40
print(f"Popped: {my_stack_optimized.pop()}") # Expected: 40
print(f"Popped: {my_stack_optimized.pop()}") # Expected: 20
print(f"Current size: {my_stack_optimized.size()}") # Expected: 1
print(f"Is empty now? {my_stack_optimized.is_empty()}") # Expected: False
print(f"Popped: {my_stack_optimized.pop()}") # Expected: 10
print(f"Is empty finally? {my_stack_optimized.is_empty()}") # Expected: True
try:
my_stack_optimized.top()
except IndexError as e:
print(f"Error when peeking from empty stack: {e}") # Expected: Stack is empty--- Approach 2: Two Queues - O(N) Push, O(1) Pop ---
Is empty initially? True
Pushed 10, 20, 30. Current size: 3
Top element: 30
Popped: 30
Top element after pop: 20
Pushed 40. Top element: 40
Popped: 40
Popped: 20
Current size: 1
Is empty now? False
Popped: 10
Is empty finally? True
Error when peeking from empty stack: Stack is emptyComplexity Analysis (Approach 2):
- Time Complexity:
push(): O(N) - We dequeue and enqueue N elements.pop(): O(1) - Just apopleftoperation.top(): O(1) - Just an index lookup.is_empty(): O(1)size(): O(1)
- Space Complexity: O(N) - We store all N elements across the two queues.
Approach 3: One Queue - O(N) Push, O(1) Pop
This is a clever optimization of Approach 2. Instead of using a second explicit queue (q2) for intermediate storage and then swapping, we can achieve the same “rotation” effect using only one queue by moving elements from its front to its back.
The Idea:
When you push(x), you add x to the back of the queue. Then, to make x the new “front” (and thus the top of the stack), you dequeue all the other elements that were previously in the queue and enqueue them back to the end. This effectively rotates the queue, placing x at the very front.
push(x):- Add
xto the back of the queue (q.append(x)). - Rotate the queue: dequeue
N-1elements from the front and enqueue them at the back. This movesxto the front.
- Add
pop(): Simplypopleft()from the queue.top(): Simply peek at the front element (q[0]).
Let’s trace an example:
Stack: []
push(10):q = [10]- Queue size is 1, so
N-1is 0. No rotation needed. Stack conceptually: [10] (10 on top)
push(20):q = [10, 20]- Queue size is 2. Rotate 1 element (N-1). Dequeue
10, enqueue10.qbecomes[20, 10]Stack conceptually: [10, 20] (20 on top)
push(30):q = [20, 10, 30]- Queue size is 3. Rotate 2 elements (N-1).
- Dequeue
20, enqueue20:q = [10, 30, 20] - Dequeue
10, enqueue10:q = [30, 20, 10]Stack conceptually: [10, 20, 30] (30 on top)
- Dequeue
Now, pop():
q.popleft()-> returns30.q = [20, 10]Stack conceptually: [10, 20] (20 on top)
from collections import deque
class StackOneQueue:
"""
Implements a Stack using a single queue where push is O(N) and pop is O(1).
This is an optimized version of Approach 2.
"""
def __init__(self):
self.q = deque()
def push(self, x: int) -> None:
"""Adds an element to the top of the stack."""
self.q.append(x) # Add new element to the back (right)
# Rotate the queue: move all elements *except the new one* from front to back.
# This makes the new element (x) the first element in the queue,
# ensuring LIFO behavior for pop/top.
# Note: We iterate len(self.q) - 1 times because the new element is already in q.
# If the queue was empty before this push, len(self.q) is 1, so range(0) means no rotation.
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft()) # Dequeue from front, enqueue to back
# Total for push: O(N)
def pop(self) -> int:
"""Removes and returns the element from the top of the stack."""
if self.is_empty():
raise IndexError("Stack is empty")
return self.q.popleft() # O(1) - This is now the top of the stack
def top(self) -> int:
"""Returns the element at the top of the stack without removing it."""
if self.is_empty():
raise IndexError("Stack is empty")
return self.q[0] # O(1) - Peek at the top element
def is_empty(self) -> bool:
"""Checks if the stack is empty."""
return len(self.q) == 0
def size() -> int:
"""Returns the number of elements in the stack."""
return len(self.q)
# --- Usage Example for StackOneQueue ---
print("\n--- Approach 3: One Queue - O(N) Push, O(1) Pop ---")
my_stack_one_q = StackOneQueue()
print(f"Is empty initially? {my_stack_one_q.is_empty()}") # Expected: True
my_stack_one_q.push(10)
my_stack_one_q.push(20)
my_stack_one_q.push(30)
print(f"Pushed 10, 20, 30. Current size: {my_stack_one_q.size()}") # Expected: 3
print(f"Top element: {my_stack_one_q.top()}") # Expected: 30
print(f"Popped: {my_stack_one_q.pop()}") # Expected: 30
print(f"Top element after pop: {my_stack_one_q.top()}") # Expected: 20
my_stack_one_q.push(40)
print(f"Pushed 40. Top element: {my_stack_one_q.top()}") # Expected: 40
print(f"Popped: {my_stack_one_q.pop()}") # Expected: 40
print(f"Popped: {my_stack_one_q.pop()}") # Expected: 20
print(f"Current size: {my_stack_one_q.size()}") # Expected: 1
print(f"Is empty now? {my_stack_one_q.is_empty()}") # Expected: False
print(f"Popped: {my_stack_one_q.pop()}") # Expected: 10
print(f"Is empty finally? {my_stack_one_q.is_empty()}") # Expected: True
try:
my_stack_one_q.pop()
except IndexError as e:
print(f"Error when popping from empty stack: {e}") # Expected: Stack is empty--- Approach 3: One Queue - O(N) Push, O(1) Pop ---
Is empty initially? True
Pushed 10, 20, 30. Current size: 3
Top element: 30
Popped: 30
Top element after pop: 20
Pushed 40. Top element: 40
Popped: 40
Popped: 20
Current size: 1
Is empty now? False
Popped: 10
Is empty finally? True
Error when popping from empty stack: Stack is emptyComplexity Analysis (Approach 3):
- Time Complexity:
push(): O(N) - We perform N dequeues and N enqueues.pop(): O(1) - Just apopleftoperation.top(): O(1) - Just an index lookup.is_empty(): O(1)size(): O(1)
- Space Complexity: O(N) - We store all N elements in a single queue.
Comparison and When to Use Which Approach
Let’s summarize the time complexities for each core operation:
| Operation | Stack (Array/List) | Approach 1 (2 Queues, O(1) Push) | Approach 2 (2 Queues, O(1) Pop) | Approach 3 (1 Queue, O(1) Pop) |
|---|---|---|---|---|
push(x) |
O(1) (amortized) | O(1) | O(N) | O(N) |
pop() |
O(1) | O(N) | O(1) | O(1) |
top() |
O(1) | O(N) | O(1) | O(1) |
is_empty() |
O(1) | O(1) | O(1) | O(1) |
size() |
O(1) | O(1) | O(1) | O(1) |
| Space | O(N) | O(N) | O(N) | O(N) |
Which one to choose?
- For production code where you need a Stack: Always use your language’s native stack implementation (e.g., Python’s
listwithappendandpop, orcollections.deque). These will always be more efficient and idiomatic. - For interview questions or conceptual understanding:
- If the interviewer emphasizes
pushefficiency, Approach 1 is your answer. - If
pop(andtop) efficiency is critical, or the interviewer asks for the most common/optimized solution, Approaches 2 or 3 are better. Approach 3 is particularly elegant due to using only one queue. - Note: All these approaches have at least one O(N) operation for
pushorpop. A true stack typically has O(1) for both. The “Stack Using Queues” problem is about demonstrating understanding of transformations, not achieving superior performance over a native stack.
- If the interviewer emphasizes
Conclusion
Implementing a Stack using Queues is a fantastic exercise that reinforces your understanding of fundamental data structures and their operational differences. While not a typical production scenario, it hones your problem-solving skills and provides valuable insights into how abstract data types can be realized through various underlying structures.
By exploring the O(1) push vs. O(1) pop trade-offs, and the clever single-queue rotation, we gain a deeper appreciation for algorithmic design and complexity analysis. Keep experimenting and building these foundational blocks – they’re the bedrock of robust software.
Last updated on