This blog is under construction

Sunday 26 May 2013

C Program To Implement Priority Queue

A priority queue is an abstract data type where the elements in the queue has a "priority" associated with it.  The order in which the elements are stored/added/removed is decided by the priority associated with the element.
  • The element with high priority will be processed before the low priority element.
  • If two elements have same priority, then the element added earlier in the queue would get processed.
Example Program To Implement Priority Queues (in C):


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

   #define MAXJOBS 100

   struct job {
        char name[100];
        int jobid, priority, order;
  };

   struct pQueue {
        struct job node[MAXJOBS];
        int front, rear;
  };

   int jobCount = 0;

  /* enqeue operation */
  void enqueue(struct pQueue *pq, struct job myJob) {
        struct job temp;
        int i, j;

        if (pq->front == MAXJOBS - 1) {
                printf("Enqueue operation failed - PQ is full\n");
                return;
        } else if (pq->front == -1) {
                pq->front = 0;
        }
        pq->rear++;
        pq->node[pq->rear] = myJob;
        for (i = pq->front; i < pq->rear; i++) {
                for (j = i + 1; j <= pq->rear; j++) {
                        /* place the node with high priority at the front */
                        if (pq->node[i].priority < pq->node[j].priority) {
                                temp = pq->node[i];
                                pq->node[i] = pq->node[j];
                                pq->node[j] = temp;
                        } else  if (pq->node[i].priority ==
                                        pq->node[j].priority) {
                                /*
                                 * if both elements have same priority, then the
                                 * element with lesser order is processed first
                                 */
                                if (pq->node[i].order > pq->node[j].order) {
                                        temp = pq->node[i];
                                        pq->node[i] = pq->node[j];
                                        pq->node[j] = temp;
                                }
                        }
                }
        }
        return;
  }

  /* dequeue operation */
  void dequeue(struct pQueue *pq) {
        if (pq->front == -1) {
                printf("Priority Queue underflow\n");
                return;
        }

        if (pq->front == pq->rear) {
                pq->front = pq->rear = -1;
        } else {
                printf("Dequeued Data:\n");
                printf("Job Name : %s\n", pq->node[pq->front].name);
                printf("Job ID   : %d\n", pq->node[pq->front].jobid);
                printf("Priority : %d\n", pq->node[pq->front].priority);
                printf("Order    : %d\n", pq->node[pq->front].order);
                pq->front++;
        }
        return;
  }

  /* dump the contents of the queue */
  void dumpQueue(struct pQueue *pq) {
        int i;
        if (pq->front == -1) {
                printf("Priority Queue Underflow\n");
                return;
        }

        printf("Job Name    JobID  Priority  Order\n");
        printf("-------------------------------------\n");
        for (i = pq->front; i <= pq->rear; i++) {
                printf("%8s%5d%9d%5d\n", pq->node[i].name, pq->node[i].jobid,
                        pq->node[i].priority, pq->node[i].order);
        }
        return;
  }

  int main() {
        struct pQueue pq;
        struct job myJob;
        int i, ch, order = 0;

        memset(&pq, 0, sizeof (struct pQueue));
        pq.front = pq.rear = -1;
        while (1) {
                printf("1. Add new Job(Enqueue)\t");
                printf("2. Dequeue\n3. Dump Queue\t");
                printf("4. Exit\nEnter your choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                getchar();
                                printf("Enter the job name:");
                                fgets(myJob.name, 100, stdin);
                                myJob.name[strlen(myJob.name) - 1] = '\0';
                                printf("Job ID: ");
                                scanf("%d", &myJob.jobid);
                                printf("Priority: ");
                                scanf("%d", &myJob.priority);
                                myJob.order = order++;
                                enqueue(&pq, myJob);
                                break;

                        case 2:
                                dequeue(&pq);
                                break;

                        case 3:
                                dumpQueue(&pq);
                                break;

                        case 4:
                                exit(0);
                        default:

                                printf("U have entered wrong option!!\n");

                                break;
                }
        }
        return 0;
  }



  Output: (Array Implementation Of Priority Queue - C Program)
  jp@jp-VirtualBox:~/$ ./a.out
  1. Add new Job(Enqueue) 2. Dequeue
  3. Dump Queue                 4. Exit
  Enter your choice:1

   Enter the job name:FLY
  Job ID: 1111
  Priority: 3333

   1. Add new Job(Enqueue) 2. Dequeue
  3. Dump Queue                 4. Exit
  Enter your choice:1

   Enter the job name:RUN
  Job ID: 2222
  Priority: 1111

   1. Add new Job(Enqueue) 2. Dequeue
  3. Dump Queue               4. Exit
  Enter your choice:1

   Enter the job name:WALK
  Job ID: 3333
  Priority: 2222

   1. Add new Job(Enqueue) 2. Dequeue
  3. Dump Queue                 4. Exit
  Enter your choice:3

   Job Name    JobID  Priority  Order
  -------------------------------------
         FLY         1111     3333    0
         WALK      3333     2222    2
         RUN        2222     1111    1

     1. Add new Job(Enqueue) 2. Dequeue
    3. Dump Queue                 4. Exit
    Enter your choice:2

     Dequeued Data:
    Job Name : FLY
    Job ID   : 1111
    Priority : 3333
    Order    : 0

   1. Add new Job(Enqueue) 2. Dequeue
  3. Dump Queue                 4. Exit
  Enter your choice:3

   Job Name    JobID  Priority  Order
  -------------------------------------
      WALK       3333     2222    2
       RUN         2222     1111    1

   1. Add new Job(Enqueue) 2. Dequeue
  3. Dump Queue                 4. Exit
  Enter your choice:4




Posted by at 07:54

1 comment:

  1. Unknown24 January 2022 at 10:45

    hi, can i know how to make if the we have 3 input that have same priority, which is 1, and 1 input with priority 2, and i want the order for input that have priority 1 first then 2, even though we key in input with priority 2 first.

    ReplyDelete

Subscribe to: Post Comments (Atom)