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

shown in Figure 11-4. If the chain had only one node, dequeue would make the chain empty by set-
ting both firstNode and lastNode to null , as Figure 11-5 illustrates.
public T dequeue()
{

T front = null ;
if (!isEmpty())
{

front = firstNode.getData();
firstNode = firstNode.getNextNode();
if (firstNode == null )
lastNode = null ;
} // end if
return front;
} // end dequeue

Like enqueue , dequeue requires no search and is independent of the other entries in the queue.
Its performance is thus O(1).

FIGURE 11-4

(a) A queue of more than one entry; (b) after removing the entry
at the front of the queue

(a)

firstNode lastNode

Entry at front
of queue

Entry at back
of queue

(b)

firstNode lastNode

Entry at front
of queue

Entry at back
of queue

Returned
to client

front

FIGURE 11-5

(a) A queue of one entry; (b) after removing the entry at the
front of the queue

(a)

(b)

firstNode lastNode firstNode lastNode

Entry at front
of queue

Returned
to client

front