Stacks and queues - Data Structures and Problem Solving Using Java - page 605

1 /**
2 * Return and remove the least recently inserted item
3 * from the queue.
4 * @return the least recently inserted item in the queue.
5 * @throws UnderflowException if the queue is empty.
6 */
7 public AnyType dequeue( )
8 {
9 if( isEmpty( ) )
10 throw new UnderflowException( "ArrayQueue dequeue" );
11 currentSize--;
12
13 AnyType returnValue = theArray[ front ];
14 front = increment( front );
15 return returnValue;
16 }
17
18 /**
19 * Get the least recently inserted item in the queue.
20 * Does not alter the queue.
21 * @return the least recently inserted item in the queue.
22 * @throws UnderflowException if the queue is empty.
23 */
24 public AnyType getFront( )
25 {
26 if( isEmpty( ) )
27 throw new UnderflowException( "ArrayQueue getFront" );
28 return theArray[ front ];
29 }

figure 16.16
The dequeue and
getFront routines for
the ArrayQueue class

1 /**
2 * Make the queue logically empty.
3 */
4 public void makeEmpty( )
5 {
6 currentSize = 0;
7 front = 0;
8 back = -1;
9 }

figure 16.17
The makeEmpty routine
for the ArrayQueue
class

linked list implementations

16.2

An alternative to the contiguous array implementation is a linked list. Recall
from Section 6.5 that in a linked list, we store each item in a separate object
that also contains a reference to the next object in the list.