In this section, we present the ArrayQueue data structure, which implements a FIFO (first-in-first-out) queue; elements are removed (using the operation) from the queue in the same order they are added (using the operation).
Notice that an ArrayStack is a poor choice for an implementation of a FIFO queue. The reason is that we must choose one end of the list to add to and then remove from the other end. One of the two operations must work on the head of the list, which involves calling or with a value of . This gives a running time of .
To obtain an efficient array-based implementation of a queue, we first notice that the problem would be easy if we had an infinite array . We could maintain one index that keeps track of the next element to remove and an integer that counts the number of elements in the queue. The queue elements would always be stored in
Of course, the problem with this solution is that it requires an infinite array. An ArrayQueue simulates this by using a finite array and modular arithmetic. This is the kind of arithmetic used when we are talking about the time of day. For example 10 o'clock plus 5 hours gives 3 o'clock. Formally, we say that
More generally, for an integer and positive integer , is the unique integer such that for some integer . Less formally, the value is the remainder we get when we divide by . In many programming languages, including Java, the operator is represented using the symbol.2
Modular arithmetic is useful for simulating an infinite array, since always gives a value in the range . Using modular arithmetic we can store the queue elements at array locations
The only remaining thing to worry about is taking care that the number of elements in the ArrayQueue does not exceed the size of .
T[] a; int j; int n;
A sequence of and operations on an ArrayQueue is illustrated in Figure 2.2. To implement , we first check if is full and, if necessary, call to increase the size of . Next, we store in and increment .
|
boolean add(T x) { if (n + 1 > a.length) resize(); a[(j+n) % a.length] = x; n++; return true; }
To implement we first store so that we can return it later. Next, we decrement and increment (modulo ) by setting . Finally, we return the stored value of . If necessary, we may call to decrease the size of .
T remove() { if (n == 0) throw new NoSuchElementException(); T x = a[j]; j = (j + 1) % a.length; n--; if (a.length >= 3*n) resize(); return x; }
Finally, the operation is very similar to the operation of ArrayStack. It allocates a new array of size and copies
void resize() { T[] b = newArray(Math.max(1,n*2)); for (int k = 0; k < n; k++) b[k] = a[(j+k) % a.length]; a = b; j = 0; }
The following theorem summarizes the performance of the ArrayQueue data structure: