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

11.6

The rest of the class. The remaining public methods isEmpty and clear are straightforward:

public boolean isEmpty()
{

return (firstNode == null ) && (lastNode == null );
} // end isEmpty
public void clear()
{

firstNode = null ;
lastNode = null ;
} // end clear

Question 1 Why is a tail reference desirable when you use a chain of linked nodes to
implement a queue?

An Array-Based Implementation of a Queue

11.7

If we use an array queue to contain the entries in a queue, we could let queue[0] be the queue's front,
as Figure 11-6a shows. Here, frontIndex and backIndex are the indices of the entries at the queue's
front and back, respectively. But what happens when we remove the front entry? If we insist that the
new front entry be in queue[0] , we would need to shift each array element by one position toward the
beginning of the array. This arrangement would make the operation dequeue inefficient.
Instead, we can leave other array entries in their current positions when we remove the queue's
front entry. For example, if we begin with the array in Figure 11-6a and execute dequeue twice, the
array will be as shown in Figure 11-6b. Not moving array elements is attractive, but after several addi-
tions and removals, the array can look like the one pictured in Figure 11-6c. The queue entries have
migrated to the end of the array. The last available array location is allocated to the last entry added to
the queue. We could expand the array, but the queue has only three entries. Since most of the array is
unoccupied, why not use this space for future additions? In fact, that is just what we will do next.

A Circular Array
11.8

Once the queue reaches the end of the array, as in Figure 11-6c, we can add subsequent entries to
the queue at the beginning of the array. Figure 11-6d shows the array after two such additions to the
queue. We make the array behave as though it were circular , so that its first location follows its last
one. To do this, we use modulo arithmetic on the indices. Specifically, when we add an entry to the
queue, we first increment backIndex modulo the size of the array. For example, if queue is the
name of the array, we increment backIndex with the statement
backIndex = (backIndex + 1) % queue.length;
To remove an entry, we increment frontIndex modulo the size of the array in a similar fashion.

Question 2 When we removed an entry from an array-based bag, as we did in Chapter 2, we
replaced the removed entry with the last one in the array. Yet the implementation of the queue
just described does not do so. Explain this difference in implementations.