chap listsstacksand queues be no elements in the queueone elementtwoand so on at most there can be elements in the queue if there are array positions this means that there are different states for the queue ( through elements are possibleif the value of front is fixedthen different values for rear are needed to distinguish among the states howeverthere are only possible values for rear unless we invent special case forsayempty queues this is an example of the pigeonhole principle defined in exercise the pigeonhole principle states thatgiven pigeonholes and pigeonswhen all of the pigeons go into the holes we can be sure that at least one hole contains more than one pigeon in similar mannerwe can be sure that two of the states are indistinguishable by their 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 queueor at least boolean variable that indicates whether the queue is empty or not another solution is to make the array be of size and only allow elements to be stored which of these solutions to adopt is purely matter of the implementor' taste in such affairs my choice is to use an array of size figure shows an array-based queue implementation listarray holds the queue elementsand as usualthe queue constructor allows an optional parameter 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 allowso that empty queues can be distinguished from full queues method size is used to control the circular motion of the queue (it is the base for the modulus operatormethod rear is set to the position of the rear element in this implementationthe front of the queue is defined to be toward the lower numbered positions in the array (in the counter-clockwise direction in figure )and the rear is defined to be toward the higher-numbered positions thusenqueue increments the rear pointer (modulus size)and dequeue increments the front pointer implementation of all member functions is straightforward linked queues the linked queue implementation is straightforward adaptation of the linked list figure shows the linked queue class declaration methods front and rear are pointers to the front and rear queue elementsrespectively we will use header link nodewhich allows for simpler implementation of the enqueue operation by avoiding any special cases when the queue is empty on initializationthe front and rear pointers will point to the header nodeand front will always point to the header node while rear points to the true last link node in the queue method