C Program to implement priority queue using linked list

By | 11.04.2017

Priority queue using linked list


Write a C Program to implement priority queue using linked list. Here’s simple Program to implement priority queue using linked list in C Programming Language.


What is Queue ?


Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR, and the deletion of existing element takes place from the other end called as FRONT.

This makes queue as FIFO data structure, which means that element inserted first will also be removed first.


Basic Operations : :


  • enqueue() − add (store) an item to the queue.
  • dequeue() − remove (access) an item from the queue.
  • peek() − Gets the element at the front of the queue without removing it.
  • isfull() − Checks if the queue is full.
  • isempty() − Checks if the queue is empty.

Below is the source code for C Program to implement priority queue using linked list which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/*  C Program to implement priority queue using linked list  */

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

struct node
{
        int priority;
        int info;
        struct node *link;
}*front=NULL;

void insert(int item, int item_priority);
int del();
void display();
int isEmpty();

int main()
{
        int choice,item,item_priority;
        while(1)
        {
                printf("\n1.Insert\n");
                printf("2.Delete\n");
                printf("3.Display\n");
                printf("4.Quit\n");
                printf("\nEnter your choice : ");
                scanf("%d", &choice);

                switch(choice)
                {
                 case 1:
                        printf("\nInput the item to be added in the queue : ");
                        scanf("%d",&item);
                        printf("\nEnter its priority : ");
                        scanf("%d",&item_priority);
                        insert(item, item_priority);
                        break;
                 case 2:
                        printf("\nDeleted item is %d\n",del());
                        break;
                 case 3:
                        display();
                        break;
                 case 4:
                        exit(1);
                 default :
                        printf("\nWrong choice\n");
                }/*End of switch*/
        }/*End of while*/

        return 0;
}/*End of main()*/

void insert(int item,int item_priority)
{
        struct node *tmp,*p;

        tmp=(struct node *)malloc(sizeof(struct node));
        if(tmp==NULL)
        {
                printf("\nMemory not available\n");
                return;
        }
        tmp->info=item;
        tmp->priority=item_priority;
        /*Queue is empty or item to be added has priority more than first element*/
        if( isEmpty() || item_priority < front->priority )
        {
                tmp->link=front;
                front=tmp;
        }
        else
        {
                p = front;
                while( p->link!=NULL && p->link->priority<=item_priority )
                        p=p->link;
                tmp->link=p->link;
                p->link=tmp;
        }
}/*End of insert()*/

int del()
{
        struct node *tmp;
        int item;
        if( isEmpty() )
        {
                printf("\nQueue Underflow\n");
                exit(1);
        }
        else
        {
                tmp=front;
                item=tmp->info;
                front=front->link;
                free(tmp);
        }
        return item;
}/*End of del()*/

int isEmpty()
{
        if( front == NULL )
                return 1;
        else
                return 0;

}/*End of isEmpty()*/


void display()
{
        struct node *ptr;
        ptr=front;
        if( isEmpty() )
                printf("\nQueue is empty\n");
        else
        {       printf("\nQueue is :\n");
                printf("\nPriority       Item\n");
                while(ptr!=NULL)
                {
                        printf("%5d        %5d\n",ptr->priority,ptr->info);
                        ptr=ptr->link;
                }
        }
}/*End of display() */

OUTPUT : :


/*   C Program to implement priority queue using linked list  */

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 1

Input the item to be added in the queue : 1

Enter its priority : 1

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 1

Input the item to be added in the queue : 2

Enter its priority : 2

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 1

Input the item to be added in the queue : 3

Enter its priority : 2

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 3

Queue is :

Priority       Item
    1            1
    2            2
    2            3

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 1

Input the item to be added in the queue : 4

Enter its priority : 3

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 3

Queue is :

Priority       Item
    1            1
    2            2
    2            3
    3            4

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 2

Deleted item is 1

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 2

Deleted item is 2

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 2

Deleted item is 3

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 2

Deleted item is 4

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 3

Queue is empty

1.Insert
2.Delete
3.Display
4.Quit

Enter your choice : 4

Process returned 1

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post….

2.3 3 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments