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

Priority Queues and HeapSort