C Program to Implement Priority Queues

C Program to Implement Priority Queues

By /

A priority queue is a specialized type of queue in which each element has a priority. Unlike a standard FIFO queue, elements with higher priority are dequeued first. Priority queues are widely used in operating systems for task scheduling, network routing, and algorithms like Dijkstra’s shortest path. This article demonstrates how to implement a simple priority queue in C using arrays and linked lists, including a peek operation to view the highest-priority element without removing it.

Understanding the Problem

In a priority queue, each element has a priority value, usually an integer. When dequeuing, the element with the highest priority is removed first. The main challenge is inserting elements in the correct position based on their priority while ensuring dequeue operations always remove the highest-priority element. Proper handling ensures that tasks or data are processed in the intended order. The peek operation allows checking the highest-priority element without removing it.

Program 1: Priority Queue Using Arrays

This implementation uses a fixed-size array to store elements and their priorities. Elements are inserted so that the queue remains sorted by priority, with the highest-priority element at the front. A peek function is added to view the front element without dequeuing it.

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

#define MAX 5

typedef struct {
    int data;
    int priority;
} Node;

Node queue[MAX];
int size = 0;

int isFull() {
    return size == MAX;
}

int isEmpty() {
    return size == 0;
}

void enqueue(int data, int priority) {

    if (isFull()) {
        printf("Queue Overflow! Cannot insert %d\n", data);
        return;
    }

    int i = size - 1;

    while (i >= 0 && queue[i].priority < priority) {
        queue[i + 1] = queue[i];
        i--;
    }

    queue[i + 1].data = data;
    queue[i + 1].priority = priority;
    size++;

    printf("%d enqueued with priority %d\n", data, priority);

}

void dequeue() {

    if (isEmpty()) {
        printf("Queue Underflow! Nothing to dequeue.\n");
        return;
    }

    printf("%d dequeued from the queue\n", queue[0].data);

    for (int i = 1; i < size; i++) {
        queue[i - 1] = queue[i];
    }

    size--;

}

int peek() {

    if (isEmpty()) {
        printf("Queue is empty.\n");
        return -1;
    }

    return queue[0].data;

}

void display() {

    if (isEmpty()) {
        printf("Queue is empty.\n");
        return;
    }

    printf("Queue elements (data:priority): ");

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

    printf("\n");

}

int main() {

    enqueue(10, 2);
    enqueue(20, 3);
    enqueue(30, 1);
    display();

    printf("Peek element: %d\n", peek());

    dequeue();
    display();

    enqueue(40, 4);
    display();

    printf("Peek element: %d\n", peek());

    return 0;

}

In this array-based priority queue, elements are inserted in descending order of priority. The dequeue function always removes the highest-priority element at the front. The peek function allows accessing the front element without removing it, which is useful for checking the next task or element to process. Insertion requires shifting lower-priority elements, making it O(n), while dequeue and peek are O(1).

Program 2: Priority Queue Using Linked List

A linked list allows dynamic memory allocation, making the queue flexible in size. Nodes are inserted in order of priority so that the highest-priority element is always at the front. A peek function is included to view the front element without removal.

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

typedef struct Node {
    int data;
    int priority;
    struct Node *next;
} Node;

Node *front = NULL;

void enqueue(int data, int priority) {

    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->priority = priority;
    newNode->next = NULL;

    if (!front || priority > front->priority) {

        newNode->next = front;
        front = newNode;

    } else {

        Node *temp = front;

        while (temp->next && temp->next->priority >= priority) {
            temp = temp->next;
        }

        newNode->next = temp->next;
        temp->next = newNode;

    }

    printf("%d enqueued with priority %d\n", data, priority);

}

void dequeue() {

    if (!front) {
        printf("Queue Underflow! Nothing to dequeue.\n");
        return;
    }

    Node *temp = front;

    printf("%d dequeued from the queue\n", front->data);

    front = front->next;

    free(temp);

}

int peek() {

    if (!front) {
        printf("Queue is empty.\n");
        return -1;
    }

    return front->data;

}

void display() {

    if (!front) {
        printf("Queue is empty.\n");
        return;
    }

    Node *temp = front;

    printf("Queue elements (data:priority): ");

    while (temp) {
        printf("%d:%d ", temp->data, temp->priority);
        temp = temp->next;
    }

    printf("\n");

}

int main() {

    enqueue(10, 2);
    enqueue(20, 3);
    enqueue(30, 1);
    display();

    printf("Peek element: %d\n", peek());

    dequeue();
    display();

    enqueue(40, 4);
    display();

    printf("Peek element: %d\n", peek());

    return 0;

}

In this linked-list priority queue, nodes are inserted in descending order of priority. The dequeue function always removes the front node, which is the highest-priority element. The peek function returns the front element without removal, making it easy to check the next task. Dynamic memory allocation allows the queue to grow as needed without worrying about a fixed size.

FAQs

Q1: Can a priority queue be implemented using a linked list?
Yes. Linked lists allow dynamic memory allocation, and insertion can be done based on priority without array limits.

Q2: Can multiple elements have the same priority?
Yes. Elements with the same priority are typically dequeued in FIFO order.

Q3: What is the time complexity of insertion and deletion?

  • Array-based: Insertion is O(n), deletion and peek are O(1).
  • Linked-list: Insertion is O(n) in the worst case, deletion and peek are O(1).

Q4: Are there more efficient ways to implement a priority queue?
Yes. Using a binary heap reduces insertion and deletion time to O(log n), which is more efficient for large datasets.

Q5: What is the purpose of the peek operation?
peek() allows viewing the highest-priority element without removing it from the queue, useful for task scheduling and inspection.

Conclusion

Priority queues are essential for applications that require ordering based on importance rather than arrival time. Array-based implementations are simple and suitable for small queues, while linked lists or heaps provide more flexibility and efficiency for larger or dynamic data. Proper handling of insertion and deletion ensures the priority queue operates correctly.

References & Additional Resources

A curated collection of textbooks and tutorials for learning priority queues and their implementations in C.

  1. Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference covering C fundamentals, arrays, and pointers essential for implementing priority queues.
  2. Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of priority queues, heaps, and their implementation in C with practical examples.
  3. GeeksforGeeks: Priority Queue in C – Introduction to priority queues and their usage with C examples.
  4. Programiz: Heap-Based Priority Queue – Practical guide to implementing priority queues using heaps in C.
  5. TutorialsPoint: Priority Queue Using Arrays – Step-by-step explanation of array-based priority queue implementation.
  6. C Standard Library Documentation – Official reference for standard C functions and libraries helpful in implementing priority queues.

Related Posts

Scroll to Top