Implement the Queue ADT using a circular linked list. You will finish the implem
ID: 3800140 • Letter: I
Question
Implement the Queue ADT using a circular linked list. You will finish the implementation of the ch05.queues. CircularLinkedUnbndQueue class that already provided partial implementation of the methods. You should complete enqueue (most part of this method is done), dequeue, isFull, isEmpty and toString method. Enhance main methods to test the functionality.
Here is the code that needs to be completed:
Also, here is the code that was imported.
LLNode Class
QueueOverflowException Class
public class QueueOverflowException extends RuntimeException
{
public QueueOverflowException()
{
super();
}
public QueueOverflowException(String message)
{
super(message);
}
}
UnboundedQueueInterface Class
package ch05.queues;
public interface UnboundedQueueInterface<T> extends QueueInterface<T>
{
void enqueue(T element);
// Adds element to the rear of this queue.
}
Explanation / Answer
This is a perfectly working piece of code, tested thoroughly
package cho5.queues;
import support.LLNode;
public class CircularLinkedUnbndQueue<T> implements UnboundedQueueInterface<T> {
protected final int MAXIMUM_QUEUE_SIZE = 100;
protected int currentSize = 0;
protected LLNode<T> rear; // reference to the rear of this queue
public CircularLinkedUnbndQueue() {
rear = null;
}
/**
* Adds element to the rear of this queue.
* Throws QueueOverflowException if the queue is full
*/
@Override
public void enqueue(T element)
{
if (rear == null) { /* empty queue */
LLNode<T> newNode = new LLNode<T>(element);
newNode.setLink(newNode);
rear = newNode;
} else {
/* If the queue is full, throw exception */
if (isFull()) {
throw new QueueOverflowException("inserting in a full Queue");
}
/* step 1: create new object and let it link to the current front
* step 2: let the current rear node point to the new node
* step 3: update the rear reference of the queue
*/
LLNode<T> newNode = new LLNode<T>(element);
newNode.setLink(rear.getLink());
rear.setLink(newNode);
rear = newNode;
}
currentSize++;
}
/**
* Throws QueueUnderflowException if this queue is empty;
* otherwise, removes front element from this queue and returns it.
*/
@Override
public T dequeue()
{
if (isEmpty())
throw new QueueUnderflowException("Dequeue attempted on empty queue.");
else {
currentSize--;
LLNode<T> frontNode = rear.getLink();
T element = frontNode.getInfo();
/* If there is only one element, remove it
* */
if (rear.getLink() == rear) {
rear = null;
return element;
}
rear.setLink(rear.getLink().getLink());
return element;
}
}
/**
* Throws QueueUnderflowException if this queue is empty;
* otherwise, return front element from this queue.
*/
@Override
public T front() {
if (isEmpty())
throw new QueueUnderflowException("Dequeue attempted on empty queue.");
else {
LLNode<T> frontNode = rear.getLink();
T element = frontNode.getInfo();
return element;
}
}
/**
* Returns true if this queue is empty; otherwise, returns false.
*/
@Override
public boolean isEmpty()
{
if (rear == null)
return true;
else
return false;
}
@Override
public boolean isFull() {
return (currentSize == MAXIMUM_QUEUE_SIZE) ? true : false;
}
public String toString() {
LLNode<T> temp = rear.getLink();
StringBuffer buffer = new StringBuffer("[");
if (temp == rear) {
buffer.append(temp.getInfo()+"]");
return buffer.toString();
}
while (temp.getLink() != rear.getLink()) {
buffer.append(temp.getInfo()+", ");
temp = temp.getLink();
}
buffer.append(temp.getInfo()+"]");
return buffer.toString();
}
/* test the toString method */
public static void main(String[] args) {
CircularLinkedUnbndQueue<String> stringQueue = new CircularLinkedUnbndQueue<String>();
stringQueue.enqueue("A");
stringQueue.enqueue("B");
stringQueue.enqueue("C");
System.out.println(stringQueue.toString());
stringQueue.dequeue();
System.out.println(stringQueue.toString());
}
}
package cho5.queues;
public class QueueOverflowException extends RuntimeException {
/**
*
*/
private static final long serialVersionUID = -345259975691158780L;
public QueueOverflowException() {
super();
}
public QueueOverflowException(String message) {
super(message);
}
}
package cho5.queues;
public class QueueUnderflowException extends RuntimeException {
/**
*
*/
private static final long serialVersionUID = 6229315379876092973L;
public QueueUnderflowException() {
super();
}
public QueueUnderflowException(String message) {
super(message);
}
}
You didn't gave me the implementation of QueueInterface<T> which the following class implements. So, i removed the "extend" and wrote the methods directly. If you want, you can just add the interface.
package cho5.queues;
public interface UnboundedQueueInterface<T>{
/**
* Adds element to the rear of this queue.
* Throws QueueOverflowException if the queue is full
*/
public void enqueue(T element);
/**
* Throws QueueUnderflowException if this queue is empty;
* otherwise, removes front element from this queue and returns it.
*/
public T dequeue();
/**
* Throws QueueUnderflowException if this queue is empty;
* otherwise, return front element from this queue.
*/
public T front();
/**
* Returns true if this queue is empty; otherwise, returns false.
*/
public boolean isEmpty();
/**
* Returns true if this queue is full; otherwise, returns false.
*/
public boolean isFull();
}