The aims of this labsheet are to:

1. Implement a cyclic block version of a queue ADT.

2. implement a cyclic linked version of a queue ADT.

3. implement a cyclic Deque.

Exercises

1. An Alternative Cyclic Block Implementation of a Queue

   In the Lectures we discussed implemented a cyclic block implementation of the queue ADT using two indices to the first and last items in the block representing the queue. As discussed in the lecture notes, this requires increasing the size of the block by one in order to differentiate between an empty queue and a full queue.

   An alternative solution suggested in the lecture notes was to keep an index to the first item, along with an integer variable, say count, that stores the current size (the number of items) of the queue. Thus, for example, when an item is inserted into the queue, count will increase by 1.

   Write a cyclic block implementation of a queue called QueueCyclic using this alternative approach.

   Use an index called first to refer to the position in the block of the first character in the queue and an item count called count to determine the number of characters currently in the queue. Along with a reference to the actual block of characters, these two variables should be the only other instance variables needed in your implementation (in particular, the last instance variable is no longer needed). When you enqueue an item for example, the correct position in the block to insert the item will need to be calculated from first and count.

   Your queue ADT must implement the CITS2200.Queue interface (that is, the Queue interface in the CITS2200 package). However, since this class is block-based, as per the lecture notes, only a partial implementation of interface should be met: when all the space in the block is consumed, the enqueue method should generate an Overflow exception.

   Fully document your code using javadoc comments.

2. A Cyclic Linked Implementation of a Queue

   An (unbounded) queue can be implemented cyclically based on a linked representation. In this case, rather than referencing "null", the successor of the last item in the queue references the beginning of the queue. While this is not necessary to prevent memory erosion, it does mean that rather than having two references to the beginning and the end of the queue, only a single reference is needed.

   Write a cyclic linked implementation of a queue called QueueLinked using this approach.

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

3. A Cyclic Block implementation of a Deque.

   Implement and test your solution for the cyclic block implementation of the deque ADT discussed in Tutorial 3:

   1. DequeCyclic(s): create an empty deque of size s.
   2. isEmpty(): return true iff the deque is empty, false otherwise.
   3. isFull(): return true iff the deque is full, false otherwise.
   4. pushLeft(c): add object c as the left-most object in the deque, or throw an Overflow exception if the deque is full.
   5. pushRight(c): add object c as the right-most object in the deque, or throw an Overflow exception if the deque is full.
   6. peekLeft(): return the left-most object in the deque, or throw an Underflow exception if the deque is empty.
   7. peekRight(): return the right-most object in the deque, or throw an Underflow exception if the deque is empty.
   8. popLeft(): remove and return the left-most object in the deque, or throw an Underflow exception if the deque is empty.
   9. popRight(): remove and return the right-most object in the deque, or throw an Underflow exception if the deque is empty.

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

   Submit your DequeCyclic 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.

   Submit by 11:59 pm, Friday, March 31, 2023

Sample solution for Lab 3