1.6.3.1 Implementation as an Array1.6.3 Queues1.6.3 Queues1.6.3.2 Implementation as a Linked List

1.6.3.1 Implementation as an Array

A simple implementation of a queue is by an array. The index head refers to the position of the head element of the queue, the index tail refers to the first free array slot where new elements can be enqueued. The following diagram illustrates the array in the initial state (head equals tail):

Queue

After five elements have been inserted we have the following state:

Queue

After two elements have been dequeued we have the state:

Queue

Now we would like to have four more elements inserted. However, there are only three more free slots at the end of the array. What shall we do? The answer is simple: whenever one of the indices head or tail runs out of the right end of the array it moves back into the array at the left end:

Queue

We can achieve this effect by computing the new index as
  tail = (tail + 1) % n;

where n is the length of the array. By this trick we simulate a so called  circular array as illustrated by the following diagram:

Circular Array

At no time, the queue can hold more than n elements but, as long as this condition is met, we can perform arbitrary many queue operations.

The following Java class implements this idea:

  class ArrayQueue implements Queue
  {
    int[] a;

    int head = 0;
    int tail = 0;
    int count = 0;

    ArrayQueue(int n)
    {
      a = new int[n];
    }

    public int isEmpty()
    {
      return count == 0;
    }

    public int enqueue(int value)
    {
      if (count == a.length) System.exit(-1);
      count = count+1;
      a[tail] = value;
      tail = (tail+1) % a.length; 
    }

    public int dequeue()
    {
      count = count-1;
      int value = a[head];
      head = (head+1) % a.length;
      return value;
    }

    public int peek()
    {
      return a[head];
    }
  }

In this implementation, we use the counter count to keep track of the number of elements stored in the array. Otherwise, there is no possibility to distinguish the full state from the empty state: in both situation head equals tail. If the array gets full, we simply abort the program.

In a real implementation, a larger array should be allocated.

With this implementation, we can write a program

  Queue q = new ArrayQueue(8);
  q.enqueue(2); q.enqueue(3); q.enqueue(5); 
  int v0 = s.dequeue(); System.out.println(v0);
  int v1 = s.dequeue(); System.out.println(v1);

which gives output

  2
  3

Cyclic arrays are a popular implementation technique to implement queues, for instance in system software where incoming events have to be buffered until they can be processed in the order in which they have arrived. However, there are also other techniques as demonstrated by the following subsection.


© Wolfgang Schreiner; February 3, 2005

1.6.3.1 Implementation as an Array1.6.3 Queues1.6.3 Queues1.6.3.2 Implementation as a Linked List