Implementing Stacks and Queues

Active learning works well here because students often confuse LIFO and FIFO rules, and hands-on practice with real code helps them internalize the differences. Small group simulations and pair work also let students verbalize their reasoning, which deepens their understanding of how stacks and queues behave in actual programs.

• Grade 11
• Computer Science
• 4 activities
• 20 min–45 min

Learning Objectives

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

Experiential Learning

⏱ 30 min·Pairs

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.

Prepare & details

Design an algorithm that uses a stack to reverse a string.

Facilitation Tip: During Pair Programming: Stack Reversal, encourage students to swap roles every two operations to keep both partners engaged in the logic.

Setup: Varies; may include outdoor space, lab, or community setting

Materials: Experience setup materials, Reflection journal with prompts, Observation worksheet, Connection-to-content framework

• Apply
• Analyze
• Evaluate
• Self-Awareness
• Self-Management
• Social Awareness

Experiential Learning

⏱ 45 min·Small Groups

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.

Prepare & details

Compare the performance characteristics of array-based versus linked-list-based stacks and queues.

Facilitation Tip: In Small Groups: Queue Simulation, provide real-world scenarios like ticket sales or printer queues to make the FIFO concept tangible.

Setup: Varies; may include outdoor space, lab, or community setting

Materials: Experience setup materials, Reflection journal with prompts, Observation worksheet, Connection-to-content framework

• Apply
• Analyze
• Evaluate
• Self-Awareness
• Self-Management
• Social Awareness

Experiential Learning

⏱ 25 min·Whole Class

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.

Prepare & details

Construct a program that simulates a waiting line using a queue.

Facilitation Tip: For Whole Class: Performance Benchmark, run the same test twice, once with arrays and once with linked lists, to highlight resizing costs.

Setup: Varies; may include outdoor space, lab, or community setting

Materials: Experience setup materials, Reflection journal with prompts, Observation worksheet, Connection-to-content framework

• Apply
• Analyze
• Evaluate
• Self-Awareness
• Self-Management
• Social Awareness

Experiential Learning

⏱ 20 min·Individual

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.

Prepare & details

Design an algorithm that uses a stack to reverse a string.

Facilitation Tip: During Individual: Mixed Implementation, give a starter code snippet that intentionally uses the wrong structure for the task, so students debug the mismatch.

Setup: Varies; may include outdoor space, lab, or community setting

Materials: Experience setup materials, Reflection journal with prompts, Observation worksheet, Connection-to-content framework

• Apply
• Analyze
• Evaluate
• Self-Awareness
• Self-Management
• Social Awareness

Teaching This Topic

Start with concrete, relatable examples like undo features for stacks or printer queues for queues to ground abstract rules. Avoid teaching these structures in isolation—instead, pair each new operation with a real problem students care about. Research shows that tracing paper or whiteboard sketches helps students visualize pointers and shifts in state, so include these visual tools often. Finally, emphasize that the choice between array and linked list depends on the context, not a universal rule.

What to Expect

By the end of these activities, students should confidently trace stack and queue operations, choose the right implementation for a task, and compare performance trade-offs using Big O notation. They will also articulate why one structure fits a problem better than the other, backing claims with data from benchmarks.

Watch Out for These Misconceptions

Common Misconception

During Pair Programming: Stack Reversal, watch for students who treat stack and queue operations interchangeably.

What to Teach Instead

Have them pause after each operation to sketch the stack’s state with arrows and labels, then repeat the process for a queue with the same inputs to highlight the divergence.

Common Misconception

During Whole Class: Performance Benchmark, watch for students who assume arrays are always faster due to indexing speed.

What to Teach Instead

Ask groups to increase the dataset size until the linked list’s insertion time becomes noticeably faster, then discuss memory fragmentation in arrays as the cause.

Common Misconception

During Small Groups: Queue Simulation, watch for students who ignore the FIFO rule when modeling real-world systems.

What to Teach Instead

Require them to map each enqueue and dequeue operation to a specific person or item in their scenario, forcing them to follow the order strictly.

Assessment Ideas

Quick Check

After Pair Programming: Stack Reversal, display a sequence of mixed stack and queue operations on the board and ask students to write the final state of each structure on a sticky note to submit.

Exit Ticket

After Whole Class: Performance Benchmark, ask students to compare their array and linked list runtimes in one paragraph, explaining which structure they would choose for a large dataset and why.

Discussion Prompt

During Small Groups: Queue Simulation, circulate and ask each group to justify their choice of implementation for their scenario, then facilitate a class vote on the most convincing argument.

Extensions & Scaffolding

• Challenge students who finish early to implement a stack using two queues or a queue using two stacks, then compare performance with the original version.
• Scaffolding for struggling students: Provide pre-labeled tracing templates with blanks for each operation’s state after it runs.
• Deeper exploration: Ask small groups to design a hybrid data structure that blends stack and queue behaviors, then present their logic to the class.

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.