Lesson Goal
Understand how stacks and queues organize data, compare LIFO and FIFO strategies, and apply these structures to real computational and software engineering problems.
1) Why Data Structures Matter
Data structures define how information is stored, accessed, and processed. In software engineering, they influence not only performance but also behavior. A queue does not simply store values; it encodes fairness and processing order. A stack does not simply hold elements; it encodes reversal, backtracking, and nested execution.
That is why choosing a data structure is also choosing a strategy for control flow.
2) Stacks and LIFO
A stack follows the LIFO rule: Last In, First Out. The most recently inserted element is the first one removed. This is useful when the latest action or decision should be revisited before older ones.
- push: add an item to the top
- pop: remove the top item
- peek: inspect the top item without removing it
stack = []
stack.append("A")
stack.append("B")
top = stack.pop() # "B"
peek = stack[-1] # "A"Typical use cases include undo history, recursive calls, expression parsing, and backtracking algorithms.
3) Queues and FIFO
A queue follows the FIFO rule: First In, First Out. The earliest inserted element is the first one removed. This is appropriate when processing order should follow arrival order.
- enqueue: add an item to the end
- dequeue: remove an item from the front
- front: inspect the next item to be processed
from collections import deque
queue = deque()
queue.append("task-1")
queue.append("task-2")
item = queue.popleft() # "task-1"Typical use cases include request scheduling, print queues, customer service systems, and message processing pipelines.
4) Comparison: Stack vs Queue
| Structure | Rule | Best For | Typical Example |
|---|---|---|---|
| Stack | LIFO | Backtracking, undo, nested execution | Browser history, recursive calls |
| Queue | FIFO | Fair scheduling, ordered processing | Job queues, request processing |
The key distinction is order. The same elements stored in a stack and a queue can lead to very different behaviors.
5) Real-World Cases
Stacks appear when software must revisit the most recent decision first. Queues appear when software must respect arrival order or process work fairly.
- Stacks: browser back button, undo in editors, call stacks, maze backtracking.
- Queues: message brokers, ticketing systems, print jobs, asynchronous task workers.
6) Events, Queues, and Software Systems
Modern systems frequently use event-driven architectures. In these systems, one component emits an event, a queue or topic stores that event, and one or more consumers process it later. This decouples systems and helps handle burst traffic.
- RabbitMQ: queue-based processing and routing.
- Kafka: event streams with ordered consumption by partition.
- AWS SQS: managed queue infrastructure in cloud systems.
- Celery: asynchronous background task processing in Python applications.
These tools are real-world embodiments of queue behavior, especially FIFO and controlled sequential processing.
7) Backtracking and Sequential Processing
Stacks and queues support different algorithmic strategies:
- Backtracking with stacks: explore a path, remember decisions, and return when blocked.
- Sequential processing with queues: preserve order and handle pending tasks fairly.
This distinction is central to the robot maze challenge, where the robot must both backtrack efficiently and manage keys in the order they were collected.
8) Graded Activity
In this activity, students will program an explorer robot that must traverse a maze, collecting keys and opening locked doors until reaching the exit. The robot uses a stack to store its movements, allowing it to backtrack when it encounters a dead end, and a queue to manage the collected keys, ensuring that doors are opened in the correct order (FIFO). The challenge is to implement the robot’s movement logic, ensuring that it explores efficient paths, avoids blockages, and correctly uses the data structures.
By the end of this activity, you are expected to be able to:
- Implement and use stacks (LIFO) and queues (FIFO) to solve computational problems.
- Develop algorithms that use stacks for backtracking and queues for sequential processing.
- Apply flow control strategies to navigate a maze efficiently.
- Write structured code to manage states and decisions at runtime.
Deadline: the activity must be submitted by the end of the class.
Google Colab: https://colab.research.google.com/drive/1y7lwATSS__ni2RO8ODqDkF33OlUvqxpq?usp=sharing