Exercise 1a of this labsheet is worth 2.5% of your final mark in this unit. The final date for submission is: 11:59pm Friday, May 5, 2023.

The aims of this labsheet are to:

1. implement a linked version of the priority queue ADT, and

2. implement a block version of the priority queue ADT.

Exercises

1. Linked Implementation of a Priority Queue

   Topic 13 of the lecture notes discusses the PriorityQueue ADT, generously providing code for a linked implementation. In this exercise, you must extend this code so that it fully implements the CITS2200.PriorityQueue interface. Your implementation should simply store Objects rather than use Java generics, but it will need to provide an iterator to access the elements of the collection. The iterator class must be implemented as an inner class.

   1. Write a class called PriorityQueueLinked that implements a singly linked version of the PriorityQueue interface.

      Your priority queue ADT must implement the CITS2200.PriorityQueue interface (that is, the PriorityQueue interface in the CITS2200 package). Fully document your code using javadoc comments.

      Submit your PriorityQueueLinked implementation to the correct Moodle folder.

      If submitted before the due date, the system will compile and run your code, estimate your mark, and provide you with feedback. Final marking will occur after the posted due date and is subject to further examination, testing, and plagiarism checks of your code. Note that for security reasons, your code cannot contain any I/O commands, including printing statements. Although the auto-marking program provides you with some feedback, it should not be used as a substitute for your own testing. Indeed, you may be penalised if you make too many submissions.

      Note: as the security manager used by the auto-marking program is a little overzealous, it may terminate when constructing and using instances of your inner class. To overcome this, you should make all inner classes and their constructors public, and if any other class refers to variables in an inner class, those variables should also be public.

   2. Write a test program that thoroughly tests each operation of your priority queue ADT to satisfy yourself that your code is working correctly.

2. Block Implementation of a Priority Queue

   If we know in advance that a priority queue will only ever need to cater for a small number of discrete priorities (say 10), we can implement all operations of the priority queue in constant time by representing the priority queue as an array of queues - each queue storing the elements of a single priority. Note that while an operation may be linear in the number of priorities in the priority queue, the operation is still constant with respect to the size of the overall data structure.

   1. Write a class called PriorityQueueBlock that implements a block version of the PriorityQueue interface with all operations running in constant time. Fully document your code using javadoc comments.

   2. Write a test program that thoroughly tests each operation of your priority queue ADT to satisfy yourself that your code is working correctly.

Sample solution for Lab 7 is here