GDcademy
Comprehensive Guide to Priority Queue: Algorithms, Pseudo Code, Implementation, and Complexity Analysis

Comprehensive Guide to Priority Queue: Algorithms, Pseudo Code, Implementation, and Complexity Analysis

Gourab Das's photo
Gourab Das
·

10 min read

Table of contents

1. Simple Queue (Linear Queue)

  • Description:
    A simple queue follows the FIFO principle, where elements are added at the rear and removed from the front. It uses a fixed-size array to implement the queue, and once full, no new elements can be added.

Algorithm for Simple Queue Operations

  1. Enqueue (Insert an element):

    • Check if the queue is full (rear == size - 1).

    • If full, display "Queue Overflow."

    • Otherwise:

      • Increment the rear index.

      • Insert the new element at queue[rear].

  2. Dequeue (Remove an element):

    • Check if the queue is empty (front > rear).

    • If empty, display "Queue Underflow."

    • Otherwise:

      • Retrieve the element at queue[front].

      • Increment the front index.

  3. Peek (View the front element):

    • Check if the queue is empty (front > rear).

    • If empty, display "Queue is Empty."

    • Otherwise, return the element at queue[front].

Pseudo Code

Enqueue Operation

ENQUEUE(queue, element):
    IF rear == size - 1:
        PRINT "Queue Overflow"
        EXIT
    ELSE:
        rear = rear + 1
        queue[rear] = element

Dequeue Operation

DEQUEUE(queue):
    IF front > rear:
        PRINT "Queue Underflow"
        EXIT
    ELSE:
        element = queue[front]
        front = front + 1
        RETURN element

Peek Operation

PEEK(queue):
    IF front > rear:
        PRINT "Queue is Empty"
        EXIT
    ELSE:
        RETURN queue[front]

C Language Code

#include <stdio.h>
#define SIZE 100

int queue[SIZE];
int front = 0, rear = -1;

void enqueue(int element) {
    if (rear == SIZE - 1) {
        printf("Queue Overflow\n");
        return;
    }
    queue[++rear] = element;
    printf("Enqueued: %d\n", element);
}

void dequeue() {
    if (front > rear) {
        printf("Queue Underflow\n");
        return;
    }
    printf("Dequeued: %d\n", queue[front++]);
}

void peek() {
    if (front > rear) {
        printf("Queue is Empty\n");
        return;
    }
    printf("Front element: %d\n", queue[front]);
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    dequeue();
    peek();
    dequeue();
    dequeue();
    dequeue();
    return 0;
}

Time and Space Complexity

OperationTime ComplexitySpace Complexity
EnqueueO(1)O(n)
DequeueO(1)O(n)
PeekO(1)O(1)

2. Circular Queue

Description:

A circular queue overcomes the limitations of a simple queue by reusing vacant spaces. The rear pointer wraps around to the beginning of the array when it reaches the end, forming a circular structure.

Algorithm for Circular Queue Operations

  1. Enqueue (Insert an element):

    • Check if the queue is full: (rear + 1) % size == front.

    • If full, display "Queue Overflow."

    • Otherwise:

      • If the queue is empty, set front = 0.

      • Update rear = (rear + 1) % size.

      • Insert the element at queue[rear].

  2. Dequeue (Remove an element):

    • Check if the queue is empty: front == -1.

    • If empty, display "Queue Underflow."

    • Otherwise:

      • Retrieve the element at queue[front].

      • If front == rear, reset front and rear to -1 (queue becomes empty).

      • Otherwise, update front = (front + 1) % size.

  3. Peek (View the front element):

    • Check if the queue is empty: front == -1.

    • If empty, display "Queue is Empty."

    • Otherwise, return queue[front].

Pseudo Code

Enqueue Operation

ENQUEUE(queue, element):
    IF (rear + 1) % size == front:
        PRINT "Queue Overflow"
        EXIT
    ELSE:
        IF front == -1:
            front = 0
        rear = (rear + 1) % size
        queue[rear] = element

Dequeue Operation

DEQUEUE(queue):
    IF front == -1:
        PRINT "Queue Underflow"
        EXIT
    ELSE:
        element = queue[front]
        IF front == rear:
            front = rear = -1
        ELSE:
            front = (front + 1) % size
        RETURN element

Peek Operation

PEEK(queue):
    IF front == -1:
        PRINT "Queue is Empty"
        EXIT
    ELSE:
        RETURN queue[front]

C Language Code

#include <stdio.h>
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

void enqueue(int element) {
    if ((rear + 1) % SIZE == front) {
        printf("Queue Overflow\n");
        return;
    }
    if (front == -1) front = 0;
    rear = (rear + 1) % SIZE;
    queue[rear] = element;
    printf("Enqueued: %d\n", element);
}

