Rex Jaeschke is an independent computer consultant, seminar leader, and author of several books, including The Dictionary of Standard C (Professional Press, Horsham, PA). Readers are encouraged to submit column topics and suggestions to Rex at 2051 Swans Neck Way, Reston, VA, 22091 or via UUCP at rex@aussie.com.
Introduction
In recent installments I have discussed stacks. A stack is a last-in-first-out (LIFO) list since you remove items from the same end to which you add them. However, in certain kinds of applications it is desirable to service requests in the same order in which they arrive. That is, in a first-in-first-out (FIFO) manner. This requires a queue. Simply stated, a queue is a linear list in which additions take place at one end while removals take place at the other end. For the purpose of this discussion, we will say that additions are made to the tail of the queue and removals are taken from the head.The term queue is often used in relation to computing. For example, on many operating systems you can submit a job to the batch queue. You can also send print jobs to a print queue. In fact, there may be multiple queues for a single printer where each queue requires different stationary. An operator directs one queue to the printer and when those jobs are completed, he changes paper type/size and prints from the other queue.
I have discussed two primary ways of representing lists thus far: using contiguous arrays and non-contiguous linked lists. Let's look first at the array method as it applies to queues.
Representing Queues Using Arrays
To represent a queue of names where each name is no more than 10 characters long you can define a two-dimensional array of Nx11 characters. Such a queue can accommodate N entries each of length 10 (plus a trailing null character). Also, you could use a one-dimensional array of char pointers and allocate space for each string using malloc. This would potentially require less memory but would add to the runtime cost.To keep track of where it starts and ends, the queue needs a head and tail index pointer. And you also need a way to indicate if the queue is empty. In previous articles an index of -1 was used for this purpose. However, this meant that the index variables had to be signed just to handle this one negative value. In this installment, I reserve index zero for this purpose allowing the index variables to be unsigned, which is more natural. The array gives up its zeroth element, a small price.
If a number of nodes are added to the queue and none are deleted, the queue grows from the head in a backwards direction and the queue becomes full when the last array element is occupied. However, if one or more nodes is removed along the way, the head node is no longer element 1. Eventually, the head node could become the last element in the array. There are two ways to deal with this situation. In the first solution, when the last array element becomes occupied, shuffle the queue back to the start of the array so the head node is once again element 1. The problem here is that the queue could be quite long and this operation can be expensive. The second solution eliminates this problem simply by treating the array as being circular. That is, the first element logically follows the last. (Of course, in our case we need to skip over element 0 since it is never used, but this causes no hardship.)
Listing 1 contains the code.
The remove node function doesn't actually retain the string removed; it simply deletes the whole node. In a real application, you would save the value of the node being removed and use it somehow but that is of no importance here.
The list node option lists the current queue starting at the head. The node number printed is relative to the start of the queue and is not related to the array index it occupies.
The option to dump the queue is simply for debugging/interest; it allows you to see the raw array contents at any time.
Figure 1 contains some sample output when this program was run.
Next month we'll see how to represent a queue in a linked list.