Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 128

n elements in the queue if there are n array positions. This means that there are
n + 1 different states for the queue (0 through n elements are possible).
If the value of front is fixed, then n+ 1 different values for rear are needed
to distinguish among the n+ 1 states. However, there are only n possible values for
rear unless we invent a special case for, say, empty queues. This is an example of
the Pigeonhole Principle defined in Exercise 2.30. The Pigeonhole Principle states
that, given n pigeonholes and n + 1 pigeons, when all of the pigeons go into the
holes we can be sure that at least one hole contains more than one pigeon. In similar
manner, we can be sure that two of the n + 1 states are indistinguishable by the n
relative values of front and rear . We must seek some other way to distinguish
full from empty queues.
One obvious solution is to keep an explicit count of the number of elements in
the queue, or at least a Boolean variable that indicates whether the queue is empty
or not. Another solution is to make the array be of size n + 1, and only allow
n elements to be stored. Which of these solutions to adopt is purely a matter of the
implementor's taste in such affairs. My choice is to use an array of size n + 1.
Figure 4.27 shows an array-based queue implementation. listArray holds
the queue elements, and as usual, the queue constructor allows an optional param-
eter to set the maximum size of the queue. The array as created is actually large
enough to hold one element more than the queue will allow, so that empty queues
can be distinguished from full queues. Member maxSize is used to control the
circular motion of the queue (it is the base for the modulus operator). Member
rear is set to the position of the current rear element, while front is the position
of the current front element.
In this implementation, the front of the queue is defined to be toward the
lower numbered positions in the array (in the counter-clockwise direction in Fig-
ure 4.26), and the rear is defined to be toward the higher-numbered positions. Thus,
enqueue increments the rear pointer (modulus size ), and dequeue increments
the front pointer. Implementation of all member functions is straightforward.

4.3.2 Linked Queues

The linked queue implementation is a straightforward adaptation of the linked list.
Figure 4.28 shows the linked queue class declaration. Methods front and rear
are pointers to the front and rear queue elements, respectively. We will use a header
link node, which allows for a simpler implementation of the enqueue operation by
avoiding any special cases when the queue is empty. On initialization, the front
and rear pointers will point to the header node, and front will always point to
the header node while rear points to the true last link node in the queue. Method
enqueue places the new element in a link node at the end of the linked list (i.e.,
the node that rear points to) and then advances rear to point to the new link
node. Method dequeue removes and returns the first element of the list.