Queues

The key definition of a stack is LIFO. A queue is somewhat related but the key concept is First In, First Out, FIFO. The word queue must be of French origin given its spelling. In New York people stand on line at the theater, in America, people stand in line and in England, they queue up.

A queue needs two pointers, front and rear. It also uses four routines like stacks. Items are added at the rear and removed at the front. The four operations are; enqueue, dequeue, is_queue_empty and is_queue_full .

Uses

Queues are normally used in operating systems for scheduling various tasks. Often there is more than one for a given resource to allow priorities. They can be used as a kind of buffer, for message passing between processes and in simulations.

Implementation

This implementation uses our list code and is very simple. The code is also here
First we have an interface the defines the queue functions.
The list implementation of the interface is pretty simple.
And here is a driver that looks a lot like the stack driver.
Finally, the output from the example.

The queue is empty
There are 0 elements in the queue
There are 3 elements in the queue
Queue Contents
x= 1 y= 23
x= 2 y= 24
x= 3 y= 24
starting chop
removed element: x= 1 y= 23
Queue Contents
x= 2 y= 24
x= 3 y= 24

Linear Sequential Queues in an array

Queues can also be implemented in an array, but there are some complications due to the fixed size of the array. One common implementation is to have an array of the data objects of a size, QSIZE, and two indices, front and rear. These are both initialized to 0; As each item is added to the queue, the it is stored at the location stored in the rear pointer. This is then incremented. When an item is removed, it is copied from the location stored in the front pointer which is then incremented.

Notice what happens if many things are added to the queue so that the rear pointer points to the last element in the array but the front has moved from the first subscript. There are empty positions in the array but we can't use them because of the location of the rear pointer.

How to fix this?

Whenever the front and rear pointers are equal, the queue is empty. If we set front = rear = 0 at this point, the queue is still empty and we can reuse the space in the array. This is because we have returned to the initial conditions, where the front and rear are equal. This only puts off the problem, it doesn't solve it. The following section presents a technique to solve this.

Circular Queues

By using modulo arithmetic to increment the pointers instead of regular integer arithmetic, we can wrap the pointers around the ends of the array and thus use all the available space. Modulo arithmetic works as follows:
           a % b
returns the remainder of a divided by b. Thus, a % b will give a value between 0 and b-1.

Circular Queues Routines

These routines assume an array of items, numbered from 0 to QSIZE-1 named Q and two variables front and rear, both initialized to 0.

The addition and removal of items is similar to the above example, but due to using the modulo arithmetic, the pointers move around in the array and when they hit the physical end of the array, they wrap around to the beginning.