Class 28: Queues and Their Implementation

Held: Friday, March 10, 2006

Summary: Today we consider a second linear structure: The Queue. Queues implement a first-in, first-out policy.

Notes:

• I intend to return the exam on Monday.

Overview:

• Review of homework.
• Queues, revisited.
• Problems with the array-based implementation.
• Implementing queues with nodes.
• Priority queues.

Review of homework

• We'll look at someone's solution to the homework.

Queues, revisited

• A queue is a linear structure.
• Queues implement the FIFO (first in, first out) policy
• Queues model lines at a store (among other things).
• Queues are significantly fairer than stacks (most things eventually come out of queues; the first thing added to a stack may never return)

Problems with the array-based implementation

• Michael suggested an array-based implementation of queues.
  • Like the array-based implementation of stacks, it keeps track of the "end" (where to add values).
  • It also keeps track of the "front" (where to remove values)
  • When the end is reached, shift stuff left.
• I've implemented a simple version of this strategy.
  • The array doesn't expand when necessary.
• I haven't implemented isEmpty correctly. How should I correct it?
• What else is wrong with this implementation? It can be inefficient.
• Consider
  • Put N objects (the size of the array)
  • Repeat N times
    • Get an object
    • Put an object (which causes the array to shift)
• Arguably, we should be able to get and put in O(1) time.

Implementing queues with nodes

• How can we do better?
• We can use an idea from Scheme.
• Rather than shoving stuff in an array, we use a linked collection of nodes.
• Each node keeps track of
  • The current value
  • A link to the rest of the queue
• The queue keeps track of the first node and the last node.
• We'll look at this implementation in some depth.

Priority Queues

• Our final linear structure is the priority queue.
• Priority queues implement a "highest priority first" get method.
• How do we determine priority?
  • If all the objects in our priority queue are Comparable, we can use the CompareTo method.
  • We can require that each priority queue have an underlying Comparator, which is probably specified in the constructor
• We'll look at implementation issues in the next class.