CS 210 Queue Code

Queue Algorithms, Part 2

This set of algorithms deals with queues implemented using linked lists. Error is a routine that takes a type of error as an argument and does whatever is appropriate.

Linked Sequential Queues

These routines assume a record as described below and two pointer variables front and rear, initialized to NULL. The routine createnode() sets its argument to be a NULL pointer when there is no more space
         struct Q {
              int stuff;   /* we don't care exactly what this is 
              struct Q *next;
             };

         void addq(int item) {
         /* this adds item to the rear of the queue  */
            struct Q *x;
1.            x=createnode(x);
2.            if (x != NULL) {   /* this is the check for a 'full' queue  */
3.               x->stuff = item;
4.               x->next = NULL;
5.               if (rear == NULL)   /* first one  */
6.                  rear = front = x;
7.               else {
8.                  rear->next = x;
9.                  rear = x;
10.              }
               }
11.            else
12.               error(queue_full);
         } /* addq */

         int getq() {
         /* this returns the item at the front of the queue  */
            int x;
            struct Q *y;
1.            if (front != NULL) {
2.               y = front;
3.               front = front->next;
4.               x=y->thing;
5.               free(y);
6.               return(x);
              }
7.            else
8.               error(queue_empty);
         } /* getq */

Linked Circular Queues

There are no algorithms here since the reason we built circular sequential queues was to reuse the memory. The fact that we get new space as needed and return it in linked linear queues makes this unnecessary.