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

return front;
} // end removeFront

Aside from its name, this method differs from dequeue only in the addition of the else clause.
Figure 11-19 illustrates the effect of removeFront for a deque of at least two entries.

FIGURE 11-19

(a) A deque containing at least two entries; (b) after removing the
first node and obtaining a reference to the deque's new first entry

(a)

firstNode

Entry at front
of deque

(b)

firstNode

Entry at front
of deque

Returned
to client

front

The method removeBack has an analogous definition:

public T removeBack()
{

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

back = lastNode.getData();
lastNode = lastNode.getPreviousNode();
if (lastNode == null )
firstNode = null ;
else
lastNode.setNextNode( null );
} // end if
return back;
} // end removeBack
The implementations of removeFront and removeBack are each O(1).

11.39

Retrieving an entry. The method getFront has the same implementation as given in Segment 11.4
for a queue. The method getBack is analogous to getFront and is left as an exercise. Both
getFront and getBack are O(1) operations.

Question 8 Implement the method getBack for the ADT deque when a doubly linked chain
contains the deque's entries.