School of Computer Science and Software Engineering

# School of Computer Science and Software Engineering

## CITS2200 Data Structures and Algorithms

The aims of this labsheet are to:

1. Implement a cyclic block 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 cssubmit.

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 27, 2020

# The University of Western Australia

## University information

CRICOS Code: 00126G