Computing · JC 2 · Abstract Data Structures and Algorithms · Semester 1

Stacks and Queues: Implementations and Applications

Students will identify and create simple step-by-step instructions (algorithms) for everyday tasks, understanding the importance of order and precision.

• MOE Syllabus Outcomes
• MOE: Algorithms - Middle School

About This Topic

Stacks and queues form essential abstract data types in computing, with stacks following last-in-first-out (LIFO) order and queues adhering to first-in-first-out (FIFO). At JC 2 level, students compare array-based implementations, which offer constant-time access but fixed capacity, against linked-list versions that provide dynamic sizing at the cost of pointer overhead. They analyse amortised time complexities for operations like push and pop, and evaluate space trade-offs to decide preferences based on use cases.

This topic integrates with the MOE Computing curriculum's focus on algorithms, linking to graph traversals where stacks drive depth-first search (DFS) by exploring deeply before backtracking, while queues enable breadth-first search (BFS) through level-by-level expansion. Students design stack-based algorithms for postfix expression evaluation, parsing operands and operators sequentially, and compute O(n) time and space complexities. These skills sharpen analytical thinking for real-world applications like function call management and task scheduling.

Active learning suits this topic well. When students simulate stacks with cards or queues with lines of objects, pair-program implementations, or trace traversals on paper graphs collaboratively, they internalise abstract behaviours and spot implementation flaws hands-on. This approach turns theoretical analysis into practical insight, boosting retention and problem-solving confidence.

Key Questions

1. Compare array-based and linked-list-based implementations of a stack in terms of amortised time complexity and space overhead, and explain under what conditions each is preferred.
2. Design an algorithm using a stack to evaluate a postfix (reverse Polish notation) arithmetic expression and analyse its time and space complexity.
3. Explain how a queue underpins BFS and how a stack underpins DFS, and determine what structural property of each ADT makes it suited to its respective traversal.

Learning Objectives

• Compare the amortised time complexity and space overhead of array-based versus linked-list-based stack implementations.
• Design and analyze an algorithm using a stack to evaluate a postfix arithmetic expression.
• Explain how a queue's FIFO property enables Breadth-First Search (BFS) and how a stack's LIFO property enables Depth-First Search (DFS).
• Evaluate the suitability of stacks and queues for specific applications based on their operational characteristics.

Before You Start

Arrays and Linked Lists

Why: Students need a foundational understanding of how these data structures store elements and manage memory to compare their implementation of stacks and queues.

Basic Algorithmic Concepts

Why: Familiarity with sequential execution, loops, and conditional statements is necessary to design and analyze algorithms for stack and queue operations.

Key Vocabulary

Stack (LIFO)	A data structure where the last element added is the first one to be removed, like a stack of plates.
Queue (FIFO)	A data structure where the first element added is the first one to be removed, similar to a waiting line.
Amortised Time Complexity	The average time complexity of an operation over a sequence of operations, accounting for occasional expensive operations.
Postfix Notation (RPN)	An arithmetic expression format where operators follow their operands, e.g., 3 4 + instead of 3 + 4.
Breadth-First Search (BFS)	A graph traversal algorithm that explores neighbor nodes before moving to the next level, often using a queue.
Depth-First Search (DFS)	A graph traversal algorithm that explores as far as possible along each branch before backtracking, often using a stack.

Watch Out for These Misconceptions

Common Misconception

Array-based stacks are always faster than linked-list ones.

What to Teach Instead

Arrays provide O(1) amortised access without pointers, but resizing doubles space periodically. Linked lists avoid resizing yet incur O(1) per node allocation. Active pairwise comparisons of test cases reveal context-specific trade-offs, like fixed vs variable sizes.

Common Misconception

Stacks and queues are interchangeable for traversals.

What to Teach Instead

Stacks suit DFS for deep exploration due to LIFO backtracking; queues fit BFS for breadth via FIFO. Group simulations on graphs highlight how order affects paths, correcting assumptions through visual tracing.

Common Misconception

Postfix evaluation requires recursion.

What to Teach Instead

Stacks enable iterative parsing by deferring operators until operands arrive. Hands-on token games show linear passes suffice, building confidence in non-recursive algorithms via step-by-step enactment.

Active Learning Ideas

Pair Programming: Stack Implementations

Pairs implement array-based and linked-list stacks in pseudocode or Python, adding push, pop, and peek methods. They test with sequences of operations and measure simulated time costs. Compare results in a shared class document.

45 min·Pairs

Small Groups: Postfix Evaluator Game

Groups receive cards with postfix expressions like '3 4 + 5 *'. They use physical tokens on a stack model to evaluate step-by-step, recording stack states. Discuss errors and complexities as a group.

30 min·Small Groups

Whole Class: Graph Traversal Simulation

Project a simple graph. Class votes on next moves using stack (DFS) or queue (BFS) rules, with teacher facilitating pushes/pops on a board. Students note visited order and path properties.

35 min·Whole Class

Individual: Queue vs Stack Challenges

Students solve puzzles like reversing a word (stack) or round-robin scheduling (queue) using everyday objects. Submit traces showing operation sequences and rationale for ADT choice.

25 min·Individual

Real-World Connections

• Software engineers use stacks to manage function calls in programming languages like Python and Java. When a function is called, its context is pushed onto the call stack; when it returns, its context is popped off, enabling program execution flow.
• Operating systems employ queues for task scheduling, prioritizing processes based on arrival time or other criteria. For example, a print queue manages print jobs submitted by multiple users to a shared printer, ensuring fair access.
• Network routers utilize queues to buffer incoming data packets when network traffic is high, preventing packet loss. This ensures that data is processed in the order it was received, maintaining data integrity.

Assessment Ideas

Quick Check

Present students with two code snippets: one implementing a stack using an array and another using a linked list. Ask them to identify one advantage and one disadvantage of each implementation in terms of memory usage and performance for a large number of operations.

Exit Ticket

Provide students with a postfix expression, e.g., '5 2 + 3 *'. Ask them to trace the evaluation using a stack, showing the stack's state after each operation. Then, ask them to state the final result.

Discussion Prompt

Pose the question: 'Imagine you are designing a system to manage customer support tickets. Would you use a stack or a queue? Justify your choice by explaining how the ADT's properties align with the system's requirements for handling incoming requests.'

Frequently Asked Questions

How to compare array and linked-list stack implementations?

Guide students to benchmark push/pop times: arrays excel in cache locality for small, known sizes; linked lists handle growth flexibly despite overhead. Use tables for amortised O(1) analysis and scenarios like undo histories (array) versus dynamic calls (linked). Visual aids like memory diagrams clarify space costs, fostering informed choices.

What algorithm evaluates postfix expressions using stacks?

Scan left-to-right: push operands, pop two for operators, push result. For '2 3 + 4 *', stack evolves as [2],[2,3],[5],[5,4],[20]. Time/space both O(n). Practice with varied expressions reinforces parsing logic and error handling in operator precedence.

Why stacks for DFS and queues for BFS?

DFS mimics recursion with LIFO backtracking to unexplored branches first. BFS uses FIFO to process levels evenly, ideal for shortest paths. Demonstrate on trees: stack yields [A,B,D] order; queue [A,B,C]. This structural fit underpins efficiency in unweighted graphs.

How does active learning benefit teaching stacks and queues?

Activities like card stacks or line queues make LIFO/FIFO tangible, while pair-coding implementations exposes complexity pitfalls early. Collaborative traversals on graphs reveal traversal differences dynamically. Students gain deeper analysis skills, as physical or simulated errors prompt debugging discussions that lectures miss, improving long-term mastery.