📌 Deque and Priority Queue in C

1️⃣ Deque (Double-Ended Queue)

A Deque (Double-Ended Queue) is a special type of queue where elements can be added or removed from both the front and the rear.

🔹 Types of Deques:
1️⃣ Input-Restricted Deque – Insertions allowed only at rear, but deletions allowed at both ends.
2️⃣ Output-Restricted Deque – Deletions allowed only from front, but insertions allowed at both ends.

---

✅ C Program: Deque Using Array

#include <stdio.h>
#define SIZE 5  // Define the max size

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

// Check if deque is full
int isFull() {
    return ((front == 0 && rear == SIZE - 1) || (front == rear + 1));
}

// Check if deque is empty
int isEmpty() {
    return (front == -1);
}

// Insert at the front
void insertFront(int value) {
    if (isFull()) {
        printf("Deque Overflow!\n");
        return;
    }
    if (isEmpty()) front = rear = 0;
    else if (front == 0) front = SIZE - 1;
    else front--;

    deque[front] = value;
    printf("Inserted %d at Front\n", value);
}

// Insert at the rear
void insertRear(int value) {
    if (isFull()) {
        printf("Deque Overflow!\n");
        return;
    }
    if (isEmpty()) front = rear = 0;
    else if (rear == SIZE - 1) rear = 0;
    else rear++;

    deque[rear] = value;
    printf("Inserted %d at Rear\n", value);
}

// Delete from the front
void deleteFront() {
    if (isEmpty()) {
        printf("Deque Underflow!\n");
        return;
    }
    printf("Deleted %d from Front\n", deque[front]);
    if (front == rear) front = rear = -1;
    else if (front == SIZE - 1) front = 0;
    else front++;
}

// Delete from the rear
void deleteRear() {
    if (isEmpty()) {
        printf("Deque Underflow!\n");
        return;
    }
    printf("Deleted %d from Rear\n", deque[rear]);
    if (front == rear) front = rear = -1;
    else if (rear == 0) rear = SIZE - 1;
    else rear--;
}

// Display Deque
void display() {
    if (isEmpty()) {
        printf("Deque is empty!\n");
        return;
    }
    printf("Deque: ");
    int i = front;
    while (1) {
        printf("%d ", deque[i]);
        if (i == rear) break;
        i = (i + 1) % SIZE;
    }
    printf("\n");
}

int main() {
    insertRear(10);
    insertRear(20);
    insertFront(5);
    display();
    
    deleteFront();
    display();
    
    insertFront(15);
    deleteRear();
    display();
    
    return 0;
}

✅ Efficient operations at both ends
✅ Useful for complex data structures (e.g., Palindrome checking, Undo/Redo functionality, etc.)

---

2️⃣ Priority Queue

A Priority Queue is a queue where each element has a priority.
🔹 Higher-priority elements are dequeued before lower-priority elements.
🔹 Can be implemented using arrays, linked lists, or heaps.

---

✅ C Program: Priority Queue Using Array

#include <stdio.h>
#define SIZE 5

struct PriorityQueue {
    int data;
    int priority;
} pq[SIZE];

int count = 0;

// Insert an element into priority queue
void insert(int value, int priority) {
    if (count == SIZE) {
        printf("Priority Queue Overflow!\n");
        return;
    }
    int i = count - 1;
    while (i >= 0 && pq[i].priority > priority) {
        pq[i + 1] = pq[i];
        i--;
    }
    pq[i + 1].data = value;
    pq[i + 1].priority = priority;
    count++;
    printf("Inserted %d with priority %d\n", value, priority);
}

// Remove highest-priority element
void delete() {
    if (count == 0) {
        printf("Priority Queue Underflow!\n");
        return;
    }
    printf("Removed %d with priority %d\n", pq[0].data, pq[0].priority);
    for (int i = 0; i < count - 1; i++) {
        pq[i] = pq[i + 1];
    }
    count--;
}

// Display priority queue
void display() {
    if (count == 0) {
        printf("Priority Queue is empty!\n");
        return;
    }
    printf("Priority Queue: ");
    for (int i = 0; i < count; i++) {
        printf("(%d, P:%d) ", pq[i].data, pq[i].priority);
    }
    printf("\n");
}

int main() {
    insert(10, 2);
    insert(20, 1);
    insert(30, 3);
    display();
    
    delete();
    display();
    
    return 0;
}

✅ Processes high-priority elements first
✅ Used in scheduling, networking, AI algorithms

---

3️⃣ Comparison: Deque vs Priority Queue

Feature	Deque	Priority Queue
Insertion	Both ends	Based on priority
Deletion	Both ends	Always removes highest priority
Order	FIFO (both sides)	Priority-based
Implementation	Array, Linked List	Array, Heap, Linked List
Use Case	Undo/Redo, Palindrome checking	Scheduling, Dijkstra’s Algorithm