Python Stacks and Queues
Introduction
When organizing data in your programs, you'll often need specialized containers that handle data in specific ways. Two of the most fundamental data structures in computer science are stacks and queues. These structures are particularly important because they serve as building blocks for more complex algorithms and are used extensively in software development.
In this tutorial, we'll explore how to implement and use stacks and queues in Python. We'll cover their core concepts, implementation options, and real-world applications to give you a solid understanding of these essential data structures.
What Are Stacks?
A stack is a linear data structure that follows the LIFO principle - Last In, First Out. Think of a stack of plates - you can only take the top plate (the last one placed), and you can only add a new plate to the top of the stack.
The two primary operations on a stack are:
- Push: Add an item to the top of the stack
- Pop: Remove the item from the top of the stack
Implementing a Stack in Python
Python offers several ways to implement stacks:
Using Lists
The simplest way to implement a stack in Python is using a list:
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
return None
def size(self):
return len(self.items)
Let's see how to use this stack implementation:
# Create a new stack
stack = Stack()
# Add items to the stack
stack.push('a')
stack.push('b')
stack.push('c')
print("Stack size:", stack.size()) # Output: Stack size: 3
print("Top item:", stack.peek()) # Output: Top item: c
# Remove items
popped_item = stack.pop()
print("Popped item:", popped_item) # Output: Popped item: c
print("New top item:", stack.peek()) # Output: New top item: b
Using collections.deque
For better performance, especially when dealing with large stacks, you can use collections.deque:
from collections import deque
class Stack:
def __init__(self):
self.items = deque()
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
return None
def size(self):
return len(self.items)
Stack Applications
Stacks are used in numerous algorithms and applications:
- Expression Evaluation: Stacks are used to evaluate expressions like checking for balanced parentheses.
- Function Call Management: Programming languages use stacks to manage function calls (the call stack).
- Undo Mechanisms: Applications like text editors use stacks to implement undo functionality.
- Browser History: The back button in web browsers uses a stack to keep track of visited pages.
Example: Checking Balanced Parentheses
Here's a practical example of using a stack to check if parentheses in an expression are balanced:
def are_brackets_balanced(expression):
stack = []
# Dictionary to store the mapping of closing to opening brackets
brackets_map = {')': '(', '}': '{', ']': '['}
# Iterate through each character in the expression
for char in expression:
# If it's an opening bracket, push to stack
if char in '({[':
stack.append(char)
# If it's a closing bracket
elif char in ')}]':
# If stack is empty or the top doesn't match, it's not balanced
if not stack or stack.pop() != brackets_map[char]:
return False
# If the stack is empty, all brackets were matched
return len(stack) == 0
# Test cases
print(are_brackets_balanced("(a+b)")) # Output: True
print(are_brackets_balanced("{[a+b]*(c-d)}")) # Output: True
print(are_brackets_balanced("(a+b")) # Output: False
print(are_brackets_balanced("(a+b)]")) # Output: False
What Are Queues?
A queue is a linear data structure that follows the FIFO principle - First In, First Out. Think of people waiting in a line - the first person to arrive is the first person to be served.
The two primary operations on a queue are:
- Enqueue: Add an item to the end of the queue
- Dequeue: Remove the item from the front of the queue
Implementing a Queue in Python
Using Lists
We can implement a basic queue using Python lists, but it's not efficient for large queues:
class Queue:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.pop(0) # Inefficient for large queues
return None
def peek(self):
if not self.is_empty():
return self.items[0]
return None
def size(self):
return len(self.items)
Let's see how to use this queue:
# Create a new queue
queue = Queue()
# Add items to the queue
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
print("Queue size:", queue.size()) # Output: Queue size: 3
print("Front item:", queue.peek()) # Output: Front item: a
# Remove items
dequeued_item = queue.dequeue()
print("Dequeued item:", dequeued_item) # Output: Dequeued item: a
print("New front item:", queue.peek()) # Output: New front item: b
Using collections.deque
For better performance, especially for large queues, use collections.deque:
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def is_empty(self):
return len(self.items) == 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.popleft() # O(1) operation
return None
def peek(self):
if not self.is_empty():
return self.items[0]
return None
def size(self):
return len(self.items)
Using queue.Queue
Python's standard library offers a thread-safe Queue implementation:
from queue import Queue
# Create a queue
q = Queue()
# Add items
q.put('a')
q.put('b')
q.put('c')
# Get size
print("Queue size:", q.qsize()) # Output: Queue size: 3
# Remove items
print("Dequeued item:", q.get()) # Output: Dequeued item: a
print("Queue empty?", q.empty()) # Output: Queue empty? False
Queue Applications
Queues are used in various algorithms and real-world applications:
- Job Scheduling: Operating systems use queues for CPU scheduling.
- Breadth-First Search: Graph algorithms use queues for traversal.
- Print Spooling: Print jobs are processed in the order they are received.
- Message Buffers: Handling messages between applications.
Example: Level Order Traversal of a Binary Tree
Here's a practical example of using a queue for level-order traversal of a binary tree:
from collections import deque
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def level_order_traversal(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
current = queue.popleft()
result.append(current.value)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return result
# Create a sample tree
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
print(level_order_traversal(root)) # Output: [1, 2, 3, 4, 5, 6]
Specialized Queue Types
Priority Queue
A priority queue is a special queue where elements have associated priorities. Elements with higher priorities are served before those with lower priorities.
Python provides a built-in module for implementing priority queues:
import heapq
# Create a priority queue
priority_queue = []
# Add items with priorities (priority, item)
heapq.heappush(priority_queue, (3, "Medium priority"))
heapq.heappush(priority_queue, (1, "High priority"))
heapq.heappush(priority_queue, (5, "Low priority"))
# Remove items (lowest value = highest priority)
while priority_queue:
print(heapq.heappop(priority_queue))
# Output:
# (1, 'High priority')
# (3, 'Medium priority')
# (5, 'Low priority')
Double-ended Queue (Deque)
A deque allows insertion and removal from both ends:
from collections import deque
# Create a deque
d = deque()
# Add items to both ends
d.append("right")
d.appendleft("left")
print(d) # Output: deque(['left', 'right'])
# Remove items from both ends
print(d.pop()) # Output: right
print(d.popleft()) # Output: left
Performance Considerations
Understanding the time complexity of stack and queue operations is important:
| Data Structure | Implementation | Push/Enqueue | Pop/Dequeue | Peek |
|---|---|---|---|---|
| Stack | List | O(1) | O(1) | O(1) |
| Stack | collections.deque | O(1) | O(1) | O(1) |
| Queue | List | O(1) | O(n) | O(1) |
| Queue | collections.deque | O(1) | O(1) | O(1) |
| Queue | queue.Queue | O(1) | O(1) | O(1) |
For efficient queue implementation, always prefer collections.deque over lists.
Summary
Stacks and queues are fundamental data structures that serve different purposes:
- Stacks follow the Last-In-First-Out (LIFO) principle and are ideal for scenarios where you need to process items in reverse order of arrival.
- Queues follow the First-In-First-Out (FIFO) principle and are perfect for processing items in the order they arrive.
Python offers multiple ways to implement these structures, from simple list-based implementations to more specialized and efficient solutions like collections.deque.
Understanding when and how to use stacks and queues is crucial for solving many programming problems efficiently, particularly those involving ordered processing, traversals, and scheduling.
Practice Exercises
To solidify your understanding, try these exercises:
- Implement a stack that can keep track of its minimum element in O(1) time.
- Create a queue using two stacks.
- Implement a circular queue with a fixed size.
- Use a stack to reverse a string.
- Implement a breadth-first search algorithm for a graph using a queue.
Additional Resources
If you spot any mistakes on this website, please let me know at [email protected]. I’d greatly appreciate your feedback! :)