Computer Science · Grade 11 · Data Structures and Management · Term 3

Implementing Stacks and Queues

Students will implement stack and queue data structures using arrays or linked lists, and apply them to simple problems.

• Ontario Curriculum Expectations
• CS.HS.A.3
• CS.HS.A.4

About This Topic

Stacks and queues are core abstract data types that organize data using last-in-first-out (LIFO) and first-in-first-out (FIFO) rules. Grade 11 students implement these structures with arrays or linked lists, then solve problems like reversing a string via stack operations or modeling a waiting line with a queue. They analyze performance differences, such as constant-time access in arrays versus dynamic resizing in linked lists, which sharpens their ability to select appropriate tools for tasks.

This topic supports Ontario's Computer Science curriculum by emphasizing algorithm design and efficiency evaluation, key to standards like CS.HS.A.3 and CS.HS.A.4. Students construct programs that reveal how push, pop, enqueue, and dequeue work under the hood, connecting theory to practical coding. Comparing implementations builds nuanced understanding of trade-offs in memory use and operation speed.

Active learning excels with this content because students code, test, and debug iteratively in real time. Collaborative challenges let them trace executions together, spot errors faster, and adapt algorithms on the fly. This hands-on process turns abstract rules into reliable skills, increasing confidence for complex data structures ahead.

Key Questions

1. Design an algorithm that uses a stack to reverse a string.
2. Compare the performance characteristics of array-based versus linked-list-based stacks and queues.
3. Construct a program that simulates a waiting line using a queue.

Learning Objectives

• Implement stack and queue data structures using arrays and linked lists.
• Analyze the time and space complexity of stack and queue operations for both array-based and linked-list-based implementations.
• Design an algorithm that utilizes a stack to reverse a string.
• Construct a program simulating a real-world waiting line using a queue.
• Compare and contrast the performance characteristics of array-based versus linked-list-based stacks and queues.

Before You Start

Introduction to Arrays

Why: Students need to understand how arrays store collections of data and how to access elements by index.

Basic Programming Constructs (Variables, Loops, Conditionals)

Why: Implementing stacks and queues requires fundamental programming logic, including variable manipulation, iteration, and conditional statements.

Introduction to Linked Lists

Why: Students should have a foundational understanding of nodes, pointers, and how linked lists are structured to implement linked list-based stacks and queues.

Key Vocabulary

Stack	A Last-In, First-Out (LIFO) data structure where elements are added (pushed) and removed (popped) from the same end, called the top.
Queue	A First-In, First-Out (FIFO) data structure where elements are added (enqueued) at one end (rear) and removed (dequeued) from the other end (front).
LIFO	Acronym for Last-In, First-Out, describing the principle of how data is accessed in a stack.
FIFO	Acronym for First-In, First-Out, describing the principle of how data is accessed in a queue.
Array-based Implementation	A method of building a data structure using a contiguous block of memory, like an array, which has a fixed size or requires resizing.
Linked List Implementation	A method of building a data structure using nodes that contain data and a pointer to the next node, allowing for dynamic resizing.

Watch Out for These Misconceptions

Common Misconception

Stacks and queues use the same access rules.

What to Teach Instead

Stacks are LIFO, queues FIFO; confusion leads to wrong outputs. Tracing paper simulations in pairs clarifies order differences, as students manually push/pop/enqueue/dequeue to see results diverge.

Common Misconception

Arrays always outperform linked lists.

What to Teach Instead

Arrays offer fast indexing but costly insertions; linked lists reverse this. Group benchmarking with large datasets reveals context-specific strengths, helping students discard absolute views through data.

Common Misconception

Data structure choice has no runtime impact.

What to Teach Instead

Operations vary in Big O notation by implementation. Step-through debugging in whole class demos visualizes extra traversals or copies, connecting code to efficiency metrics.

Active Learning Ideas

Pair Programming: Stack Reversal

Pairs implement a stack using an array with push and pop methods. They input a string, push characters, then pop to reverse it, handling edge cases like empty strings. Pairs test multiple inputs and swap code for peer review.

30 min·Pairs

Small Groups: Queue Simulation

Groups build a linked-list queue for a bank line simulator, coding enqueue and dequeue. They add 20 customers, process service times, and output wait statistics. Groups present results and discuss FIFO behavior.

45 min·Small Groups

Whole Class: Performance Benchmark

Display array-based and linked-list stack code. Class runs timed tests on 1,000 operations, records results on shared board. Discuss why one outperforms in specific scenarios.

25 min·Whole Class

Individual: Mixed Implementation

Students choose array or linked list to code both stack and queue, solving a provided problem like task scheduling. They self-test with unit cases and note pros/cons.

20 min·Individual

Real-World Connections

• Web browser history uses a stack to manage navigation, allowing users to go back to previous pages with the 'back' button.
• Call center software often uses a queue to manage incoming customer calls, ensuring that calls are answered in the order they were received.
• Undo functionality in text editors and graphic design software, such as Adobe Photoshop, is typically implemented using a stack to keep track of recent actions.

Assessment Ideas

Quick Check

Present students with a sequence of operations for both a stack and a queue (e.g., push A, push B, pop, enqueue C, dequeue). Ask them to trace the state of each data structure after each operation and record the final output.

Exit Ticket

Ask students to write a short paragraph explaining one scenario where a stack would be more appropriate than a queue, and one scenario where a queue would be more appropriate than a stack. They should justify their choices based on the LIFO and FIFO principles.

Discussion Prompt

Facilitate a class discussion comparing array-based versus linked-list-based implementations. Ask: 'When might an array-based stack be preferred, even if it means potential wasted space? When would a linked list's flexibility be essential for a queue?'

Frequently Asked Questions

How can active learning help students understand stacks and queues?

Active approaches like pair programming implementations and group simulations make LIFO/FIFO rules experiential. Students trace code live, fix bugs collaboratively, and benchmark performances, which solidifies abstract concepts. This beats passive reading, as immediate feedback builds debugging skills and reveals trade-offs, preparing them for real software challenges. Retention improves through ownership of working code.

What are the performance differences between array-based and linked-list stacks?

Array-based stacks offer O(1) push/pop with top indexing but risk resizing overhead. Linked-list versions handle dynamic growth seamlessly via pointers, though each operation traverses nodes. Students compare via benchmarks: arrays shine for fixed sizes, lists for frequent inserts. This analysis teaches amortized analysis basics.

How do you reverse a string using a stack?

Push each character onto the stack, then pop them into a new string. For 'hello', push 'h','e','l','l','o'; popping yields 'o','l','l','e','h'. Edge cases include empty strings. Implement with array: track top index, grow if needed. Tests confirm LIFO reverses perfectly.

Why simulate a waiting line with a queue?

Queues model real FIFO scenarios like print jobs or customer lines, teaching enqueue front, dequeue back. Students code to add/serve elements, compute averages. This applies theory, reveals underflow risks, and contrasts stacks, building intuition for everyday algorithms in software.