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

16.

The ADT randomized queue is like a queue, but the removal and retrieval operations involve an entry chosen at
random instead of the entry at the beginning of the queue. These operations should return null if they encounter
an empty randomized queue.

a. Write a Java interface that specifies the methods for a randomized queue.
b. Define a class of randomized queues, named RandomizedQueue , that implements the interface you created
in Part a . Name the retrieval operation get instead of getFront .

A NSWERS TO S ELF -T EST Q UESTIONS

1.

The back of the queue is at the end of the chain. Since you add to the back of a queue, you need to add a node to
the end of the chain. A tail reference allows you to do this without first traversing the chain to locate its last node.
Thus, a tail reference enables an efficient enqueue operation.

2.

Entries in a bag are in no particular order within the bag and, thus, the array. Queue entries have an order relative
to one another that must be maintained.

3.

public void clear()
{

if (!isEmpty())
{

for ( int index = frontIndex; index != backIndex;
index = (index + 1) % queue.length)

{

queue[index] = null ;
} // end for
queue[backIndex] = null ;
} // end if
frontIndex = 0;
backIndex = queue.length - 1;
} // end clear

4.

public void clear()
{

while (!isEmpty())
dequeue();
} // end clear

This version of clear is easier to write than the version given in Question 3.

5.

Each enqueue operation needs to move all of the entries in the queue to vacate queue[0] before it adds a new entry.

6.

You place the new entry into the node that freeNode currently references. You then insert a new node after that
node and make freeNode reference the new node. The new node is now the unused node.

7.

You can repeatedly call dequeue until the queue is empty, as in the answer to Question 4. Or you can set the data
fields of each node in the queue to null and then set queueNode equal to freeNode .

8.

public T getBack()
{

T back = null ;
if (!isEmpty())
back = lastNode.getData();
return back;
} // end getBack