Queues: FIFO Data StructureActivities & Teaching Strategies
Active learning works especially well for queues because fairness through FIFO ordering is intuitive in daily life but tricky to implement correctly in code. Students need to physically manipulate enqueue and dequeue actions to internalize how the abstraction matches real systems like printers or CPUs.
Learning Objectives
- 1Compare the time complexity of enqueue and dequeue operations for array-based and linked-list-based queue implementations.
- 2Design a program that utilizes a queue to manage print jobs for a simulated network printer.
- 3Analyze the role of queues in implementing breadth-first search algorithms for graph traversal.
- 4Evaluate the trade-offs between space efficiency and time efficiency for different queue implementations.
Want a complete lesson plan with these objectives? Generate a Mission →
Simulation Game: The Printer Queue
Students act as print jobs arriving at different times. The 'printer' (one designated student) processes jobs strictly in arrival order. After one round, introduce a priority variant where urgent jobs jump ahead. The class compares the two systems, discussing fairness, throughput, and starvation, making the design trade-offs tangible before they appear in code.
Prepare & details
Compare the operational principles of stacks and queues and their respective use cases.
Facilitation Tip: During the Printer Queue simulation, hand out sticky notes so students can physically pass tasks to the 'printer' and witness gaps in the array grow visibly.
Setup: Flexible space for group stations
Materials: Role cards with goals/resources, Game currency or tokens, Round tracker
Collaborative Lab: Array-Based vs. Linked-List Queue
Pairs implement both an array-based and a linked-list-based queue with enqueue, dequeue, peek, and isEmpty methods. They benchmark both with a sequence of 1,000 operations and compare memory usage by counting the maximum number of variables in use at once. Pairs then write a brief design recommendation for each of two scenarios: a memory-constrained embedded system and a high-throughput server.
Prepare & details
Design a system where a queue would be the most appropriate data structure for managing tasks.
Facilitation Tip: While implementing array vs. linked-list queues, ask students to annotate their code with index states at each step to reveal wasted space or null pointers.
Setup: Groups at tables with problem materials
Materials: Problem packet, Role cards (facilitator, recorder, timekeeper, reporter), Problem-solving protocol sheet, Solution evaluation rubric
Think-Pair-Share: BFS and Queues
Show students a small graph and ask them individually to trace why a queue (not a stack) ensures that breadth-first search explores nodes level by level. Pairs compare their reasoning and then trace through the BFS algorithm step by step on a shared diagram, annotating the queue state after each enqueue and dequeue operation. This pairs data structure understanding with algorithm application.
Prepare & details
Evaluate the performance characteristics of array-based versus linked-list-based queue implementations.
Facilitation Tip: For the BFS think-pair-share, provide a small graph and colored markers so pairs can literally trace the queue order on paper before coding.
Setup: Standard classroom seating; students turn to a neighbor
Materials: Discussion prompt (projected or printed), Optional: recording sheet for pairs
Gallery Walk: Real-World Queue Systems
Post 5 real-world queue scenarios: airport check-in, hospital triage, CPU scheduling, message broker, HTTP request handling. For each, student pairs answer three questions: what is the queue storing, what determines order, and what happens if the queue is full or empty. Responses are compared during debrief, emphasizing how each system handles overflow or high-demand situations.
Prepare & details
Compare the operational principles of stacks and queues and their respective use cases.
Facilitation Tip: In the Gallery Walk, assign each pair one real-world scenario card to explain how their queue choices affect fairness or efficiency.
Setup: Wall space or tables arranged around room perimeter
Materials: Large paper/poster boards, Markers, Sticky notes for feedback
Teaching This Topic
Start with the printer simulation to ground FIFO in a concrete, low-stakes task. Move quickly to the array vs. linked-list lab so students confront memory issues firsthand. Use the think-pair-share to bridge the abstract queue concept to BFS before they write any code. Avoid rushing through the linked-list implementation; many students need to draw pointers repeatedly to trust the links.
What to Expect
Successful learning looks like students confidently choosing the correct queue implementation for a given scenario, tracing operations without index errors, and explaining why a FIFO sequence matters in systems such as BFS or process scheduling.
These activities are a starting point. A full mission is the experience.
- Complete facilitation script with teacher dialogue
- Printable student materials, ready for class
- Differentiation strategies for every learner
Watch Out for These Misconceptions
Common MisconceptionDuring Simulation: The Printer Queue, watch for students assuming a stack would work just as well as a queue for print jobs.
What to Teach Instead
After the simulation, replay the same job sequence with a stack and ask students to compare the order of printed pages to the original FIFO output. Have them write a one-sentence rule explaining when a stack is appropriate for print jobs.
Common MisconceptionDuring Collaborative Lab: Array-Based vs. Linked-List Queue, watch for students believing the array-based queue never wastes memory.
What to Teach Instead
Ask students to trace an array-based queue through 10 enqueue and 6 dequeue operations. Have them circle the unused cells and calculate the wasted space percentage. Then ask them to propose one fix and implement it.
Common MisconceptionDuring Think-Pair-Share: BFS and Queues, watch for students equating any graph traversal with FIFO ordering.
What to Teach Instead
Present a small priority queue example alongside the BFS graph. Ask pairs to explain in one sentence why FIFO alone cannot handle priorities, then show how their BFS code would need to change.
Assessment Ideas
After Simulation: The Printer Queue, run a live trace on the board with 5 enqueue and 3 dequeue operations. Ask students to write the next item to dequeue on a sticky note and hold it up for immediate feedback.
During Collaborative Lab: Array-Based vs. Linked-List Queue, circulate and listen for groups debating which structure to use for a printer queue that handles 1000 pages per minute. Ask one group to present their reasoning and code structure at the end of the lab.
After Gallery Walk: Real-World Queue Systems, ask students to write a paragraph connecting one real-world system they saw to a specific choice of queue implementation, naming either array or linked list and justifying the decision based on performance or memory constraints.
Extensions & Scaffolding
- Challenge students to implement a circular buffer version of the array-based queue and compare throughput with the original linear array.
- Scaffolding: Provide pre-labeled diagrams of front and rear pointers for students to trace during the array-based queue lab.
- Deeper exploration: Ask students to research priority queues and modify their BFS implementation to process higher-priority nodes first.
Key Vocabulary
| Queue | A linear data structure that follows the First-In, First-Out (FIFO) principle, where elements are added at one end (rear) and removed from the other end (front). |
| Enqueue | The operation of adding an element to the rear of the queue. |
| Dequeue | The operation of removing and returning the element from the front of the queue. |
| FIFO | Acronym for First-In, First-Out, meaning the first element added to a data structure is the first one to be removed. |
| Circular Array | An array implementation of a queue where the indices wrap around, allowing efficient reuse of space and avoiding shifting elements. |
Suggested Methodologies
Simulation Game
Complex scenario with roles and consequences
40–60 min
Collaborative Problem-Solving
Structured group problem-solving with defined roles
25–50 min
More in Object-Oriented Design and Data Structures
OOP Principles: Encapsulation and Abstraction
Students explore the core OOP principles of encapsulation and abstraction, understanding how they promote modularity and data hiding.
2 methodologies
Inheritance and Polymorphism in Depth
Students design class hierarchies that promote code reuse and flexibility, implementing interfaces and abstract classes.
2 methodologies
Introduction to Generic Programming
Students learn to write generic classes and methods that can operate on different data types, enhancing code reusability.
2 methodologies
Implementing Linked Lists (Singly and Doubly)
Students build and manipulate singly and doubly linked lists from scratch, understanding dynamic memory allocation.
2 methodologies
Stacks: LIFO Data Structure
Students implement stack data structures and explore their applications in function call management and expression evaluation.
2 methodologies
Ready to teach Queues: FIFO Data Structure?
Generate a full mission with everything you need
Generate a Mission