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

1 package weiss.nonstandard;
2
3 // ArrayQueue class
4 //
5 // CONSTRUCTION: with no initializer
6 //
7 // ******************PUBLIC OPERATIONS*********************
8 // void enqueue( x ) --> Insert x
9 // AnyType getFront( ) --> Return least recently inserted item
10 // AnyType dequeue( ) --> Return and remove least recent item
11 // boolean isEmpty( ) --> Return true if empty; else false
12 // void makeEmpty( ) --> Remove all items
13 // ******************ERRORS********************************
14 // getFront or dequeue on empty queue
15
16 public class ArrayQueue<AnyType>
17 {
18 public ArrayQueue( )
19 { /* Figure 16.12 */ }
20
21 public boolean isEmpty( )
22 { /* Figure 16.13 */ }
23 public void makeEmpty( )
24 { /* Figure 16.17 */ }
25 public AnyType dequeue( )
26 { /* Figure 16.16 */ }
27 public AnyType getFront( )
28 { /* Figure 16.16 */ }
29 public void enqueue( AnyType x )
30 { /* Figure 16.14 */ }
31
32 private int increment( int x )
33 { /* Figure 16.11 */ }
34 private void doubleQueue( )
35 { /* Figure 16.15 */ }
36
37 private AnyType [ ] theArray;
38 private int currentSize;
39 private int front;
40 private int back;
41
42 private static final int DEFAULT_CAPACITY = 10;
43 }

figure 16.10
Skeleton for the
array-based queue
class

We declare two methods in the private section. These methods are used
internally by the ArrayQueue methods but are not made available to the user of
the class. One of these methods is the increment routine, which adds 1 to its
parameter and returns the new value. Because this method implements wrap-
around, if the result would equal the array size it is wrapped around to zero.
This routine is shown in Figure 16.11. The other routine is doubleQueue , which

If the queue is full,
we must imple-
ment array doubling
carefully.