Laboratory: Priority Queues

Summary: In this laboratory, you will have an opportunity to ground your understanding of priority queues, particularly of the array-based implementation of queues. Along the way, you may think more about object-oriented design, such as the design of adapter classes.

Required Code Files:

https://github.com/Grinnell-CSC207/linear

Preparation

a. Add up the number of vowels in the first names of all of your group members. Make a note as to whether that number is even or odd.

b. Review the reading on linear structures.

c. Review the reading on priority queues.

Exercises

Exercise 1: Code Reading, Revisited

a. Read through our interface for priority queues, PriorityQueue.java.

b. Read through the documentation on the standard Java implementation of priority queues, available at http://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html.

c. Discuss with your partner how you would write an adapter class to make the built in priority queues match the desired behavior of our priority queue interface.

d. Look at BuiltinPriorityQueue.java to see how our implementation matches your design.

Exercise 2: Basic Experiments

Look at PriorityQueueExpt. Summarize what the queue should look like at each step of the first series of procedure calls. You may also want to revisit the ReportingLinearStructure class.

Run PriorityBasedQueueExpt and see if you get the output that you expect.

Exercise 3: Changing the Ordering

a. Revise PriorityQueueExpt so that the queue gives highest priority to the longest strings. That is, get should return the longest remaining string.

b. Revise PriorityQueueExpt so that the queue gives highest priority to the alphabetically first string.

Exercise 4: Code Reading, Revised

a. Read through ArrayBasedPriorityQueue.java. You will note that the iterator is not yet implemented and that prioritization is not yet implemented.

b. Make some notes to yourself as to how you might finish implementing the put and get methods.

Exercise 5: Implementing Priority Queues

As the reading noted, there are two basic strategies for implementing priority queues in arrays.

You can keep the values in order from lowest priority to highest priority. In this case, the put method must ensure that the elements in the array are stored in order. (You can probably use a variant of the insert method from insertion sort to achieve that goal.)
You can keep the values in arbitrary order and search for the highest-priorty element whenever we call get or peek. (You can probably use a variant of the indexOfSmallest method from selection sort to achieve that goal.)

If you came up with an odd number in the preparation, use the first of the two approaches. If you came up with an even number, use the second of the two approaches.

For Those with Extra Time

If you are fortunate enough to have extra time, do some of the following:

Implement array-based priority queues using whichever approach you did not use in exercise 5.
Make your priority queues expand automatically when someone tries to add an element beyond the initial capacity.
Implement linked priority queues.
Implement randomized queues, which give you an “unpredictable” element of the queue each time you call get. The easy approach is to simply pick a random position each time. However, that approach does not guarantee that peek returns the same value as the subsequent get. Start with the easy approach, and then see if you can get peek and get to work in synchrony.