Following code has the start of a class which implements a Queue using a linked
ID: 3806777 • Letter: F
Question
Following code has the start of a class which implements a Queue using a linked list WITHOUT also defining all of the List methods. This also improve this class because, unlike Java, it uses the correct names. You will need to complete the enqueue(), dequeue(), and peek() methods to add an element, remove the element at the front, and return (without removing) the element at the front. Your methods will need to use the Entry and EmptyQueueException classes from the JAR file I supply. (It's custom entry class)
Explanation / Answer
import IntQueue.Entry;
/**
* Class which implements a proper {@code Queue} (including using the CORRECT method names) using a set of singly linked
* nodes. Besides in the naming convention, this does not include the methods that are inappropriate for a Queue to
* have,
*
* @param Type of data stored within this Queue.
*/
public class ProperQueue {
/**
* The first node in the linked list (or null if the list is empty). This is the end of the list where we remove
* elements from.
*/
private Entry head;
/**
* The first node in the linked list (or null if the list is empty). This is the end of the list where we add elements
* to include them on the queue.
*/
private Entry tail;
/**
* The number of elements currently in the queue.
*/
private int size;
/** Create a new (empty) instance of this class. */
public ProperQueue() {
head = null;
tail = null;
size = 0;
}
/**
* Adds an item to the end of the queue. Traditionally, this is the only
* method available to add data to a Queue.
*
* @param item Element to be added to the end of the queue.
* @return Element added to the Queue (e.g., {@code item}).
*/
public E enqueue(E item) {
// add i to the queue
size++;
Entry e = new Entry(item, null, head);
if (head != null) head.setPrev(e);
head = e;
if (tail == null) tail = e;
return item;
}
/**
* Removes and returns the element at the front of this queue. Traditionally,
* this is the only method available to remove data from the Queue.
*
* @return Element that was removed from the front of the Queue.
* @throws EmptyQueueException Thrown when the Queue does not have any
* elements to remove.
*/
public E dequeue() {
E res = null;
if (tail == null)
throw new EmptyQueueException("Error: can't dequeue empty queue");
else {
res = (E)tail.getVal();
if (tail.getPrev() == null) {
tail = null;
head = null;
} else {
tail = tail.getPrev();
tail.setNext(null);
}
}
size--;
return res;
}
/**
* Like {@link #dequeue()}, this returns the element at the front of the
* queue, but unlike {@link #dequeue} this method DOES NOT remove it from the
* queue.
*
* @return Element that is at the front of the queue.
* @throws EmptyQueueException Thrown when the Queuedoes not have any elements
* to remove.
*/
public E peek() {
E res = null;
if (tail == null)
{
throw new EmptyQueueException("Error: can't dequeue empty queue");
}
else {
res = (E)tail.getVal();
}
size--;
return res;
}
/**
* Returns the number of elements in this Queue.
*
* @return Items available in the Queue.
*/
public int size() {
return size;
}
/**
* Returns whether there are any elements in this Queue.
*
* @return True if the Queue does not have any elements; false otherwise.
*/
public boolean isEmpty() {
return size == 0;
}
}