A Linked Queue Implementation
File QueueADT.java contains a Java interface representing a queue ADT. In addition to enqueue(), dequeue(), and isEmpty(), this interface contains two methods that are not described in the book - isFull () and size().
//*********************************************************
// QueueADT.java
// The classic FIFO queue interface.
//*********************************************************
public interface QueueADT
{
//---------------------------------------------
// Puts item on end of queue.
//---------------------------------------------
public void enqueue(Object item);
//---------------------------------------------
// Removes and returns object from front of queue.
//---------------------------------------------
public Object dequeue();
//---------------------------------------------
// Returns true if queue is empty.
//---------------------------------------------
publicbooleanisEmpty();
//---------------------------------------------
// Returns true if queue is full.
//---------------------------------------------
publicbooleanisFull();
//---------------------------------------------
// Returns the number of elements in the queue.
//---------------------------------------------
File LinkedQueue.java contains a skeleton for a linked implementation of this interface; it also includes a toString() method that returns a string containing the queue elements, one per line.
// LinkedQueue.java
// A linked-list implementation of the classic FIFO queue interface.
//***********************************************************
public class LinkedQueue implements QueueADT
{
private Node front, back;
privateintnumElements;
//---------------------------------------------
// Constructor; initializes the front and back pointers
// and the number of elements.
//---------------------------------------------
publicLinkedQueue()
{
}
//---------------------------------------------
// Puts item on end of queue.
//---------------------------------------------
public void enqueue(Object item)
{
}
//---------------------------------------------
// Removes and returns object from front of queue.
//---------------------------------------------
public Object dequeue()
{
Object item = null;
}
//---------------------------------------------
// Returns true if queue is empty.
//---------------------------------------------
publicbooleanisEmpty()
{
}
//---------------------------------------------
// Returns true if queue is full, but it never is.
//---------------------------------------------
publicbooleanisFull()
{
}
//---------------------------------------------
// Returns the number of elements in the queue.
//---------------------------------------------
publicint size()
{
}
//---------------------------------------------
// Returns a string containing the elements of the queue
// from first to last
//---------------------------------------------
public String toString()
{
String result = "\n";
Node temp = front;
while (temp != null)
{
result += temp.getElement() + "\n";
temp = temp.getNext();
}
return result;
}
}
It depends on the Node class in Node.java. (This could also be defined as an inner class.) Collections
//************************************************************
// Node.java
// A general node for a singly linked list of objects.
//************************************************************
public class Node
{
private Node next;
private Object element;
//-------------------------------------------------------
// Creates an empty node
//-------------------------------------------------------
public Node()
{
next = null;
element = null;
}
//-------------------------------------------------------
// Creates a node storing a specified element
//-------------------------------------------------------
public Node(Object element)
{
next = null;
this.element = element;
}
//-------------------------------------------------------
// Returns the node that follows this one
//-------------------------------------------------------
public Node getNext()
{
return next;
}
//-------------------------------------------------------
// Sets the node that follows this one
//-------------------------------------------------------
public void setNext(Node node)
{
next = node;
}
//-------------------------------------------------------
// Returns the element stored in this node
//-------------------------------------------------------
public Object getElement()
{
return element;
}
//-------------------------------------------------------
// Sets the element stored in this node
//-------------------------------------------------------
public void setElement(Object element)
{
this.element = element;
}
}
File TestQueue.java contains a simple test program.
//**********************************************************
// TestQueue
// A driver to test the methods of the QueueADT implementations.
//**********************************************************
public class TestQueue
{
public static void main(String[] args)
{
QueueADT q = new LinkedQueue();
System.out.println("\nEnqueuing chocolate, cake, pie, truffles:");
q.enqueue("chocolate");
q.enqueue("cake");
q.enqueue("pie");
q.enqueue("truffles");
System.out.println("\nHere's the queue: " + q);
System.out.println("It contains " + q.size() + " items.");
System.out.println("\nDequeuing two...");
System.out.println(q.dequeue());
System.out.println(q.dequeue());
System.out.println("\nEnqueuing cookies, profiteroles, mousse, cheesecake,
ice cream:");
q.enqueue("cookies");
q.enqueue("profiteroles");
q.enqueue("mousse");
q.enqueue("cheesecake");
q.enqueue (" ice cream");
System.out.println("\nHere's the queue again: " + q);
System.out.println("Now it contains " + q.size() + " items.");
System.out.println("\nDequeuing everything in queue");
while (!q.isEmpty())
System.out.println(q.dequeue());
System.out.println("\nNow it contains " + q.size() + " items.");
if (q.isEmpty())
System.out.println("Queue is empty!");
else
System.out.println("Queue is not empty -- why not??!!");
}
}
Complete the method definitions in LinkedQueue.java. Some things to think about:
• In enqueue() and dequeue() you have to maintain both the front and back pointers - this takes a little thought. In particular, in enqueue be careful of the case where the queue is empty and you are putting the first item in. This case requires special treatment (think about why).
• The easiest way to implement the size() method is to keep track of the number of elements as you go with the numElements variable - just increment this variable when you enqueue an element and decrement it when you dequeue an element.
• A linked queue is never full, so isFull() always returns false. Easy! Study the code in TestQueue.java so you know what it is doing, then compile and run it. Correct any problems in your Linked Queue class.