Getting Queued with an ADT

I l @ ve RuBoard

Getting Queued with an ADT

The abstract data type approach to programming in C, as you've seen, involves the following three steps:

1. Describing a type, including its operations, in an abstract, general fashion.

2. Devising a function interface to represent the new type.

3. Writing detailed code to implement the interface.

You've seen this approach applied to a simple list. Now, apply it to something slightly more complex: the queue.

Defining the Queue Abstract Data Type

A queue is a list with two special properties. First, new items can be added only to the end of the list. In this respect, the queue is like the simple list. Second, items can be removed from the list only at the beginning. You can visualize a queue as a line of people buying tickets to a theater. You join the line at the end, and you leave the line at the front, after purchasing your tickets. A queue is a first in, first out (FIFO) data form, just the way a movie line is (if no one cuts into the line). Once again, let's frame an informal, abstract definition, as shown here:

Type Name :	Queue
Type Properties:	Can hold an ordered sequence of items.
Type Operations:	Initialize queue to empty. Determine whether queue is empty. Determine whether queue if full. Determine number of items in the queue. Add item to rear of queue. Remove and recover item from front of queue.

Defining an Interface

The interface definition will go into a file called queue.h . We'll use C's typedef facility to create names for two types: Item and Queue . The exact implementation for the corresponding structures should be part of the queue.h file, but conceptually, designing the structures is part of the detailed implementation stage. For the moment, just assume that the types have been defined and concentrate on the function prototypes .

First, consider initialization. It involves altering a Queue type, so the function should take the address of a Queue as an argument:

 void InitializeQueue (Queue * pq); 

Next , determining whether the queue is empty or full involves a function that should return a true or false value. Because the function doesn't alter the queue, it can take a Queue argument. On the other hand, it can be faster and less memory intensive to just pass the address of a Queue , depending on how large a Queue -type object is. Let's try that approach this time. To indicate that these functions don't change a queue, you can, and should, use the const qualifier:

 BOOLEAN FullQueue(const Queue * pq); BOOLEAN EmptyQueue(const Queue * pq); 

Paraphrasing, the pointer pq points to a Queue data object that cannot be altered through the agency of pq . You can define a similar prototype for a function that returns the number of items in a queue.

 int QueueItems(const Queue * pq); 

Adding an item to the end of the queue involves identifying the item and the queue. This time the queue is altered, so using a pointer is necessary, not optional. The function could be type void , or you can use the return value to indicate whether the operation of adding an item succeeded. Let's take the second approach:

 BOOLEAN EnQueue(Item item, Queue * pq); 

Finally, removing an item can be done several ways. If the item is defined as a structure or as one of the fundamental types, it could be returned by the function. The function argument could be either a Queue or a pointer to a Queue . Therefore, one possible prototype is this:

 Item DeQueue(Queue q); 

However, the following prototype is a bit more general:

 BOOLEAN DeQueue(Item * pitem, Queue * pq); 

The item removed from the queue goes to the location pointed to by the pitem pointer, and the return value indicates whether the operation succeeded.

Implementing the Interface Data Representation

The first step is deciding what C data form to use for a queue. One possibility is an array. The advantages to arrays are that they're easy to use and that adding an item to the end of an array's filled portion is easy. The problem comes with removing an item from the front of the queue. In the analogy of people in a ticket line, removing an item from the front of the queue consists of copying the value of the first element of the array (simple), and then moving each item left in the array one element toward the front. That is easy to program, but it wastes a lot of computer time (see Figure 17.6).

Figure 17.6. Using an array as a queue.

A second way to handle the removal problem in an array implementation is to leave the remaining elements where they are and, instead, change which element you call the front (see Figure 17.7). This method's problem is that the vacated elements become dead space, so the available space in the queue keeps decreasing .

Figure 17.7. Redefining the front element.

