Software Engineering • Module 5
Data Structures:
Fundamentals and Implementations
Lesson 2 | Prof. Afonso Brandão
Stacks and LIFO
Queues and FIFO
Real-World Systems
Maze Robot Activity
Why Data Structures Matter
They shape how information flows, is stored, and is consumed by software
  • Data structures are not abstract theory only.
  • They encode access order, decision strategy, and system behavior.
  • Choosing the wrong structure creates unnecessary complexity and runtime cost.
In practice, stacks and queues appear whenever software needs ordering, coordination, or controlled processing.
Stack: LIFO
Last In, First Out

Main Operations

  • push adds to the top
  • pop removes the top element
  • peek inspects the top element

Typical Mental Model

  • Undo history
  • Call stack
  • Backtracking
stack = [] stack.append("A") # push stack.append("B") top = stack.pop() # "B" peek = stack[-1] # "A"
Queue: FIFO
First In, First Out

Main Operations

  • enqueue adds to the end
  • dequeue removes from the front
  • front inspects the next element

Typical Mental Model

  • Customer service lines
  • Task scheduling
  • Message processing
from collections import deque queue = deque() queue.append("task-1") # enqueue queue.append("task-2") item = queue.popleft() # "task-1"
Stacks vs Queues
The difference is not storage, but ordering strategy
Structure Rule Best For Typical Examples
Stack LIFO Backtracking, nested execution, undo Browser history, recursion, maze exploration
Queue FIFO Sequential processing, fairness, scheduling Message brokers, print queues, event handling
Real-World Use Cases for Stacks
Stacks are ideal when the most recent decision must be revisited first
  • Undo and redo in editors.
  • Navigation history in browsers.
  • Recursive function calls managed by the runtime.
  • Backtracking in games, parsers, and path exploration.
In a maze, a stack lets the robot remember the last safe movement so it can return when a path reaches a dead end.
Real-World Use Cases for Queues
Queues are ideal when processing order must respect arrival order
  • API request scheduling.
  • Job workers and background processing.
  • Customer support tickets and print jobs.
  • Sequential event consumption in distributed systems.
In the robot activity, a queue ensures collected keys are used in the same order they were discovered.
Events and Queues in Modern Software
Many software systems are built around event-driven processing

What Happens

  • A producer emits an event
  • The event enters a queue or topic
  • Consumers process events in order or by partition

Why It Matters

  • Decouples systems
  • Absorbs load peaks
  • Enables asynchronous workflows
Examples of Queue-Based Tools
The same FIFO idea appears in infrastructure and applications
  • RabbitMQ for work queues and routing.
  • Kafka for event streams and ordered processing by partition.
  • AWS SQS for cloud queue processing.
  • Celery for background task execution in Python systems.
Queue-based tools are practical implementations of FIFO concepts used to coordinate distributed work.
Backtracking and Sequential Processing
Stacks and queues solve different flow-control problems

Use a Stack When

  • You need to return to a previous step
  • The latest path or choice should be reversed first
  • The algorithm explores depth before alternatives

Use a Queue When

  • Items must be processed fairly in order
  • You have pending work arriving over time
  • The algorithm explores breadth or scheduled order
Robot Maze Activity
The challenge combines LIFO backtracking and FIFO resource usage
The explorer robot must traverse a maze, collect keys, open locked doors, and reach the exit.
  • Use a stack to store movements and backtrack on dead ends.
  • Use a queue to manage collected keys in FIFO order.
  • Ensure the robot avoids blockages and explores efficient paths.
Graded Activity: Maze Robot
Applying Stacks and Queues

Context

An explorer robot has been sent to map a maze full of narrow passages, locked doors, and scattered keys. The robot's goal is to collect the necessary keys and reach the exit, avoiding dead ends and obstacles along the way.

The robot follows two fundamental rules:
1. If it needs to backtrack, it must follow the steps in reverse order → We use a stack (LIFO) to store movements.
2. If it picks up a key, it must be used in the order it was collected → We use a queue (FIFO) to manage the keys.

Your challenge is to implement the robot's movement logic, ensuring that it correctly explores the maze, collects and uses keys in the right order, and finds the exit.

Maze Rules

  1. The robot can move up, down, left, and right, as long as it doesn't hit a wall.
  2. Whenever it moves, the movement is stored on a stack, allowing it to backtrack if necessary.
  3. If it finds a key (K), the key is added to a queue.
  4. If it finds a locked door (D), it can only open it if it has at least one key in the queue, and the oldest key (FIFO) will be used.
  5. If it gets stuck with no way out, it must use the stack to backtrack and try another path.
  6. The robot only wins the game when it reaches the exit (E), ensuring all necessary doors were opened beforehand.

Maze Example

S → . → K → . → D → . → E
    ↓       ↑       ↓
    .   X   .   X   .
    ↓       ↑       ↓
    . → . → K → . → D

Legend:
- S = Robot's starting point
- E = Exit (final goal)
- K = Key (added to the queue when collected)
- D = Door (only opens if there is a key in the queue)
- X = Wall (impassable obstacle)
- . = Free path

Game Flow Example

  1. The robot moves from position S to the right and collects a key (K).
  2. It continues forward and finds a door (D).
  3. Since it has a key in the queue, the door is unlocked, and it moves on.
  4. It finds another door but does not have enough keys.
  5. It uses the stack to backtrack to a part of the maze where it can explore a new path and collect another key.
  6. Now, it returns to the door with the new key and continues to the exit.

Code Objective

You must implement the robot's movement logic using:
- A stack to store movements (allowing it to backtrack from dead ends).
- A queue to store collected keys and ensure doors are unlocked in the correct order.

The code should print each of the robot's movements and indicate when it collects a key, opens a door, or finds the exit.
The graded activity will be done in the classroom with pen and paper and will last for one hour.
Questions?
Next: Security in Web and Cloud Systems
🏠 Home 📖 Material
1 / 1