void dequeue() {
    if (front == -1) {
        printf("Queue Underflow\n");
        return;
    }
    printf("Dequeued: %d\n", queue[front]);
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % SIZE;
    }
}

void peek() {
    if (front == -1) {
        printf("Queue is Empty\n");
        return;
    }
    printf("Front element: %d\n", queue[front]);
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    dequeue();
    peek();
    enqueue(40);
    enqueue(50);
    enqueue(60);
    dequeue();
    dequeue();
    peek();
    return 0;
}

⭐Circular Queue is Full Condition

In a circular queue, the array wraps around when the Rear reaches the end of the array. The condition (Rear + 1) % Size == Front means that the next position of the Rear (after incrementing it) is equal to the Front. This indicates that the queue has no empty slots left and is therefore full.

Example

Let’s assume the circular queue has a Size = 5. This means the queue has 5 slots, indexed from 0 to 4.

1. Initial State (Empty Queue):

  • Front = -1, Rear = -1 (queue is empty).

  • Queue: [_, _, _, _, _]

2. After Enqueue Operations:

We enqueue the following elements step by step:

  • Enqueue 10:

    • Front = 0, Rear = 0

    • Queue: [10, _, _, _, _]

  • Enqueue 20:

    • Rear = 1

    • Queue: [10, 20, _, _, _]

  • Enqueue 30:

    • Rear = 2

    • Queue: [10, 20, 30, _, _]

  • Enqueue 40:

    • Rear = 3

    • Queue: [10, 20, 30, 40, _]

  • Enqueue 50:

    • Rear = 4

    • Queue: [10, 20, 30, 40, 50]

3. Check for Full Condition:

  • Now, Front = 0, Rear = 4.

  • If we try to enqueue one more element, the Rear would wrap around to the start of the array:

      Next Rear = (Rear + 1) % Size = (4 + 1) % 5 = 0

  • Since Next Rear = Front, the condition (Rear + 1) % Size == Front is satisfied, meaning the queue is full. We cannot add more elements without dequeuing first.

Visualization of Full Queue

rustCopy codeFront ->  0
Queue -> [10, 20, 30, 40, 50]
Rear  ->  4

If we try to enqueue, the next position of Rear will overlap with Front, indicating the queue is full.

⭐Let's understand how the "queue full condition" works when dequeues are performed in between, using the same example of a circular queue with Size = 5.

Initial Setup

  • Queue size: 5

  • Indexes: 0, 1, 2, 3, 4

Step 1: Initial State (Empty Queue)

  • Front = -1, Rear = -1

  • Queue: [_, _, _, _, _]

Step 2: Enqueue Elements

We enqueue 3 elements (10, 20, 30):

  1. Enqueue 10:

    • Front = 0, Rear = 0

    • Queue: [10, _, _, _, _]

  2. Enqueue 20:

    • Rear = 1

    • Queue: [10, 20, _, _, _]

  3. Enqueue 30:

    • Rear = 2

    • Queue: [10, 20, 30, _, _]

Step 3: Dequeue an Element

We perform one dequeue operation:

  1. Dequeue 10:

    • Before dequeue: Front = 0, Rear = 2

    • After removing 10, move Front to (Front + 1) % Size = (0 + 1) % 5 = 1.

    • Front = 1, Rear = 2

    • Queue: [_, 20, 30, _, _]

Now the queue has 2 elements: [_, 20, 30, _, _].

Step 4: Enqueue More Elements

We enqueue more elements to fill the queue:

  1. Enqueue 40:

    • Rear = (Rear + 1) % Size = (2 + 1) % 5 = 3

    • Front = 1, Rear = 3

    • Queue: [_, 20, 30, 40, _]

  2. Enqueue 50:

    • Rear = (Rear + 1) % Size = (3 + 1) % 5 = 4

    • Front = 1, Rear = 4

    • Queue: [_, 20, 30, 40, 50]

  3. Enqueue 60 (wrap around to the beginning of the array):

    • Rear = (Rear + 1) % Size = (4 + 1) % 5 = 0

    • Front = 1, Rear = 0

    • Queue: [60, 20, 30, 40, 50]

Step 5: Check Full Condition

Now, the queue is full:

  • Front = 1, Rear = 0.

  • Next position of Rear will be (Rear + 1) % Size = (0 + 1) % 5 = 1.

  • Since Next Rear == Front, the condition (Rear + 1) % Size == Front is satisfied, and the queue is full.

Visualization After Dequeues and Enqueues

Front ->  1
Queue -> [60, 20, 30, 40, 50]
Rear  ->  0

Time and Space Complexity

OperationTime ComplexitySpace Complexity
EnqueueO(1)O(n)
DequeueO(1)O(n)
PeekO(1)O(1)

