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 .
- dequeue
return to the caller the front item on the stack and remove it
- enqueue(item)
put the item on the end of the queue
- is_queue_empty,full
return true if the condition holds, false otherwise
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.