# 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:

 0 p r N-1 111 222 333 444 555 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

1. Queue implementation module (version 1).  Write a module queueofints.c to implement a queue of integers in a statically allocated array. The module must contain the functions  createqueueenqueuedequeueisempty,  and  isfull.  The array that houses the queue, as well as the indices that indicate the beginning and the end of the queue, must be global variables in the module.  Also write an interface queueofints.h for the module.  [Solution: ./solutions/fila2.html]
2. Write a function that will return the length (that is, the number of elements) of a queue.
3. Take a design decision different from the one above: suppose that the part of the array occupied by the queue is qu[p..r].  Write the code of the functions enqueue, dequeue, isempty, and isfull.
4. Take a design decision different from the one above: suppose that the part of the array occupied by the queue is qu[0..r].  Write the code of the functions enqueue, dequeue, isempty, and isfull.

## 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:

 0 1 2 3 4 5 0 0 1 0 0 0 0 1 0 0 1 0 0 0 2 0 0 0 0 1 0 3 0 0 1 0 1 0 4 1 0 0 0 0 0 5 0 1 0 0 0 0

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

 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..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

1. Size of the queue.  Is the space allocated to the array qu sufficient?  Can the instruction enqueue (j) cause an overflow of the queue?
2. Dynamic allocation.  Write a version of the function distances that takes the number of cities, N, as a parameter.
3. The algorithm is correct.  Prove that the function distances is correct, that is, prove that it computes the correct distances from c. The proof must show, for each city j, that (1) if dist[j] < N then there exists a path of length dist[j] from c to j and (2) no path from c to j is shorter than dist[j].
4. Write a version of the function distances that will return the distance from one given city a to another given city b.
5. Imagine a chessboard with m rows and n columns. Some squares are free while other are blocked. There is a robot in square (1,1), which is free. In each step, the robot can only move from a free square to a free square. In each step, it can only move north, east, south, or west. Help the robot find its way to the square (m,n).  (Hint: Add to the board a frame of blocked squares.)

## 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].

 0 p r N-1 111 222 333 444 555 666
 0 r p N-1 444 555 666 111 222 333

We shall always have  0p < N  and  0r < N,  but cannot assume that pr .  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

1. Imagine a circular implementation of a queue in an array qu[0..9] that contains
```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?

2. Consider a circular implementation of a queue in an array.  Write the code of the functions isempty and isfull. Write a function that will return the length (that is, the number of elements) of the queue.
3. Queue implementation module (version 2).  Write a module queueofints.c for the circular implementation of a queue of integers. The module must contain the functions  createqueueenqueuedequeueisempty,  and  isfull.  The array and the variables that mark the beginning and the end of the queue must be global in the module.  Also write an interface queueofints.h for the module.  (See one of the exercises above.)

## 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

1. Queue implementation module (version 3).  Write a module queueofints.c to implement a queue of integers in an array with resizing.  The module must contain the functions  createqueueenqueuedequeueisempty,  and  freequeue.  (In this version, the function isfull does not make sense.)  Treat the parameters of the queue as global variables in the module.  Also write an interface queueofints.h for the module.  [Solution: ./solutions/fila3.html]
2. Queue implementation module (version 4).  Write a module queueofchars.c to implement a queue of bytes.  (See the previous exercise.)

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

1. Implement a queue in a circular linked list without head cell. (Hint: Let r be the address of the last cell; the first cell will be pointed by r->next. The linked list will be empty if and only if r == NULL.)
2. Implement a queue in a noncircular linked list with head cell. You will have to maintain the address c of the head cell and the address r of the last cell.
3. Implement a queue in a noncircular linked list without head cell. You will have to maintain a pointer p to the first cell and a pointer r to the last.
4. Queue implementation module (version 5).  Write a module queueofints.c that will implement a queue of integer numbers in a linked list (you decide what kind of list).  The module must contain the functions  createqueueenqueuedequeueisempty,  and  freequeue.  Treat the parameters of the queue as global variables in the module.  Also write an interface queueofints.h for the module.  (See one of the exercises above.)
5. Doubly linked list.  Implement a queue in a doubly linked list without head cell. Use a pointer p to the first cell and a pointer r to the last.
6. Deque.  A deque allows insertion and deletion at any of the two extremes of the queue. Implement a deque (in an array or a linked list) and write the functions to operate the structure.