Lab: Gaining Experience with Abstract Data Types


Instructions: Answer as many of the following questions as you can during the lab period. If you are unable to complete the assignment during the lab period it is strongly recommended that you complete it on your own.

Getting Ready: Before going any further, you should:

  1. Make a directory for this lab.
  2. Setup your development environment.
  3. Download the following files:
    to your working directory. (In most browsers, the easiest way to do this is by right-clicking on each of the links above.)

1. The Assignment: This part of the lab will help you gain some experience designing and implementing abstract data types.

A priority queue is an abstract data type in which each value entered has an associated priority. The highest priority values move to the front of the priority queue. The next value to leave the priority queue is always the value with the highest priority that has been in the priority queue the longest.

One way to implement a priority queue is with a collection of (regular) queues. Each queue holds values of equal priority. When a value enters the priority queue, it is placed in the regular queue that matches its priority; values leave the priority queue starting with the regular queues of highest priority.

  1. Complete the PriorityQueue class using an array of regular queues. (Note: One of the methods uses a variable-length parameter list.) Remember to submit your solution.

  2. Test your priorty queue using the Driver.

Copyright 2007