Priority Queue using Linked List

Think of a priority queue as a unique type of linked list where every item comes with a ranking. It's quite different from your standard Linked List, which goes by the "FIFO" (First In, First Out) rule. In a priority queue, things get organized based on how crucial they are. The more important something is, the sooner it gets attention. Data items of higher significance go to the head of the queue in order of priority, from least important to most important. Normally, items that are of equal significance are handled in the order they were added to the queue. In many circumstances, including job organization, data compression for storage, and determining the optimum path for items on a network, priority queues are immensely helpful.

Explanation using Example:

Imagine we have a list of numbers: 5, 9, 12, 18.

Priority Queue with a List

Now, suppose we want to add a new number, which is 3. Since 3 has most priority than the other numbers, we'll place it at the very beginning of our list like this:

Next, we need to add the number 7 to the list. To do this, we'll go through the list one by one. First, we compare 7 with 3. Since 7 has less priority than 3, we won't insert it before 3. Next, we compare 7 with 5. Again, 7 is less prior than 5, so it won't go before 5 either. Now, we compare 7 with 9. Since 7 has more priority than 9, so will add before 9:

Implementation Overview:

#include <stdio.h>

#include <malloc.h>

typedef struct node {

    int priority;

    int info;

    struct node *link;

} NODE;

NODE *front = NULL;

// insert method

void insert(int data, int priority) {

    NODE *temp, *q;

    temp = (NODE *)malloc(sizeof(NODE));

    temp->info = data;

    temp->priority = priority;

    if (front == NULL || priority < front->priority) {

        temp->link = front;

        front = temp;

    } else {

        q = front;

        while (q->link != NULL && q->link->priority <= priority)

            q = q->link;

        temp->link = q->link;

        q->link = temp;

    }

}

// delete method

void del() {

    NODE *temp;

    if (front == NULL)

        printf("Queue Underflow\n");

    else {

        temp = front;

        printf("Deleted item is %d\n", temp->info);

        front = front->link;

        free(temp);

    }

}

// display method

void display() {

    NODE *ptr;

    ptr = front;

    if (front == NULL)

        printf("Queue is empty\n");

    else {

        printf("Queue is:\n");

        printf("Priority       Item\n");

        while (ptr != NULL) {

            printf("%5d        %5d\n", ptr->priority, ptr->info);

            ptr = ptr->link;

        }

    }

}

int main() {

    int choice, data, priority;

    do {

        printf("1.Insert\n");

        printf("2.Delete\n");

        printf("3.Display\n");

        printf("4.Quit\n");

        printf("Enter your choice: ");

        scanf("%d", &choice);

        switch (choice) {

            case 1:

                printf("Enter the data to add to the queue: ");

                scanf("%d", &data);

                printf("Enter its priority: ");

                scanf("%d", &priority);

                insert(data, priority);

                break;

            case 2:

                del();

                break;

            case 3:

                display();

                break;

            case 4:

                break;

            default:

                printf("Wrong choice\n");

        }

    } while (choice != 4);

    return 0;

}

Output:

Explanation:

The provided C code demonstrates the implementation of a priority queue using a linked list.

It includes functions for inserting elements (insert), deleting elements (del), and displaying the queue (display).

The highest-priority element is always listed first in the priority queue because of the way it is constructed.

It is easier to remove the item with the greatest priority when the elements are arranged in descending order of importance.

1. push() Function:

• The push() function is implemented as an insert in the code.
• It adds a new element to the priority queue along with its priority.
• The element with the highest priority is inserted at the beginning of the queue.
• When adding a new element, the code checks if the queue is empty or if the new element has higher priority than the current front element. If so, it inserts the element at the front. Otherwise, it traverses the list to find the correct position based on priority.

2. pop() Function:

• The pop() function is implemented as del in the code.
• It removes the element with the highest priority from the queue.
• This operation is efficient and takes constant time because the highest-priority element is always at the front.

3. peek() Function:

• The peek() function allows you to view the element with the highest priority without removing it from the queue.
• While the code does not explicitly implement a peek function, you can easily implement one by inspecting the front element (front) of the linked list.

Overview of Code:

The code defines a NODE structure to represent elements with data and priority fields.

The insert function adds elements while maintaining priority order. It checks if the queue is empty or iterates through the list to find the correct position for insertion.

The del function removes the highest-priority element from the front of the queue. It also checks for queue underflow.

You can look at the items in the priority queue by using the display function, which displays the components and their priorities.

The main function offers a simple user interface for interacting with the priority queue, allowing you to add components with priorities, remove elements, show the queue, and quit the program.

In conclusion, the provided C code effectively demonstrates a priority queue implemented using a linked list, fulfilling the key concepts and functions associated with priority queues.