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

FIGURE 11-2

(a) Before adding a new node to an empty chain; (b) after adding it

(a) (b)

firstNode lastNode firstNode lastNode

newNode

FIGURE 11-3

(a) Before, (b) during, and (c) after adding a new node to the end of a
nonempty chain that has a tail reference

(a)

lastNode newNode

(b)

After executing
lastNode.setNextNode(newNode);

lastNode newNode

(c)

After executing
lastNode = newNode;

newNode

lastNode

11.4

Retrieving the front entry. We get the entry at the front of the queue by accessing the data portion
of the first node in the chain. Like enqueue , getFront is an O(1) operation.

public T getFront()
{

T front = null ;
if (!isEmpty())
front = firstNode.getData();
return front;
} // end getFront

11.5

Removing the front entry. The method dequeue retrieves the entry at the front of the queue and
then removes the chain's first node by making firstNode reference the second node in the chain, as