Algorithms Design   |   C language   |   Index

Queues

A queue is a dynamic data structure that allows deletion of elements and insertion of new elements.  More specifically, a queue is a data structure subject to the following rule of operation: every deletion deletes the oldest element of the queue, i.e., the element that has been in the structure for more time.

Therefore, the first object inserted into the queue is also the first to be deleted. This policy is known by the acronym FIFO (= First In First Out).

Array implementation

Suppose that our queue resides in an array qu[0..N-1].  (The nature of the elements of the array is irrelevant: they can be integers, bytes, pointers, etc.)  Let's say that the part of the array occupied by the queue is

qu[p..r-1] .

The first element of the queue is at index p and the last one at index r-1.  The queue is empty if  p == r  and full if  r == N.  The figure shows a queue that contains the numbers 111, 222, … , 666:

To delete (= de-queue) an element from the queue just do

   x = qu[p++];  

This is equivalent to the pair of instructions  x = qu[p]; p += 1;.  Of course you should not do this if the queue is empty.  To insert (= enqueue) an element y into the queue all you have to do is

   qu[r++] = y;  

This is equivalent to the pair of instructions  qu[r] = y; r += 1;.  Note how this code works correctly even when the queue is empty. Of course you should not do this if the queue is full, for otherwise the queue would overflow.

To help the human reader, we can present the operations of deletion and insertion as two small functions. If the elements of the queue are integer numbers, we can write

int dequeue (void) {
   return qu[p++];
}

void enqueue (int y) {
   qu[r++] = y;
}

(These two functions have the additional benefit of isolating the user of the queue from the specific names of variables and design decisions, like qu[p..r-1] instead of qu[p..r], for example.)

We are assuming here that the variables qu, p, r, and N are global, i.e., that they were defined outside the code of the functions.  To complete the package, we need three more functions: one to create a queue, one to check whether the queue is empty, and one to check whether the queue is full. (See the exercise below.)

Exercises 1

Application: distances in a graph

The ideia of a queue comes up naturally in the calculation of distances in a graph.  (A simplified version of the problem is the level traversal of a binary tree.)  Imagine N cities numbered form 0 to N-1 and interconnected by one-way roads. We shall say that a city j is a neighbor of a city i if there is a road from i to j. This neighborhood relation will be represented by a matrix A as follows:

A[i][j]  is  1  if j is a neighbor of i

and is 0 otherwise. Assume that the matrix has zeros on the diagonal, though this is irrelevant.  Here is an example where N is 6:

The distance from a city c to a city j is the least number of roads one must traverse to go from c to j.  (In general, the distance from c to j is not equal to the distance from j to c.)  Our problem is this:  given a city c,

find the distance from c to each of the other cities.

The distances can be stored in an array dist so that the distance from c to j is dist[j].  We must make a design decision to take care of the case in which it is impossible to go from c to j.  We could say that dist[j] is infinite in this case; but it is more convenient to say that dist[j] is N, since no actual distance can be greater than N-1.  For example, if we take c to be 3 in the example above, we shall have

Here is the ideia of an algorithm that uses a queue of active cities to solve our problem. A city i is active if dist[i] has already been computed but the roads that begin in i have not yet been all explored. In each iteration, the algorithm

deletes from the queue a city i and inserts into the queue all the neighbors of i whose distances have not yet been computed.

We show next the code that implements the ideia. (You may want to see first a draft in pseudocode.)  To simplify, the variables qu, p, r, and dist are global, that is, they are defined outside the code of the functions.

#define N 100
int qu[N], int p, r;
int dist[N];

void createqueue (void) {
   p = r = 0;
}

int isempty (void) {
   return p >= u;
}

int dequeue (void) {
   return qu[p++];
}

void enqueue (int y) {
   qu[r++] = y;
}

// This function receives a matrix A that
// represents the interconnections between
// cities 0..N-1 and fills in the array dist
// in such a way that dist[i] is the distance
// from city c to city i, for each i.