A clever solution to the dead space problem is to make the queue circular . This means wrapping around from the end of the array to the beginning. That is, consider the first element of the array as immediately following the last element so that when you reach the end of the array, you can start adding items to the beginning elements if they have been vacated (see Figure 17.8). You can imagine drawing the array on a strip of paper, and then pasting one end of the array to the other to form a band . Of course, you now have to do some fancy bookkeeping to make sure the end of the queue doesn't pass the front.

Figure 17.8. A circular queue.

Yet another solution is to use a linked list. This has the advantage that removing the front item doesn't require moving all the other items. Instead, you just reset the front pointer to point to the new first element. Because we've already been working with linked lists, we'll take this tack. To test our ideas, we'll start with a queue of integers:

 typedef int Item; 

A linked list is built from nodes, so let's define a node next:

 typedef struct node {    Item item;    struct node * next; } Node; 

For the queue, you need to keep track of the front and rear items. You can use pointers to do this. Also, you can use a counter to keep track of the number of items in a queue.

 typedef struct queue {    Node * front;   /* pointer to front of queue */    Node * rear;    /* pointer to rear of queue  */    int items;      /* number of items in queue  */ } Queue; 

Note that a Queue is a structure with three members , so the earlier decision to use pointers to queues instead of entire queues as arguments is a time and space saver.

Next, think about the size of a queue. With a linked list, the amount of available memory sets the limit, but often a much smaller size is more appropriate. For example, you might use a queue to simulate airplanes waiting to land at an airport. If the number of waiting planes gets too large, new arrivals might be rerouted to other airports. We'll set a maximum queue size of 10. Listing 17.6 contains the definitions and prototypes for the queue interface. It leaves open the exact definition of the Item type. When using the interface, you would insert the appropriate definition for your particular program.

Listing 17.6 The queue.h interface header file.

 /* queue.h -- interface for a queue */ #ifndef _QUEUE_H_ #define _QUEUE_H_ /* INSERT ITEM TYPE HERE */ /* INSERT ITEM TYPE HERE */ /* FOR EXAMPLE, */ typedef int Item; /* OR typedef struct item {int gumption; int charisma;} Item; */ #define MAXQUEUE 10 typedef enum boolean {False, True} BOOLEAN; typedef struct node {    Item item;    struct node * next; } Node; typedef struct queue {    Node * front;  /* pointer to front of queue  */    Node * rear;   /* pointer to rear of queue   */    int items;     /* number of items in queue   */ } Queue; /* operation:        initialize the queue                       */ /* precondition:     pq points to a queue                       */ /* postcondition:    queue is initialized to being empty        */ void InitializeQueue(Queue * pq); /* operation:        check if queue is full                     */ /* precondition:     pq points to previously initialized queue  */ /* postcondition:    returns True if queue is full, else False  */ BOOLEAN FullQueue(const Queue * pq); /* operation:        check if queue is empty                    */ /* precondition:     pq points to previously initialized queue  */ /* postcondition:    returns True if queue is empty, else False */ BOOLEAN EmptyQueue(const Queue *pq); /* operation:        determine number of items in queue         */ /* precondition:     pq points to previously initialized queue  */ /* postcondition:    returns number of items in queue           */ int QueueItems(const Queue * pq); /* operation:        add item to rear of queue                  */ /* precondition:     pq points to previously initialized queue */ /*                   item is to be placed at rear of queue      */ /* postcondition:    if queue is not empty, item is placed at   */ /*                   rear of queue and function returns         */ /*                   True; otherwise, queue is unchanged and    */ /*                   function returns False                     */ BOOLEAN EnQueue(Item item, Queue * pq); /* operation:        remove item from front of queue            */ /* precondition:     pq points to previously initialized queue  */ /* postcondition:    if queue is not empty, item at head of     */ /*                   queue is copied to *pitem and deleted from */ /*                   queue, and function returns True; if the   */ /*                   operation empties the queue, the queue is  */ /*                   reset to empty. If the queue is empty to   */ /*                   begin with, queue is unchanged and the     */ /*                   function returns False                     */ BOOLEAN DeQueue(Item *pitem, Queue * pq); #endif 

