Outline:

1. Circular-array-based queue
   • high-level idea
   • implementation: Exercise
   • time complexity
2. Linked-list-based queue
3. Comparison of queue and stack implementations
4. Review

What’s next

Upcoming events/assessments:

• CS Bits and Bytes Thursday at 3:30pm in Anderson 329: Alex Dixon ‘01 (at Adobe) on HDR photo editing
• Assignment 4 will be released Friday

What you should do now:

• Review!

Reminder: Exam Day on Friday

You will see these Quiz Learning Objectives for the first time:

• Core:
  • SQ 3: queues
  • SQ 4: core queue time complexity
• Advanced:
  • LT 7: debugging lists
  • LT 8: using lists
  • SQ 6: queue time complexity

There will also be a packet of learning objectives you’ve seen before, covering everything from Units 1+2 except the five listed above and SQ 7: using stacks/queues.

Reading assignment (to be completed by the next class):

Another linear data structure (from today):

• Circular queue

More linear data structures (for next Monday):

• Doubly-linked lists
• Deques