Just For Fun 08: Stacks and Queues
Exploring LIFO and FIFO Data Structures with Python Lists
By the end of this lesson, you will be able to:
Introduction
Stacks and queues are two of the most fundamental data structures in computer science. A stack follows Last-In-First-Out (LIFO) order – think of a stack of plates, where you add and remove from the top. A queue follows First-In-First-Out (FIFO) order – think of a line at a coffee shop, where the first person in line is served first.
Key Concepts
💡 Concept 1: Stack (LIFO)
A stack supports two main operations: push (add to the top) and pop (remove from the top). Python lists make great stacks using append() and pop().
Example:
# stack = []
# stack.append(1) -> [1]
# stack.append(2) -> [1, 2]
# stack.pop() -> returns 2, stack is now [1]💡 Concept 2: Queue (FIFO)
A queue supports enqueue (add to the back) and dequeue (remove from the front). While a list can act as a queue, collections.deque is much more efficient for removing from the front.
Example:
# from collections import deque
# queue = deque()
# queue.append("A") -> A is in line
# queue.append("B") -> A, B are in line
# queue.popleft() -> returns "A", B remainsInteractive Examples
Example 1: A Simple Stack
What this code does: This code uses a plain Python list as a stack, pushing several values on and then popping them off one at a time, demonstrating the Last-In-First-Out order.
Example Code:
stack = []
# Push some values
for value in [10, 20, 30, 40]:
stack.append(value)
print(f"Pushed {value}, stack is now: {stack}")
print("\nNow popping everything off:")
while stack:
value = stack.pop()
print(f"Popped {value}, stack is now: {stack}")Example 2: Balanced Parentheses Checker
What this code does: This is a classic use of a stack: to check whether parentheses are balanced, push every opening bracket onto a stack, and pop it off when you see the matching closing bracket. If the stack ends up empty, the brackets are balanced.
Example Code:
def is_balanced(expression):
"""Return True if all brackets in expression are balanced"""
matching = {")": "(", "]": "[", "}": "{"}
stack = []
for char in expression:
if char in "([{":
stack.append(char)
elif char in ")]}":
if not stack or stack.pop() != matching[char]:
return False
return not stack
tests = ["(a + b) * [c - d]", "([)]", "{[()]}", "(( )"]
for test in tests:
print(f"{test!r} -> balanced: {is_balanced(test)}")Example 3: A Queue with collections.deque
What this code does: This simulates a print queue: documents are added to the back of the line and printed (removed) from the front, one at a time, showing the First-In-First-Out order.
Example Code:
from collections import deque
print_queue = deque()
# Enqueue some print jobs
for document in ["essay.docx", "photo.png", "resume.pdf", "notes.txt"]:
print_queue.append(document)
print(f"Added to queue: {document}")
print("\nNow printing documents in order:")
while print_queue:
document = print_queue.popleft()
print(f"Printing: {document}")Challenge Yourself
Challenge Tasks:
- Build a browser history simulator: use a stack to track pages visited, supporting a “back” operation
- Combine a stack and a queue to check if a word is a palindrome (reverse with a stack, compare with a queue)
- Add a “peek” function to look at the top of a stack (or front of a queue) without removing it
- Research question: Why is
collections.dequefaster than a plain list for queue operations?
Use any of the terminals above to experiment with these challenges!
Summary
In this lesson, you explored two essential data structures:
- Stacks (LIFO): Built with Python lists using
append()/pop(), used to check balanced parentheses - Queues (FIFO): Built with
collections.dequeusingappend()/popleft(), used to simulate a print queue - Real-world uses: Undo features, browser history, task scheduling, and more all rely on stacks and queues