Computer Science - ICT Grade 10 Data Structures Stacks Queues Trees

Grade 10 Computer Science – Data Structures: Stacks, Queues, Trees

1. The Driving Question

"If your phone’s ‘undo’ button, a line at the DMV, and your family tree all follow different rules for organizing information, how do programmers decide which rule to use—and why can’t they just shove everything into a list and call it a day?" You’ve written code that stores data in arrays or lists, but real programs—like games, social media feeds, or file systems—need smarter ways to add, remove, and search data fast. How do you pick the right "shape" for your data when the wrong one could make your app slow, crash, or just feel clunky?

2. The Core Idea – Built, Not Listed

Imagine you’re backstage at a concert, and the band’s roadies are packing gear into a van. If they toss everything in randomly, finding the drummer’s cymbals later will be a nightmare. Instead, they use three strategies:

1. The "Last-In, First-Out" (LIFO) Stack: Like a stack of pizza boxes. The last box you put on top is the first one you grab when you’re hungry. This is how your phone’s "undo" button works—it remembers the most recent action first.
2. The "First-In, First-Out" (FIFO) Queue: Like a line at a food truck. The first person in line gets their burrito first, and new people join at the back. This is how printers handle jobs or how Netflix streams episodes in order.
3. The Tree: Like a family tree, where each person (node) has parents (above) and children (below). This is how file systems organize folders or how Google Maps finds the fastest route—by branching out from a starting point.

These aren’t just abstract ideas; they’re tools that solve specific problems. A stack is useless for printing jobs, and a queue can’t handle "undo." Trees let you search millions of files in seconds, while a list would take hours.

Key Vocabulary:
- Stack: A collection where the last item added is the first one removed (LIFO).
Example: The "back" button in a web browser—it pops the most recent page off the stack.
Note: In college, stacks are used in recursion (functions calling themselves) and memory management (the "call stack").

• Queue: A collection where the first item added is the first one removed (FIFO).
  Example: A playlist where songs play in the order they were added, not shuffled.
  Note: In systems programming, queues manage tasks like network requests or CPU scheduling.

• Tree: A hierarchical structure with a root node, branches (edges), and leaves (nodes with no children).
  Example: A tournament bracket where each game (node) has two teams (children) advancing to the next round.
  Note: In databases, trees (like B-trees) optimize search speed; in AI, decision trees classify data.

• Node: A single "unit" in a data structure that holds data and (usually) pointers to other nodes.
  Example: In a social media "friend tree," each node is a user with links to their friends.
  Note: In graph theory (college), nodes can have multiple parents, turning trees into more complex networks.

3. Assessment Translation

How this appears on tests (Grade 10):
- Multiple Choice: Questions test whether you can identify the right structure for a scenario (e.g., "Which data structure models a printer queue?") or predict output (e.g., "What’s the order of items after three pushes and two pops on a stack?").
Distractor patterns: - Confusing stack/queue behavior (e.g., "first-in, last-out" for a stack).
- Misidentifying tree traversal order (e.g., mixing up pre-order and post-order).
- Overcomplicating simple scenarios (e.g., suggesting a tree for a linear process like a playlist).

• Short Answer: "Explain why a stack is a poor choice for managing a print queue. Give an example of a better structure." Proficient response:

  
  

  "A stack uses LIFO, so the first print job added would be the last one printed—like if the first person in line at a printer got their document last. A queue (FIFO) is better because it processes jobs in the order they’re received. For example, if three people send jobs at 9:00, 9:01, and 9:02, a queue would print them in that order, while a stack would print 9:02 first."

  
  

• Coding Task: Implement a stack or queue in pseudocode or a language like Python/Java. Example: python # Implement a stack with push/pop methods stack = [] stack.append("A") # push stack.append("B") print(stack.pop()) # outputs "B" Proficient: Correct methods, handles edge cases (e.g., popping from an empty stack).
  Developing: Missing methods or logic errors (e.g., popping from the wrong end).

Model Proficient Response (Short Answer):
Prompt: "Describe a real-world scenario where a tree is more efficient than a list. Explain why." Response:

"A file system uses a tree to organize folders and files. If you had a list of 10,000 files, finding one would mean checking each item one by one (O(n) time). With a tree, you start at the root folder, then branch to subfolders, cutting the search time dramatically (O(log n) for balanced trees). For example, finding ‘Documents/CS101/Assignment1’ is faster in a tree because you only check the ‘Documents’ branch, not every file on the computer."

4. Mistake Taxonomy

Mistake 1: Misapplying Stack/Queue Rules
Question: "You push the numbers 1, 2, 3 onto a stack. Then you pop twice. What’s the remaining stack?" Common Wrong Answer: [1, 2] (student pops from the front like a queue).
Why It Loses Credit: Stacks are LIFO; pops remove the last item added. The correct order is [1] (pop 3, then 2).
Fix: Draw the stack vertically (like plates) and label the "top." Pop from the top, push to the top.

Mistake 2: Confusing Tree Traversal Orders
Question: "Traverse this tree in pre-order: [Root: 5, Left: 3, Right: 7]. Show the order." Common Wrong Answer: 3, 5, 7 (student does in-order by mistake).
Why It Loses Credit: Pre-order is root → left → right. The correct order is 5, 3, 7.
Fix: Use the mnemonic "Root, Left, Right" and trace with your finger: start at 5, go left to 3, then right to 7.

Mistake 3: Overcomplicating Simple Structures
Question: "Which data structure would you use to model a line at a coffee shop?" Common Wrong Answer: "A tree, because it’s hierarchical" (student forces a complex structure).
Why It Loses Credit: The scenario is linear (FIFO), so a queue is sufficient. Trees are for hierarchical data.
Fix: Ask: "Does the order matter? Is it first-come, first-served?" If yes, it’s a queue. If it’s nested (e.g., folders), it’s a tree.

5. Connection Layer

1. Within CS: Stacks → Recursion
   Recursion uses the call stack to track function calls. Understanding stacks helps debug infinite recursion (e.g., "Why does my program crash with a ‘stack overflow’?").

2. Across Subjects: Trees → Biology (Phylogenetic Trees)
   Trees model evolutionary relationships in biology. The "root" is a common ancestor, and "branches" show divergence—just like folders branching from a parent directory.

3. Outside School: Queues → Traffic Light Algorithms
   Traffic lights use queues to manage cars at intersections. The first car to arrive at a red light is the first to go when it turns green—just like a print queue. (Next time you’re stuck at a light, notice how the order is preserved!)

6. The Stretch Question

"If a tree is just a ‘restricted’ graph (no cycles, one parent per node), why do we even bother with trees? Couldn’t we just use graphs for everything?" Pointers Toward an Answer: - Trees are predictable: Their structure guarantees efficient search (O(log n)) and no infinite loops. Graphs are flexible but require extra checks (e.g., "Is this node already visited?").
- Trade-off: Trees sacrifice some freedom (e.g., no "back edges" like in social networks) for speed and simplicity. For example, file systems could use graphs to let files have multiple parents, but that would make searching chaotic.
- Real-world example: Git (version control) uses a directed acyclic graph (DAG), which is like a tree but allows some nodes to have multiple parents. This hybrid gives flexibility and structure.