Implementing the Interface Functions

Now we can get down to writing the interface code. First, initializing a queue to empty means setting the front and rear pointers to NULL and setting the item count (the items member) to :

 void InitializeQueue(Queue * pq) {    pq->front = pq->rear = NULL;    pq->items = 0; } 

Next, the items member makes it easy to check for a full queue or empty queue and to return the number of items in a queue:

 BOOLEAN FullQueue(const Queue * pq) {    return pq->items == MAXQUEUE; } BOOLEAN EmptyQueue(const Queue * pq) {    return pq->items == 0; } int QueueItems(const Queue * pq) {    return pq->items; } 

Adding an item to the queue involves the following steps:

1. Creating a new node.

2. Copying the item to the node.

3. Setting the node's next pointer to NULL , identifying the node as the last in the list.

4. Setting the current rear node's next pointer to point to the new node, linking the new node to the queue.

5. Setting the rear pointer to the new node, making it easy to find the last node.

6. Adding 1 to the item count.

Also, the function has to handle two special cases. First, if the queue is empty, the front pointer should be set to point to the new node. That's because when there is just one node, that node is both the front and the rear of the queue. Second, if the function is unable to obtain memory for the node, it should do something. Because we envision using small queues, such failure should be rare, so we'll simply have the function terminate the program if the program runs out of memory.

 BOOLEAN EnQueue(Item item, Queue * pq) {    Node * pnew;    if (FullQueue(pq))       return False;    pnew = (Node *) malloc( sizeof(Node));    if (pnew == NULL)    {       fprintf(stderr,"Unable to allocate memory!\n");       exit(1);    }    CopyToNode(item, pnew);    pnew->next = NULL;    if (EmptyQueue(pq))       pq->front = pnew;            /* item goes to front     */    else       pq->rear->next = pnew;       /* link at end of queue   */    pq->rear = pnew;                /* record location of end */    pq->items++;                    /* one more item in queue */    return True; } 

The CopyToNode() function is a static function to handle copying the item to a node:

 static void CopyToNode(Item item, Node * pn) {    pn->item = item; } 

Removing an item from the front of the queue involves the following steps:

1. Copying the item to a waiting variable.

2. Freeing the memory used by the vacated node.

3. Resetting the front pointer to the next item in the queue.

4. Resetting the front and rear pointers to NULL if the last item is removed.

5. Decrementing the item count.

Here's code that does all these things:

 BOOLEAN DeQueue(Item * pitem, Queue * pq) {    Node * pt;    if (EmptyQueue(pq))       return False;    CopyToItem(pq->front, pitem);    pt = pq->front;    pq->front = pq->front->next;    free(pt);    pq->items--;    if (pq->items == 0)       pq->rear = NULL;    return True; } 

There are a couple of pointer facts you should note. First, the code doesn't explicitly set the front pointer to NULL when the last item is deleted. That's because it already sets the front pointer to the next pointer of the node being deleted. If that node is the last node, its next pointer is NULL , so the front pointer gets set to NULL . Second, the code uses a temporary pointer pt to keep track of the deleted node's location. That's because the official pointer to the first node ( pq->front ) gets reset to point to the next node, so without the temporary pointer, the program would lose track of which block of memory to free.

Keeping Your ADT Pure

After you've defined an ADT interface, you should use only the functions of the interface to handle the data type. Note, for instance, that Dequeue() depends on the EnQueue() function doing its job of setting pointers correctly and setting the next pointer of the rear node to NULL . If, in a program using the ADT, you decided to manipulate parts of the queue directly, you might mess up the coordination between the functions in the interface package.

Listing 17.7 shows all the functions of the interface, including the CopyToItem() function used in EnQueue() .

Listing 17.7 The queue.c implementation file.

 /* queue.c -- the Queue type implementation*/ #include <stdio.h> #include <stdlib.h> #include "queue.h" /* local functions */ static void CopyToNode(Item item, Node * pn); static void CopyToItem(Node * pn, Item * pi); void InitializeQueue(Queue * pq) {    pq->front = pq->rear = NULL;    pq->items = 0; } BOOLEAN FullQueue(const Queue * pq) {    return pq->items == MAXQUEUE; } BOOLEAN EmptyQueue(const Queue * pq) {    return pq->items == 0; } int QueueItems(const Queue * pq) {    return pq->items; } BOOLEAN EnQueue(Item item, Queue * pq) {    Node * pnew;    if (FullQueue(pq))       return False;    pnew = (Node *) malloc( sizeof(Node));    if (pnew == NULL)    {       fprintf(stderr,"Unable to allocate memory!\n");       exit(1);    }    CopyToNode(item, pnew);    pnew->next = NULL;    if (EmptyQueue(pq))       pq->front = pnew;    else       pq->rear->next = pnew;    pq->rear = pnew;    pq->items++;    return True; } BOOLEAN DeQueue(Item * pitem, Queue * pq) {    Node * pt;    if (EmptyQueue(pq))       return False;    CopyToItem(pq->front, pitem);    pt = pq->front;    pq->front = pq->front->next;    free(pt);    pq->items--;    if (pq->items == 0)       pq->rear = NULL;    return True; } static void CopyToNode(Item item, Node * pn) {    pn->item = item; } static void CopyToItem(Node * pn, Item * pi) {    *pi = pn->item; } 

Testing the Queue

It's a good idea to test a new design, like the queue package, before inserting it into a critical program. One approach to testing is writing a short program, sometimes called a driver , whose sole purpose is to test the package. For instance, Listing 17.8 uses a queue that enables you to add and delete integers. Before using the program, make sure the following line is present in queue.h :

 typedef int Item; 

Remember, too, that you have to link queue.c and use_q.c .

Listing 17.8 The use.qc program.

 /* use_q.c -- driver testing the Queue interface */ /* compile with queue.c                          */ #include <stdio.h> #include "queue.h"  /* defines Queue, Item       */ int main(void) {    Queue line;    Item temp;    char ch;    InitializeQueue(&line);    puts("Testing the Queue interface. Type a to add a value,");    puts("type d to delete a value, and type q to quit.");    while ((ch = getchar()) != `q')    {       if (ch != `a' && ch != `d')   /* ignore other input */          continue;       if ( ch == `a')       {          printf("Integer to add: ");          scanf("%d", &temp);          if (!FullQueue(&line))          {             printf("Putting %d into queue\n", temp);             EnQueue(temp,&line);          }          else             puts("Queue is full!");       }       else       {          if (EmptyQueue(&line))             puts("Nothing to delete!");          else          {             DeQueue(&temp,&line);             printf("Removing %d from queue\n", temp);          }       }       printf("%d items in queue\n", QueueItems(&line));       puts("Type a to add, d to delete, q to quit:");    }    puts("Bye!");    return 0; } 

Here is a sample run. You should also test to see that the implementation behaves correctly when the queue is full.

 Testing the Queue interface. Type a to add a value, type d to delete a value, and type q to quit.  a  Integer to add:  40  Putting 40 into queue 1 items in queue Type a to add, d to delete, q to quit:  a  Integer to add:  20  Putting 20 into queue 2 items in queue Type a to add, d to delete, q to quit:  a  Integer to add: 55 Putting 55 into queue 3 items in queue Type a to add, d to delete, q to quit:  d  Removing 40 from queue 2 items in queue Type a to add, d to delete, q to quit:  d  Removing 20 from queue 1 items in queue Type a to add, d to delete, q to quit:  d  Removing 55 from queue 0 items in queue Type a to add, d to delete, q to quit:  d  Nothing to delete! 0 items in queue Type a to add, d to delete, q to quit:  q  Bye! 

I l @ ve RuBoard