A stack is a fundamental data structure that follows the Last-In, First-Out (LIFO) principle: the last element added is the first one removed. While you can implement a stack using a plain Python list, Python's collections.deque is specifically optimized for fast appends and removals from both ends, making it an excellent choice for stack implementations.
This guide covers both using the built-in collections.deque directly and building a custom stack class with a manually implemented deque.
Why Use deque Instead of a List?
Python lists support append() and pop() for stack operations, but they have a drawback: when the internal array needs to be resized, these operations can take O(n) time. A deque (double-ended queue) uses a doubly-linked list internally, guaranteeing O(1) time for both append and pop operations at either end.
| Operation | List | Deque |
|---|---|---|
append() (push) |
O(1) amortized | O(1) |
pop() (from end) |
O(1) amortized | O(1) |
pop(0) (from front) |
O(n) | O(1) |
| Memory reallocation | Occasional | Never |
Method 1: Using collections.deque Directly
The simplest approach is to use collections.deque as a stack with append() for push and pop() for pop:
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.append(4)
print("Stack after pushes:", list(stack))
stack.append(5)
print("After push(5):", list(stack))
removed = stack.pop()
print(f"Popped: {removed}")
print("After pop:", list(stack))
top = stack[-1]
print(f"Top element: {top}")
print(f"Is empty: {len(stack) == 0}")
print(f"Size: {len(stack)}")Output:
Stack after pushes: [1, 2, 4]
After push(5): [1, 2, 4, 5]
Popped: 5
After pop: [1, 2, 4]
Top element: 4
Is empty: False
Size: 3Method 2: Stack Class Wrapping collections.deque
For a cleaner interface with proper stack terminology, wrap deque in a class:
from collections import deque
class Stack:
"""Stack implementation using collections.deque."""
def __init__(self):
self._container = deque()
def push(self, item):
"""Add an item to the top of the stack."""
self._container.append(item)
def pop(self):
"""Remove and return the top item. Raises IndexError if empty."""
if self.is_empty():
raise IndexError("Pop from an empty stack")
return self._container.pop()
def top(self):
"""Return the top item without removing it."""
if self.is_empty():
raise IndexError("Top from an empty stack")
return self._container[-1]
def is_empty(self):
"""Return True if the stack is empty."""
return len(self._container) == 0
def size(self):
"""Return the number of items in the stack."""
return len(self._container)
def __repr__(self):
return f"Stack({list(self._container)})"
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(4)
print(stack)
stack.push(5)
print(f"After push(5): {stack}")
removed = stack.pop()
print(f"Popped: {removed}")
print(f"After pop: {stack}")
print(f"Top: {stack.top()}")
print(f"Size: {stack.size()}")
print(f"Is empty: {stack.is_empty()}")Output:
Stack([1, 2, 4])
After push(5): Stack([1, 2, 4, 5])
Popped: 5
After pop: Stack([1, 2, 4])
Top: 4
Size: 3
Is empty: FalseMethod 3: Custom Deque Implementation with a Doubly-Linked List
For educational purposes or environments where collections.deque is not available, here is a stack built on top of a custom doubly-linked list deque:
class Node:
"""A node in a doubly-linked list."""
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class Deque:
"""Doubly-linked list implementation of a deque."""
def __init__(self):
self.head = None
self.tail = None
self._size = 0
def is_empty(self):
return self._size == 0
def append(self, value):
"""Add to the end (tail)."""
new_node = Node(value)
if self.is_empty():
self.head = self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self._size += 1
def pop_last(self):
"""Remove and return the last element."""
if self.is_empty():
raise IndexError("Pop from empty deque")
value = self.tail.value
if self.head == self.tail:
self.head = self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
self._size -= 1
return value
def peek_last(self):
"""Return the last element without removing."""
if self.is_empty():
raise IndexError("Peek from empty deque")
return self.tail.value
def size(self):
return self._size
def display(self):
elements = []
current = self.head
while current is not None:
elements.append(str(current.value))
current = current.next
return ' -> '.join(elements) if elements else '(empty)'
class Stack:
"""Stack implemented using a custom Deque."""
def __init__(self):
self._deque = Deque()
def push(self, item):
self._deque.append(item)
def pop(self):
return self._deque.pop_last()
def top(self):
return self._deque.peek_last()
def is_empty(self):
return self._deque.is_empty()
def size(self):
return self._deque.size()
def display(self):
print(f"Stack (bottom to top): {self._deque.display()}")
stack = Stack()
stack.push(7)
stack.push(8)
stack.push(9)
stack.display()
popped = stack.pop()
print(f"Popped: {popped}")
stack.display()
print(f"Top: {stack.top()}")
print(f"Size: {stack.size()}")Output:
Stack (bottom to top): 7 -> 8 -> 9
Popped: 9
Stack (bottom to top): 7 -> 8
Top: 8
Size: 2Common Mistake: Popping from an Empty Stack
Calling pop() on an empty stack without checking first causes an error:
from collections import deque
stack = deque()
try:
stack.pop()
except IndexError as e:
print(f"Error: {e}")Output:
Error: pop from an empty dequeThe correct approach: always check before popping, or use the wrapper class that provides a clear error message:
from collections import deque
stack = deque()
if stack:
value = stack.pop()
else:
print("Stack is empty, nothing to pop")Output:
Stack is empty, nothing to popStack Operations Summary
| Operation | Method (deque) | Method (class) | Time Complexity |
|---|---|---|---|
| Push | deque.append(item) |
stack.push(item) |
O(1) |
| Pop | deque.pop() |
stack.pop() |
O(1) |
| Peek/Top | deque[-1] |
stack.top() |
O(1) |
| Is Empty | len(deque) == 0 |
stack.is_empty() |
O(1) |
| Size | len(deque) |
stack.size() |
O(1) |
Which Approach to Use?
| Approach | Best For |
|---|---|
collections.deque directly |
Quick scripts, simple use cases |
Wrapper class around deque |
Production code needing clear stack semantics and error handling |
| Custom linked-list deque | Learning data structures, interview practice, or restricted environments |
For production Python code, wrapping collections.deque in a Stack class (Method 2) gives you the best combination of performance, clarity, and safety. The custom linked-list implementation (Method 3) is valuable for understanding how deques work internally but is not necessary for practical applications.