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

Recommended Schedule

Day 1

• Stacks

Day 2

• Queues

Day 3

• Heaps

Day 4

• 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 CPPLab 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 CPPLab 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 CPPLab where you will implement the logic for a Max Heap