The aims of this labsheet are to:
Implement a cyclic block version of a queue ADT.
implement a cyclic linked version of a queue ADT.
implement a cyclic Deque.
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.
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.
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:
DequeCyclic(s)
: create an empty deque of size s
.
isEmpty()
: return true iff the deque is empty, false otherwise.
isFull()
: return true iff the deque is full, false otherwise.
pushLeft(c)
: add object c
as the left-most object in the deque, or throw an Overflow
exception if the deque is full.
pushRight(c)
: add object c
as the right-most object in the deque, or throw an Overflow
exception if the deque is full.
peekLeft()
: return the left-most object in the deque, or throw an Underflow
exception if the deque is empty.
peekRight()
: return the right-most object in the deque, or throw an Underflow
exception if the deque is empty.
popLeft()
: remove and return the left-most object in the deque, or throw an Underflow
exception if the deque is empty.
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