Week 5 - Stacks, Queues, and Heaps
Learning objectives
- Solve problems using a stack
- Implement an efficient stack or queue with a linked list or array
- Implement a heap using an array
- Reason about the efficiency of algorithms involving a heap
Schedule
Day 1
Todo:
- Do the
Linked List Basics Worksheet and check against the
key.
Day 2
Todo:
- Do the Ch 29 Exercises
Day 3
- Start Heaps (Ch 30.1-30.5)
Day 4
- Finish Heaps
Todo:
- Do this Heap practice worksheet and check against the key
- Do the Ch 30 Exercises
Recommended Schedule
Day 1
- Stacks
- Do the
Linked List Basics Worksheet and check against the
key.
Day 2
- Queues
- Do the Ch 29 Exercises
Day 3
- Start Heaps (Ch 30.1-30.5)
Day 4
- Finish Heaps
- Do this Heap practice worksheet and check against the key
- Do the Ch 30 Exercises
Stacks
Read Ch 29.1-29.2
This optional video reviews the concepts:
Then, watch this video on using a stack to convert infix to postfix notation:
Important Video
There are additional examples available in this InfixToPostFixExamples.pdf.
Queues
Read Ch 29.3-29.6
Then do the Ch 29 Exercises
This optional video reviews the concepts:
Heaps and Priority Queues
Read Ch 30.1-30.9
After Ch 30.6 do the Heap WS to practice adding and removing values from a heap by hand.
This video reviews the material from 30.2-30.6:
While this one covers 30.1 and 30.7-30.8: