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.
Last month we introduced queues and showed how they can be represented in arrays. This month we'll see how they can be implemented in a linked list.
Representing Queues Using Linked Lists
Arrays are inherently restrictive in that they have a fixed size. And short of using (the potentially expensive) realloc to keep extending a dynamically allocated array, you must live with this limitation.This restriction can be removed by using a linked list instead. By allowing the nodes to be noncontiguous, we can allocate and free memory at runtime to handle addition and removal of nodes. In Listing 1, space for nodes is never actually freed; instead, it's added to a free node list for later use. As such, new memory is only allocated when the free list pool is completely used. The queue size then is only limited by available memory at runtime. Note that in this solution, the strings are not actually stored in the node but are also allocated dynamically.
Using a linked list avoids the need to have a circular queue altogether; we simply keep adding to the tail of the list and removing from the front. There is no fixed array size to work around.
The dump node option featured last month is missing since there is no fixed-size queue behind the scenes. The remove node function now actually returns the string being removed although the caller doesn't use it apart from displaying it.
Listing 1 contains the code. An example of some output appears in Figure 1.
An Issue Concerning scanf
For the most part, the program in Listing 1 (and the one in last month's installment) operates independent of the value of MAX_LEN; if the macro changes, the program changes with it. However, this is not quite complete. Note the call to scanf.
scanf("%10s", queue[tail_node]);Despite the use of MAX_LEN, the maximum length for the input is hard-coded in the edit mask string. Now if this were printf, the solution would be easy
printf("%*s", size, string);The printf family has a wild-card mechanism to allow the field width (and precision) to be specified at runtime. And while the scanf family also allows a "*" in edit masks, this, unfortunately, has a completely different meaning; it is used to suppress input conversion.The only way to provide the same flexibility using scanf, is to construct the edit mask from the individual parts. There are two ways to do this. The first involves using sprintf to create the edit mask at runtime (Listing 2) .
Another approach is to construct the edit mask string using the stringize preprocessor operator invented by ANSI C (Listing 3) .
Once the preprocessor has run, the call to scanf looks like the following:
scanf("%" "10" "s" , str);and the three adjacent string literals are concatenated by the compiler and treated as if you had written %10s directly.
Double-Ended Queues
For certain applications, a special kind of queue can be useful. It is called a double-end queue and is often abbreviated to deque (pronounced the same as deck). In such a queue, you can add and remove from either end. If, however, you can only add to one end but can remove from both, it is known as an input-restricted queue. Similarly, if you can add to either end but only remove from one end it is called an output-restricted queue.