4.2 Queue

The array implementation of a queue is also quite easy. Unlike with a stack, however, we do need some additional attributes (other than the size of the array, which is automatically maintained by an array ADT).

The internal representation is as follows:

struct _Queue
{
  struct ArrayADT *array; // where items are stored
  unsigned head; // index of the head
  unsigned size; // we need to maintain our own size
};

Conceptually, a queue has no inherent capacity limitations. The array ADT resizes automatically, so this is not a major concern. However, When the capacity of a circular queue changes, it may trigger the reorganization of data. We'll address this point later.

The head of a circular queue is the index of the next item to be removed. The ``tail'' of a circular queue is the index of the element to receive the next item. The ``tail'' is not explicitly represented because it can be computed as (head + size) % capacity.