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

  • List Iterators

Tuesday

  • Stacks

Wednesday

  • Queues

Thursday

  • Prewatch the first 8 minutes of this Heap video and take reading quiz before class.
  • Heaps

Topics

List Iterators

  • Watch this video on list iterators:

  • Read Liang Ch 20.5

  • Do the LinkedList Iterators CPPLab. Don't overthink it. It should be the shortest CPPLab in terms of lines of code you ever do.

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