void distances (int A[][N], int c) {
   for (int j = 0; j < N; ++j)  dist[j] = N;
   dist[c] = 0;
   createqueue ();
   enqueue (c);

   while (! isempty ()) { 
      int i = dequeue ();
      for (int j = 0; j < N; ++j)
         if (A[i][j] == 1 && dist[j] >= N) {
            dist[j] = dist[i] + 1;
            enqueue (j);
         }
   }
}

(The code that manipulates the queue could be embedded into the function distances. The result would be shorter and more compact, but somewhat less readable.)

Exercises 2

Circular implementation

In the implementation above, the queue moves right in the array that houses it.  This can make it difficult to predict the value to which the parameter N must be set to prevent the queue from overflowing.  A circular implementation can help to make an overflow less likely.

Suppose that the elements of the queue are arranged in the array  qu[0..N-1]  in one of the following ways:  qu[p..r-1]  or  qu[p..N-1] qu[0..r-1].

We shall always have  0 ≤ p < N  and  0 ≤ r < N,  but cannot assume that p ≤ r .  The queue is

•  empty  if   r == p  and
•  full  if either  r+1 == p   or   r+1 == N and p == 0   (i.e., if (r+1) % N == p).

The position that precedes p will be always free so we can distinguish a full queue from an empty one.  With these conventions, the deletion of an element from the queue can be done as follows:

int dequeue (void) {
   int x = qu[p++];
   if (p == N) p = 0;
   return x;
}

(provided the queue is not empty).  The insertion of an object y into the queue can be done as follows:

void enqueue (int y) {
   qu[r++] = y;
   if (r == N) r = 0;
}

(provided the queue is not full).

Exercises 3

Implementation in a resizing array

It is not always possible to predict the amount of space a queue will need.  If the array that houses the queue has been allocated dynamically (using the malloc function), we can circumvent this difficulty by resizing the array:  every time the queue becomes full, we allocate a larger array and transfer the queue to this new array.  To avoid frequent resizings, we make the new array twice as large as the original.

Here is an example for the case in which the queue contains integer numbers (and the variables qu, p, r, and N are global):

void resize (void) {
   N *= 2;
   qu = realloc (qu, N * sizeof (int));
}

A homemade version, without realloc, could be written as follows:

void resize (void) {
   N *= 2;
   int *new;
   new = malloc (N * sizeof (int));
   for (int i = p; i < r; i++)
      new[i] = qu[i];
   free (qu);
   qu = new;
}

It would be even better to transfer qu[p..r-1] to new[0..r-p-1] and change the values of the variables p and r accordingly.

Exercises 4

Linked list implementation

How to operate a queue stored in a linked list? Let's say that the cells of the list are of type cell:

typedef struct record {
   int            contents; 
   struct record *next;
} cell;

We must make some design decisions.  We shall assume that our linked list is circular:  the next cell after the last one is the first one. We shall also assume that the list has a head cell; this cell will not be deleted even if the queue becomes empty.  The first element of the queue will be put into the second cell of the list and the last element will be in the cell that precedes the head.

A pointer qu points to the head cell. The queue is empty if qu->next == qu.  An empty queue can be created and initialized as follows:

cell *qu;
qu = malloc (sizeof (cell));
qu->next = qu;

We can now define the functions that manipulates the queue.  The deletion is easy:

// Deletes an element from queue qu and
// returns the contents of the deleted
// element. Assumes that the queue is
// not empty.

int dequeue (cell *qu) {
   cell *p;
   p = qu->next;  // first in queue
   int x = p->contents;
   qu->next = p->next;
   free (p);
   return x;  
}

The insertion uses a dirty trick:  it stores the new element in the original head cell and then creates a new head cell:

// Inserts a new element with contents y
// into queue qu. Returns the address of
// the head of the resulting queue.

cell *enqueue (int y, cell *qu) { 
   cell *new;
   new = malloc (sizeof (cell));
   new->next = qu->next;
   qu->next = new;
   qu->contents = y;
   return new;
}

Exercises 5