Building Stack & Queue Classes from Scratch
Reinforce your OOP skills while learning two fundamental data structures: Stack and Queue. By the end, you'll be able to add an UNDO feature to your shop system!
Connection: You already understand the Stack concept ("like dishes"). Today we'll learn the technical terminology and implement it as a class.
Quick questions to warm up:
Confidentiality, Integrity, Availability
Readability, Maintainability, Robustness
ValueError, KeyError, TypeError
KeyError
Let's review your implementation of the challenges from Lesson 3.
| Challenge | What to Look For |
|---|---|
| A: Error Handling | try/except for KeyError, friendly error messages |
| B: Case Insensitive | .title() or .lower() approach for input |
| C: Shopping Loop | while loop, exit condition, total tracking |
| D: Input Validation | Negative budget check, ValueError handling |
| E: Better Display | Formatted items, number selection option |
Transition: "Now let's add an UNDO button to your shop system - to do this, we need to learn about Stacks."
The last item added is the first one removed.
The first item added is the first one removed.
| Operation | Stack | Queue |
|---|---|---|
| Add item | push() | enqueue() |
| Remove item | pop() | dequeue() |
| View next item (without removing) | peek() | front() |
Memory trick: LIFO = "Last In, First Out" (Stack) | FIFO = "First In, First Out" (Queue)
Why not just use a Python list directly? Here's why OOP makes sense:
Hide the implementation details. Users of your Stack don't need to know it uses a list internally.
Prevent misuse. A Stack should only allow push/pop - not random access to the middle!
stack.push(item) is clearer than list.append(item) when you're thinking about stacks.
The class can handle edge cases (like popping from an empty stack) gracefully.
Connection to Lesson 2: Remember encapsulation? This is it in action - hiding the internal list and only exposing stack operations.
Blake codes while instructor guides. Let's build a complete Stack class.
class Stack:
def __init__(self):
self._items = [] # Private - encapsulation!
def push(self, item):
"""Add an item to the top of the stack."""
self._items.append(item)
def pop(self):
"""Remove and return the top item."""
if self.is_empty():
raise IndexError("Cannot pop from empty stack")
return self._items.pop()
def peek(self):
"""Return the top item without removing it."""
if self.is_empty():
raise IndexError("Cannot peek at empty stack")
return self._items[-1]
def is_empty(self):
"""Check if the stack is empty."""
return len(self._items) == 0
def size(self):
"""Return the number of items in the stack."""
return len(self._items)_items with underscore? - Private convention. Signals "don't access directly!"is_empty() method? - Clearer than checking len(stack._items) == 0# Create a stack
my_stack = Stack()
# Push some items
my_stack.push("A")
my_stack.push("B")
my_stack.push("C")
print(f"Size: {my_stack.size()}") # 3
print(f"Top item: {my_stack.peek()}") # C
# Pop items (LIFO order!)
print(my_stack.pop()) # C (last in)
print(my_stack.pop()) # B
print(my_stack.pop()) # A (first in, last out)
# This would raise IndexError:
# my_stack.pop() # Empty stack!Let's create an UndoStack that records actions and can undo them!
class UndoStack:
def __init__(self):
self._actions = []
def record_action(self, description, data):
"""Record an action that can be undone."""
self._actions.append({
'description': description,
'data': data
})
print(f"Recorded: {description}")
def undo(self):
"""Undo the last action. Returns the action data or None."""
if not self._actions:
print("Nothing to undo!")
return None
action = self._actions.pop()
print(f"Undoing: {action['description']}")
return action['data']
def can_undo(self):
"""Check if there are actions to undo."""
return len(self._actions) > 0
def show_history(self):
"""Display all recorded actions."""
if not self._actions:
print("No actions recorded")
return
print("Action history:")
for i, action in enumerate(self._actions, 1):
print(f" {i}. {action['description']}")# Demo: Recording and undoing purchases
undo_stack = UndoStack()
budget = 100
# Simulate purchases
def purchase(item, price):
global budget
budget -= price
undo_stack.record_action(
f"Purchased {item} for ${price}",
{'item': item, 'price': price}
)
print(f"Budget: ${budget}")
# Make some purchases
purchase("Apple", 1) # Budget: $99
purchase("Watch", 50) # Budget: $49
purchase("Toothpaste", 3) # Budget: $46
# Show what we can undo
undo_stack.show_history()
# Undo last purchase
action = undo_stack.undo() # Undoing: Purchased Toothpaste for $3
if action:
budget += action['price'] # Restore the money
print(f"Budget restored to: ${budget}") # $49A Queue follows FIFO - first in, first out. Here's what the structure looks like:
class Queue:
def __init__(self):
self._items = []
def enqueue(self, item):
"""Add an item to the back of the queue."""
self._items.append(item)
def dequeue(self):
"""Remove and return the front item."""
if self.is_empty():
raise IndexError("Cannot dequeue from empty queue")
return self._items.pop(0) # Remove from front!
def front(self):
"""Return the front item without removing it."""
if self.is_empty():
raise IndexError("Cannot peek at empty queue")
return self._items[0]
def is_empty(self):
return len(self._items) == 0
def size(self):
return len(self._items)# Order processing queue
order_queue = Queue()
# Orders come in
order_queue.enqueue("Order #101 - Pizza")
order_queue.enqueue("Order #102 - Burger")
order_queue.enqueue("Order #103 - Salad")
# Process orders (FIFO - first order gets processed first)
print(order_queue.dequeue()) # Order #101 - Pizza
print(order_queue.dequeue()) # Order #102 - Burger
# What's next?
print(f"Next order: {order_queue.front()}") # Order #103 - SaladKey Difference: Stack uses pop() (removes from end), Queue uses pop(0) (removes from front).
| Feature | Stack | Queue |
|---|---|---|
| Principle | LIFO (Last In, First Out) | FIFO (First In, First Out) |
| Add operation | push() | enqueue() |
| Remove operation | pop() | dequeue() |
| Analogy | Stack of dishes | Checkout line |
| Use case | Undo, browser history | Order processing, print queue |
Push A, B, C → Stack is [A, B, C] (C on top)
Pop → removes C → [A, B]
Pop → removes B → [A]
Answer: A is left
Enqueue A, B, C → Queue is [A, B, C] (A at front)
Dequeue → removes A → [B, C]
Dequeue → removes B → [C]
Answer: C is left
Pick 1-2 options to practice at home:
Add an undo feature to your shop system from Lesson 3:
Build a simple order management system:
Create a simple browser history using Stack:
visit(url) - push URL to history stackback() - pop and return to previous URLcurrent() - show current page (peek)Next lesson: We'll continue building on OOP concepts and explore more Year 12 topics.