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).
Table of contents:
Suppose that our queue resides in an array qu[0..N1]. (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..r1] .
The first element of the queue is at index p and the last one at index r1. The queue is empty if p == r and full if r == N. The figure shows a queue that contains the numbers 111, 222, … , 666:
0  p  r  N1  
111  222  333  444  555  666 
To delete (= dequeue) 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..r1] 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.)
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 N1 and interconnected by oneway 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 N1. For example, if we take c to be 3 in the example above, we shall have
i  0  1  2  3  4  5 
dist[i]  2  3  1  0  1  6 
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..N1 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.)
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..N1] in one of the following ways: qu[p..r1] or qu[p..N1] qu[0..r1].
0  p  r  N1  
111  222  333  444  555  666 
0  r  p  N1  
444  555  666  111  222  333 
We shall always have 0 ≤ p < N and 0 ≤ r < N, but cannot assume that p ≤ r . The queue is
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).
16 17 18 19 20 11 12 13 14 15
Suppose that the first element of the queue is at index 5 and the last is at index 4. Is the queue full?
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..r1] to new[0..rp1] and change the values of the variables p and r accordingly.
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;
}