Week 6: Deques and Linear Structure Applications

Outcomes

• Explain the main operators of a deque (understand and discuss the ADT description).
  • add_front()
  • add_rear()
  • remove_front()
  • remove_rear()
  • size()
  • is_empty()
• Explain the pseudocode for the operators of a deque
• Identify the Big-Oh notation for the operators of a deque
• Explain how a Python list based implementation of a deque fulfills the operators (ADT) of the stack
• Provide an example of where a deque could be used in programming
• Given a real world example, indicate if a deque is an appropriate data structure to use with the problem.

Activities - Deque

• Like we did last week, let's mix reading with videos
  • Read Section 3.15
• Watch - What is a Deque [Video, 4 minutes]
• Read Section 3.16
• Watch - Understanding the Deque ADT [Video, 3 minutes]
• [Optional] How could you implement a Deque in python?
• Read Section 3.17
• Watch - Examining the Deque Code and considering Big-Oh [Video, 7 minutes]
  • deque_code.py [code]
• Read Section 3.18
  • I do not expect you to be an expert on this example.
  • I only ask you to read about it so you can see some problems where Deques might be used

You Do It #6

• Consider these real world examples of linear structures.
• Stack, Queue, or Deque?
• My answer key is this video [Video, 14 minutes]

Additional Resources

• You may have noticed this on the table of contents page for your textbook. Professor Gerry Jenkins is a retired professor from Long Beach City College who made a bunch of videos to correspond with the readings in your textbook. I have NOT viewed all of them. But, I know how helpful it can be to have a wide variety of study resources.
  • Video 10 on this playlist corresponds to material we covered this week
    • Note, The proper pronunciation of a Deque is "Deck" not De-Queue as Professor Jenkins pronounces it.
    • https://en.wikipedia.org/wiki/Double-ended_queue