# Class 32: Queues and Their Implementation

Back to Project Discussion. On to Preparation for Exam 2.

Held: Wednesday, 27 October 2004

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

Related Pages:

Assignments

Notes:

• The next exam will be distributed on Friday.

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.

Back to Project Discussion. On to Preparation for Exam 2.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed Dec 8 10:37:21 2004.
The source to the document was last modified on Thu Aug 26 20:22:23 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2004F/Outlines/outline.32.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu