Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |

`QueueAsArray` objects comprise three fields--`array`, `head`, and `tail`.
The first, `array`, is an array of `object`s
that is used to hold the contents of the queue.
The objects contained in the queue
will be held in a contiguous range of array elements
as shown in Figure (a).
The fields `head` and `tail`
denote the left and right ends, respectively, of this range.

**Figure:** Array implementation of a queue.

In general, the region of contiguous elements will not necessarily occupy the leftmost array positions. As elements are deleted at the head, the position of the left end will change. Similarly, as elements are added at the tail, the position of the right end will change. In some circumstances, the contiguous region of elements will wrap around the ends of the array as shown in Figure (b).

As shown in Figure ,
the leftmost element is `array[head]`,
and the rightmost element is `array[tail]`.
When the queue contains only one element,
as shown in Figure (c).

Finally, Figure (b) shows that if the queue is empty,
the `head` position will actually be to the right
of the `tail` position.
However, this is also the situation which arises when the queue
is completely full!
The problem is essentially this:
Given an array of length *n*,
then and .
Therefore, the difference between the `head` and `tail`
satisfies .
Since there are only *n* distinct differences,
there can be only *n* distinct queue lengths, 0, 1, ..., *n*-1.
It is not possible to distinguish the queue which is empty
from the queue which has *n* elements
solely on the basis of the `head` and `tail` fields.

There are two options for dealing with this problem:
The first is to limit the number of elements in the queue to be at most *n*-1.
The second is to use another field, `count`,
to keep track explicitly of the actual number of elements in the queue
rather than to infer the number
from the `head` and `tail` variables.
The second approach has been adopted in the implementation given below.

Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.