C Program to Implement Priority Queue

Introduction

A priority queue is an abstract data type similar to a regular queue, but with an added priority element for each item. Elements with higher priority are dequeued before elements with lower priority, regardless of their insertion order. A priority queue can be implemented using various data structures, but in this example, we’ll use an array-based implementation with a simple sorting mechanism to manage priorities.

Example:

• Input: Insert elements (4, 1), (5, 2), (6, 0) into the priority queue.
• Output: Elements will be dequeued in the order (5, 2), (4, 1), (6, 0) based on their priorities.

Problem Statement

Create a C program that:

• Implements a priority queue using an array.
• Allows inserting elements with associated priority.
• Performs priority-based dequeue operations.
• Displays the contents of the priority queue.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions.
2. Define Constants and Global Variables: Define the maximum size of the queue and create a structure to hold elements with their priorities.
3. Implement the Priority Queue Operations:

• Insert: Add an element to the queue based on its priority.
• Delete/Dequeue: Remove and return the element with the highest priority.
• Display: Display all elements in the queue.
• IsEmpty: Check if the queue is empty.
• IsFull: Check if the queue is full.

4. Create a Main Function: In the main() function, allow the user to perform priority queue operations interactively.

C Program to Implement Priority Queue

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

#define MAX 100  // Maximum size of the priority queue

// Structure to represent an element with priority
struct Element {
    int data;
    int priority;
};

struct Element priorityQueue[MAX];
int size = 0;  // To keep track of the number of elements in the queue

// Function to check if the priority queue is empty
int isEmpty() {
    return size == 0;
}

// Function to check if the priority queue is full
int isFull() {
    return size == MAX;
}

// Function to insert an element with its priority into the priority queue
void insert(int data, int priority) {
    if (isFull()) {
        printf("Priority queue overflow! Cannot insert %d.\n", data);
        return;
    }

    int i = size - 1;

    // Move elements forward if they have a lower priority than the new element
    while (i >= 0 && priorityQueue[i].priority < priority) {
        priorityQueue[i + 1] = priorityQueue[i];
        i--;
    }

    // Insert the new element in its correct position
    priorityQueue[i + 1].data = data;
    priorityQueue[i + 1].priority = priority;
    size++;
    printf("Inserted %d with priority %d into the priority queue.\n", data, priority);
}

// Function to delete the element with the highest priority from the priority queue
int delete() {
    if (isEmpty()) {
        printf("Priority queue underflow! Cannot delete from an empty queue.\n");
        return -1;  // Return -1 to indicate queue underflow
    }

    // Element with the highest priority is at the front of the queue
    int data = priorityQueue[0].data;

    // Move all elements one step backward to fill the gap
    for (int i = 1; i < size; i++) {
        priorityQueue[i - 1] = priorityQueue[i];
    }

    size--;
    return data;
}

// Function to display the elements of the priority queue
void display() {
    if (isEmpty()) {
        printf("Priority queue is empty!\n");
        return;
    }

    printf("Priority queue elements (data, priority):\n");
    for (int i = 0; i < size; i++) {
        printf("%d (priority %d) ", priorityQueue[i].data, priorityQueue[i].priority);
    }
    printf("\n");
}

int main() {
    int choice, data, priority;

    while (1) {
        // Provide a menu for priority queue operations
        printf("\nPriority Queue Operations Menu:\n");
        printf("1. Insert\n");
        printf("2. Delete\n");
        printf("3. Display\n");
        printf("4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter data to insert: ");
                scanf("%d", &data);
                printf("Enter priority: ");
                scanf("%d", &priority);
                insert(data, priority);
                break;
            case 2:
                data = delete();
                if (data != -1) {
                    printf("Deleted element with highest priority: %d\n", data);
                }
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
            default:
                printf("Invalid choice! Please enter a valid option.\n");
        }
    }

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Define Constants and Global Variables

• The MAX constant defines the maximum size of the priority queue.
• The priorityQueue array is an array of Element structures, each holding data and its associated priority.
• The size variable keeps track of the number of elements in the queue.

Function to Check if the Priority Queue is Empty

• The isEmpty function returns 1 if the size is 0, indicating the queue is empty, otherwise returns 0.

Function to Check if the Priority Queue is Full

• The isFull function returns 1 if the size equals MAX, indicating the queue is full, otherwise returns 0.

Function to Insert an Element with its Priority into the Priority Queue

• The insert function adds a new element to the queue in its correct position based on priority. Elements with lower priority are shifted to the right to make space for the new element.

Function to Delete the Element with the Highest Priority from the Priority Queue

• The delete function removes the element with the highest priority, which is always at the front of the queue. After deletion, the elements are shifted left to fill the gap.

Function to Display the Elements of the Priority Queue

• The display function prints all elements in the priority queue, showing both the data and its associated priority.

Main Function

• The main function provides a menu-driven interface, allowing the user to perform priority queue operations such as insert, delete, and display interactively.

Output Example

Example Output:

Priority Queue Operations Menu:
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice: 1
Enter data to insert: 4
Enter priority: 1
Inserted 4 with priority 1 into the priority queue.

Priority Queue Operations Menu:
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice: 1
Enter data to insert: 5
Enter priority: 2
Inserted 5 with priority 2 into the priority queue.

Priority Queue Operations Menu:
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice: 3
Priority queue elements (data, priority):
5 (priority 2) 4 (priority 1) 

Priority Queue Operations Menu:
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice: 2
Deleted element with highest priority: 5

Conclusion

This C program demonstrates how to implement a priority queue using an array. It handles basic operations such as inserting elements with priorities, deleting the highest priority element, and displaying the queue contents. This example is helpful for understanding priority queue management in C programming.