Assignment 10
(Abstract data types)

A priority queue is like a queue except that insertion does not always occur at the end. Instead, the priority queue is kept sorted with respect to some key value. When a new record comes, it is inserted at the appropriate location of the queue so that this sorted order in maintained. If two or more records correspond to the same value of the key used for sorting, then the records that come earlier are positioned earlier in the list. To sum up, records with smaller key values are given higher priority than those with larger key values. For records with the same key value, the usual first-come-first-serve strategy is followed. Like standard queues, deletion from a priority queue always occurs at the front.

Make an implementation of priority queues using linked lists. More specifically, implement the following functions. Strictly follow the prototypes given. You may use a dummy node at the beginning of the list.

   typedef struct {
      int key;       /* the priority queue is kept sorted with respect to this key */
      int other;     /* some other value in the structure */
   } record;

   priorityQ init ();                       /* Return an empty priority queue */
   priorityQ insert ( priorityQ, record );  /* Insert a record in a priority queue */
   priorityQ delete ( priorityQ );          /* Delete the front of a priority queue */
   void print ( priorityQ );                /* Print the pairs stored in a priority queue from front to end */

Report the output of your program for the following main() function.

   #include <stdio.h>
   #include <stdlib.h>
   #include <time.h>

   #define NITER 100

   int main ()
   {
      priorityQ Q;
      int i;
      record a;

      srand((unsigned int)time(NULL));
      Q = init();
      for (i=0; i<NITER; ++i) {
         if (rand() % 4) {           /* insert with probability 3/4 */
            a.key = 1 + rand() % 9;  /* a random key between 1 and 9 */
            a.other = i;             /* use the iteration counter as other data */
            Q = insert(Q,a);
            printf("Operation: Enqueue(%d)\n", a.key);
         } else {                    /* delete with probability 1/4 */
            Q = delete(Q);
            printf("Operation: Dequeue\n");
         }
         printf("Q = "); print(Q); printf("\n");
      }
      exit(0);
   }