Implement Queue Using Two Stacks in Python
Python class that implements a FIFO queue using two stacks, with enqueue, dequeue, peek, and emptiness checks.
Python code
40 linesclass QueueUsingStacks:
def __init__(self):
self.stack_in = []
self.stack_out = []
def enqueue(self, value):
self.stack_in.append(value)
def dequeue(self):
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
def peek(self):
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out[-1]
def is_empty(self):
return not self.stack_in and not self.stack_out
def display(self):
combined = self.stack_out[::-1] + self.stack_in
print("Queue contents (front to back):", combined)
if __name__ == "__main__":
q = QueueUsingStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.display()
print("Dequeued:", q.dequeue())
q.display()
q.enqueue(4)
print("Peek:", q.peek())
q.display()
print("Is empty:", q.is_empty())
Output
Queue contents (front to back): [1, 2, 3]
Dequeued: 1
Queue contents (front to back): [2, 3]
Peek: 2
Queue contents (front to back): [2, 3, 4]
Is empty: False
How it works
The queue uses two stacks: stack_in for new elements and stack_out for reversed order. When dequeue or peek is called and stack_out is empty, all elements from stack_in are popped and pushed onto stack_out, reversing their order so the oldest element is on top. This amortizes the cost of the reversal over multiple operations, giving O(1) average per operation. The display method reconstructs the queue by reversing stack_out (which holds elements in reverse order) and appending stack_in.
Common mistakes
- Forgetting to transfer elements when stack_out is empty during peek or dequeue
- Calling pop() on empty stack_out without checking
- Nut mixing up the order when displaying the queue
- Assuming the queue is not thread-safe in concurrent use
Variations
- Using collections.deque which provides O(1) append/pop from both ends, but this does not use two stacks
- Immediately reversing the entire stack after every enqueue for a simpler but less efficient implementation
Real-world use cases
- Simulating a FIFO buffer in systems where only stack primitives are available.
- Implementing a work queue in low‑level scheduling logic that relies on LIFO primitives.
- Designing algorithms that require queue behaviour without an explicit queue data structure.
Sponsored
More from Algorithms & data structures
- Binary Search for Ship Capacity in Python medium
- Binary Search on Answer in Python: Koko Eating Bananas medium
- Bucket Numbers into Histogram Bin Counts in Python easy
- Container With Most Water: Two-Pointer Solution in Python medium
- Count Smaller Elements to the Right in Python easy
- Depth First Search Traversal Order in Python easy
Keep learning
Related tutorials and quizzes for this topic.