Queue, Deque, and Priority Queue Implementations - Data Structures and Abstractions with Java - page 271

LISTING 11-1

An outline of a linked implementation of the ADT queue

/**

A class that implements a queue of objects by using
a chain of linked nodes.
@author Frank M. Carrano

*/
public class LinkedQueue<T> implements QueueInterface<T>
{

private Node firstNode; // references node at front of queue
private Node lastNode; // references node at back of queue

public LinkedQueue()
{

firstNode = null ;
lastNode = null ;
} // end default constructor

< Implementations of the queue operations go here. >
. . .

private class Node
{

private T data; // entry in queue
private Node next; // link to next node

< Constructors and the methods getData , setData , getNextNode , and setNextNode
are here. >
. . .
} // end Node
} // end LinkedQueue

11.3

Adding to the back. To add an entry to the back of the queue, we allocate a new node and add it to
the end of the chain. If the queue—and therefore the chain—is empty, we make both data fields,
firstNode and lastNode , reference the new node, as Figure 11-2 illustrates. Otherwise, both the
last node in the chain and the data field lastNode must reference the new node, as shown in
Figure 11-3. Thus, the definition of enqueue appears as follows:
public void enqueue(T newEntry)
{

Node newNode = new Node(newEntry, null );
if (isEmpty())
firstNode = newNode;
else
lastNode.setNextNode(newNode);
lastNode = newNode;
} // end enqueue
This operation requires no search and is independent of the other entries in the queue. Its per-
formance is thus O(1).