Priority Queue


What is a Priority Queue?

A priority queue is a special type of queue where:

  • Each element is associated with a priority.

  • Higher priority elements are served before lower priority elements.

  • If two elements have the same priority, they are served according to their order of insertion (just like a normal queue).

Example:

Imagine an emergency room:

  • Critical patients are treated first (high priority).

  • Normal cases are treated later (low priority).

How to Implement Priority Queue using Linked List?

We use a linked list where:

  • Each node contains:

    • data (the value)

    • priority (the priority number)

    • next (pointer to the next node)

  • Insertion (enqueue) is done in such a way that higher priority nodes come earlier.

  • Deletion (dequeue) always happens from the front (highest priority).



Algorithms for Priority Queue using Linked List:

1. Node Structure

  • Create a Node having data, priority, and next fields.

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

2. Enqueue (Insert according to priority)

Algorithm:

  1. Create a new node with given data and priority.

  2. If queue is empty OR the new node's priority is higher than the front node's priority:

    • Insert at the beginning.

  3. Else:

    • Traverse the list until you find a node with lower priority.

    • Insert the new node before that node.


3. Dequeue (Remove Highest Priority)

Algorithm:

  1. If the queue is empty:

    • Print "Queue is empty."

  2. Else:

    • Remove the front node (highest priority).

4. Display Queue

Algorithm:

  1. Start from the front.

  2. Print each node's data and priority.


Operation    Time ComplexityNotes
Enqueue        O(n)        Must find correct place
Dequeue        O(1)        Always remove from front

Example-1:
A placement drive interview is scheduled based on the marks in written test(out of 100).Person with highest mark is considered for interview.Create a priority queue and schedule the interview.

C Program- Priority Queue using Linked List
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
    char name[50];
    int marks;
    struct Node* next;
};

typedef struct Node Node;

Node* front = NULL;

// Function to create a new node
Node* createNode(char name[], int marks) {
    Node* temp = (Node*)malloc(sizeof(Node));
    strcpy(temp->name, name);
    temp->marks = marks;
    temp->next = NULL;
    return temp;
}

// Function to insert candidate into the priority queue
void insert(char name[], int marks) {
    Node* newNode = createNode(name, marks);

    if (front == NULL || marks > front->marks) {
        newNode->next = front;
        front = newNode;
    } else {
        Node* current = front;
        while (current->next != NULL && current->next->marks >= marks) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }

    printf("Candidate %s with marks %d added to the queue.\n", name, marks);
}

// Function to schedule interview (delete highest priority)
void scheduleInterview() {
    if (front == NULL) {
        printf("No candidates in the queue.\n");
        return;
    }

    Node* temp = front;
    printf("Interview scheduled for: %s with marks %d\n", temp->name, temp->marks);
    front = front->next;
    free(temp);
}

// Function to display the queue
void displayQueue() {
    if (front == NULL) {
        printf("Queue is empty.\n");
        return;
    }

    printf("\nCurrent Interview Queue (Highest Marks First):\n");
    Node* temp = front;
    while (temp != NULL) {
        printf("Name: %-20s Marks: %d\n", temp->name, temp->marks);
        temp = temp->next;
    }
}

// Main menu
int main() {
    int choice, marks;
    char name[50];

    while (1) {
        printf("\n--- Placement Interview Scheduler ---\n");
        printf("1. Insert Candidate\n");
        printf("2. Schedule Interview\n");
        printf("3. Display Queue\n");
        printf("4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        getchar(); // consume newline

        switch (choice) {
            case 1:
                printf("Enter Candidate Name: ");
                fgets(name, sizeof(name), stdin);
                name[strcspn(name, "\n")] = 0;  // remove newline
                printf("Enter Marks (out of 100): ");
                scanf("%d", &marks);
                insert(name, marks);
                break;

            case 2:
                scheduleInterview();
                break;

            case 3:
                displayQueue();
                break;

            case 4:
                printf("Exiting program.\n");
                exit(0);

            default:
                printf("Invalid choice. Try again.\n");
        }
    }

    return 0;
}

Example-2:
The General post office wishes to give preferential treatment to its customers. They have identified the customer categories as Defence personnel, Differently abled,Senior citizen, Ordinary. The customers are to be given preference in the decreasing order - Differently abled, Senior citizen, Defence personnel,Normal person.Generate the possible sequence of completion.

C Program- Priority Queue using Linked List

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

// Define node
struct Node {
    char name[100];
    int priority;
    struct Node* next;
};

struct Node* front = NULL;

// Create a new node
struct Node* createNode(char name[], int priority) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    strcpy(temp->name, name);
    temp->priority = priority;
    temp->next = NULL;
    return temp;
}

// Insert based on priority
void enqueue(char name[], int priority) {
    struct Node* newNode = createNode(name, priority);

    if (front == NULL || priority > front->priority) {
        newNode->next = front;
        front = newNode;
    } else {
        struct Node* temp = front;
        while (temp->next != NULL && temp->next->priority >= priority) {
            temp = temp->next;
        }
        newNode->next = temp->next;
        temp->next = newNode;
    }

    printf("Customer %s added with priority %d\n", name, priority);
}

// Remove from front
void dequeue() {
    if (front == NULL) {
        printf("No customers to serve.\n");
    } else {
        struct Node* temp = front;
        printf("Serving Customer: %s (Priority: %d)\n", front->name, front->priority);
        front = front->next;
        free(temp);
    }
}

// Display queue
void displayQueue() {
    struct Node* temp = front;
    if (temp == NULL) {
        printf("No customers in queue.\n");
    } else {
        printf("\nQueue:\n");
        while (temp != NULL) {
            printf("%s (Priority: %d) -> ", temp->name, temp->priority);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}


int main() {
    int choice;
    char name[100], category[100];
    int priority;

    do {
        printf("\nMenu\n----\n");
        printf("1. Add Customer\n");
        printf("2. Serve Customer\n");
        printf("3. Display Queue\n");
        printf("4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        getchar(); // to consume leftover newline

        switch(choice) {
            case 1:
                printf("Enter customer name: ");
                gets(name);
                printf("Enter customer category(Differently Abled-4/Senior Citizen-3/Defence Personnel-2/Ordinary-1): ");
                scanf("%d",&priority);
                enqueue(name, priority);
                displayQueue();
                break;
            case 2:
                dequeue();
                displayQueue();
                break;
            case 3:
                displayQueue();
                break;
            case 4:
                printf("Exiting...\n");
                break;
            default:
                printf("Invalid choice.\n");
        }
    } while(choice != 4);

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more