3.Priority Queue Using Array

What is a Priority Queue?

In a priority queue, elements are dequeued based on their priority. The element with the highest priority is dequeued first. If two elements have the same priority, they follow the FIFO order.

When implementing a priority queue with an array, you can choose:

  1. Unsorted Array:

    • Insertion is fast since elements are added at the end.

    • Deletion is slow because you must find the element with the highest priority.

  2. Sorted Array:

    • Insertion is slow because you need to insert the element in the correct position to maintain the order.

    • Deletion is fast because the highest-priority element is always at the start or end.

Below, we'll explain unsorted array implementation (simpler for beginners).

Priority Queue Operations (Unsorted Array)

  1. Enqueue (Insert an element):

    • Add the element to the end of the array.

    • No sorting is required.

  2. Dequeue (Remove the highest-priority element):

    • Search for the element with the highest priority (e.g., the maximum value).

    • Remove it from the array by shifting elements to fill the gap.

  3. Peek (View the highest-priority element):

    • Search for the highest-priority element and return it without removing it.

Algorithm for Unsorted Array Implementation

  1. Enqueue Operation:

    • Add the new element at the end of the array.

    • Increment the array size.

  2. Dequeue Operation:

    • Traverse the array to find the element with the highest priority.

    • Remove it by shifting elements to the left, filling the gap.

    • Decrement the array size.

  3. Peek Operation:

    • Traverse the array to find the highest-priority element and return it.

Pseudo Code

Enqueue Operation:

ENQUEUE(array, element, size):
    IF size == MAX_SIZE:
        PRINT "Queue Overflow"
        EXIT
    ELSE:
        array[size] = element
        size = size + 1

Dequeue Operation:

DEQUEUE(array, size):
    IF size == 0:
        PRINT "Queue Underflow"
        EXIT
    ELSE:
        maxIndex = 0
        FOR i = 1 TO size - 1:
            IF array[i] > array[maxIndex]:
                maxIndex = i
        PRINT "Dequeued:", array[maxIndex]
        FOR i = maxIndex TO size - 2:
            array[i] = array[i + 1]
        size = size - 1

Peek Operation:

PEEK(array, size):
    IF size == 0:
        PRINT "Queue is Empty"
        EXIT
    ELSE:
        maxIndex = 0
        FOR i = 1 TO size - 1:
            IF array[i] > array[maxIndex]:
                maxIndex = i
        RETURN array[maxIndex]

C Language Code

#include <stdio.h>

#define MAX_SIZE 100

int queue[MAX_SIZE];
int size = 0;

void enqueue(int element) {
    if (size == MAX_SIZE) {
        printf("Queue Overflow\n");
        return;
    }
    queue[size++] = element;
    printf("Enqueued: %d\n", element);
}

void dequeue() {
    if (size == 0) {
        printf("Queue Underflow\n");
        return;
    }

    int maxIndex = 0;
    for (int i = 1; i < size; i++) {
        if (queue[i] > queue[maxIndex]) {
            maxIndex = i;
        }
    }

    printf("Dequeued: %d\n", queue[maxIndex]);

    // Shift elements to fill the gap
    for (int i = maxIndex; i < size - 1; i++) {
        queue[i] = queue[i + 1];
    }
    size--;
}

void peek() {
    if (size == 0) {
        printf("Queue is Empty\n");
        return;
    }

    int maxIndex = 0;
    for (int i = 1; i < size; i++) {
        if (queue[i] > queue[maxIndex]) {
            maxIndex = i;
        }
    }

    printf("Highest-priority element: %d\n", queue[maxIndex]);
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(5);
    peek();
    dequeue();
    peek();
    dequeue();
    dequeue();
    dequeue();
    return 0;
}

Step-by-Step Walkthrough:

Suppose we perform the following operations:

  1. enqueue(10)

  2. enqueue(20)

  3. enqueue(5)

  4. peek()

  5. dequeue()

  6. peek()

  • Step 1: enqueue(10)
    Array: [10]

  • Step 2: enqueue(20)
    Array: [10, 20]

  • Step 3: enqueue(5)
    Array: [10, 20, 5]

  • Step 4: peek()

    • Find the max element (20).

    • Output: 20.

  • Step 5: dequeue()

    • Find the max element (20).

    • Remove it and shift elements.

    • Array: [10, 5].

    • Output: 20.

  • Step 6: peek()

    • Find the max element (10).

    • Output: 10.

Time Complexity

OperationTime Complexity
EnqueueO(1)
DequeueO(n)
PeekO(n)

Space Complexity

  • O(n) (Array size).

PYQ ( MAKAUT UNIVERSITY )

queueDSAmakaut