1 of 25

M4: Stacks and Queues in Real Systems

Controlling Order, Managing Flow

Prof. Justin David Pineda CISSP, CISM

2 of 25

On the Train exercise..

Stations List
Train Cars
Seats Per Car
Train Schedule/ Timetable
Passenger Demand Matrix (2d)

Reservations
Waiting list
Active trains
Event logs
Seat history (optional)

3 of 25

User POV

The passenger can:

view stations
choose origin and destination
view available trains
reserve a seat
receive seat number
cancel reservation
join waiting list if full

Likely structures involved:

station array
schedule array
car/seat arrays
reservation linked list
waiting list linked list

4 of 25

Admin POV

The admin can:

add/edit train schedules
monitor seat occupancy
add skip trains during peak hours
review passenger demand
manage waiting lists
cancel or modify reservations
check event logs
monitor synchronization of regular and skip trains

Likely structures involved:

schedule array
demand 2D array
active train linked list
event log linked list
reservation linked list

5 of 25

Motivation: Why Order Matters in Systems

How does your browser “go back”?
How do print jobs line up?
Why do systems process requests in order?

Analogy:

Stack = plates in a cafeteria

Queue = line at MRT/LRT

6 of 25

Learning Objectives

After this lesson, students should be able to:

Explain Stack (LIFO) and Queue (FIFO)
Implement both using arrays and linked lists
Analyze time complexity
Apply in real-world systems (OS, apps, networks)

7 of 25

What is a Stack?

Linear data structure
Follows LIFO (Last In, First Out)
Only one access point: TOP

Example:

Push → Add
Pop → Remove

8 of 25

Stack Operations

push() → insert element
pop() → remove element
peek() → view top element
isEmpty() / isFull()

9 of 25

Stack in C (Array Implementation)

10 of 25

Stack Visualization

Step-by-step:

Push 10 → Push 20 → Push 30

Pop → removes 30

11 of 25

Stack Applications

Undo/Redo (text editors)
Function calls (call stack)
Expression evaluation (postfix)

12 of 25

Stack Limitations

13 of 25

What is a Queue?

Linear data structure
Follows FIFO (First In, First Out)

Two ends:

Front (remove)
Rear (insert)

14 of 25

Queue Operations

enqueue() → insert
dequeue() → remove
peek() → view front

15 of 25

Queue in C (Array Implementation)

16 of 25

Visualization: Insert vs Array Shift

17 of 25

Circular Queue Concept

Singly Linked List
Doubly Linked List
Circular Linked List

18 of 25

Queue Applications

struct Node {

int data;

struct Node* prev;

struct Node* next;

};

19 of 25

Stack vs Queue Comparison

Feature	Stack	Queue
Order	LIFO	FIFO
Access	One end	Two ends
Use Case	Undo	Scheduling

20 of 25

Linked List Implementation Insight

Dynamic size
No overflow (until memory full)

Stack:

Insert/Delete at head

Queue:

Insert at tail, delete at head

21 of 25

Real-World System Mapping

OS:

Stack → function calls
Queue → process scheduling

Networking:

Queue → packet buffering

22 of 25

Key Takeaways

Stack = LIFO → last comes out first
Queue = FIFO → first comes out first
Both critical for system flow control
Choice depends on use case

23 of 25

Summary

Stacks and Queues manage order of execution
Widely used in systems, apps, and networks
Implementation affects performance

24 of 25

Stack or Queue?

Laundry Pile
MRT / LRT Line
Desk Papers / Work Tasks
Call Center Queue
Undo Feature in a Mobile App
Plate Serving at a Buffet
Browser Back Button
Emergency Task Handling

Elevator Emergency Stop Buttons
Fast Food Order Line
Browser Tabs (Recent Focus)
Traffic at Intersection
Customer Service Hotline
Airport Check-in Line
Printer Jobs in Office
Food Delivery Orders

25 of 25

Knowledge Check (Recitation)

Explain LIFO using a real-life example
What happens during stack overflow?
Difference between enqueue and push?
Why is queue used in CPU scheduling?
When would you choose stack over queue?

6. Give a real-life scenario where a queue would be unfair to use. Why?

7. In your daily work, when do you prioritize the latest task instead of the first task? What structure does this represent?

8. What problem does a circular queue solve compared to a normal queue? (Explain in simple terms)

9. Can a system use both stack and queue at the same time? Give a practical example.

10. If a system processes the most urgent tasks first, is it still a pure queue? Why or why not?

Knowledge Check – Answer Key

1. Explain LIFO using a real-life example

Answer:

LIFO means the last item added is the first one removed. A good example is a stack of plates where you take the top plate first. This shows that the most recent item is accessed first.

2. What happens during stack overflow?

Answer:

Stack overflow happens when you try to push an element into a full stack. Since there is no more space, the operation fails. This can cause errors or crashes in a program.

3. Difference between enqueue and push?

Answer:

Push is used in a stack and adds an element to the top. Enqueue is used in a queue and adds an element to the rear. They differ in structure and how elements are accessed.

4. Why is queue used in CPU scheduling?

Answer:

Queue ensures processes are handled in the order they arrive, which maintains fairness. It prevents starvation and ensures all processes get CPU time. This is important in multi-user systems.

5. When would you choose stack over queue?

Answer:

You choose a stack when you need to reverse actions or prioritize the most recent task. Examples include undo operations and function calls. It is useful when the latest activity matters most.

6. Give a real-life scenario where a queue would be unfair to use. Why?

Answer:

In an emergency room, using a queue would be unfair because critical patients may need immediate attention. A first-come, first-served approach could delay urgent cases. Priority handling is needed instead.

7. In your daily work, when do you prioritize the latest task instead of the first task? What structure does this represent?

Answer:

When a sudden urgent request comes in, I handle it first even if there are older tasks. This represents a stack because the most recent task is prioritized. It follows LIFO behavior.

8. What problem does a circular queue solve compared to a normal queue?

Answer:

A circular queue solves the issue of unused space in a normal queue. In a regular queue, freed spaces at the front cannot be reused easily. Circular queues reuse space by wrapping around.

9. Can a system use both stack and queue at the same time? Give a practical example.

Answer:

Yes, systems can use both depending on their needs. For example, a system may use a queue to process tasks and a stack to track undo actions. This allows both fairness and reversibility.

10. If a system processes the most urgent tasks first, is it still a pure queue? Why or why not?

Answer:

No, it is no longer a pure queue because queues follow strict FIFO order. Prioritizing urgent tasks changes the order of processing. This becomes a priority-based or hybrid system.