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
Class Schedule
Monday
- Stacks
Tuesday
- Queues
Wednesday
- Heaps
Thursday
- Priority Queues and HeapSort
Topics
Stacks
Watch this video on Stacks:
Read Liang Ch 12.4, 12.5, 12.9
Watch this video on using a stack to convert infix to postfix notation:
Do the InToPostFix Worksheet to practice using a stack to parse mathematical expressions. There are extra examples available in the InfixToPostfixExamples.pdf in the Class Files link.
The StackSamples project shows demonstration programs for parsing postfix expressions and for parentheses checking. Make sure to check it out.
Queues
Watch:
Here is an array based queue simulation you can try out
Read Ch 20.8
Do the Queues CPP Lab where you will implement the logic for an efficient array-based queue.There is a Queue WS in the files directory that has diagrams that might be helpful while you do the CPP Lab problems.
Heaps
Watch:
Read Ch 19.6 - 19.6.4
Do the Heap WS to practice adding and removing values from a heap by hand
Here is a min heap simulation you can try out
Priority Queues and HeapSort
Watch:
Read Ch 19.6.5 and 20.9
Here is a heap sort simulation you can try out
Do the Heaps CPP Lab where you will implement the logic for a Max Heap