C Programming Data Structures Deque And Priority Queue Complete Guide

Deque (Double-ended Queue)

A Deque, short for Double-ended Queue, is a dynamic data structure that allows insertion and deletion of elements from both ends efficiently. It combines the properties of both stacks and queues, offering more flexibility compared to traditional queues.

Properties

• Dynamic Size: You can add or remove elements without concern for predefined limits.
• Insertion/Deletion: Allows operations at both front and back ends.
• Random Access: Accessing elements is typically done from the ends, not in the middle.

Operations

1. Push Front: Adds an element to the front of the deque.
2. Push Back: Adds an element to the back of the deque.
3. Pop Front: Removes and returns the front element.
4. Pop Back: Removes and returns the back element.
5. Front: Retrieves but does not remove the front element.
6. Back: Retrieves but does not remove the back element.
7. Empty: Checks if the deque is empty.
8. Size: Returns the number of elements in the deque.

Implementation in C

To implement a deque in C, you can use a doubly linked list where each node contains a data field and pointers to the next and previous nodes. Alternatively, you can use a circular array for a more compact implementation at the cost of some complexity in managing indices.

Doubly Linked List Implementation:

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

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

struct Deque {
    struct Node* front;
    struct Node* rear;
    int count; // Keeps track of elements in the deque
};

void initializeDeque(struct Deque* dq) {
    dq->front = NULL;
    dq->rear = NULL;
    dq->count = 0;
}

void pushFront(struct Deque* dq, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) return; // Memory allocation failed
    newNode->data = data;
    newNode->next = dq->front;
    newNode->prev = NULL;

    if (dq->front == NULL) {
        dq->front = dq->rear = newNode;
    } else {
        dq->front->prev = newNode;
        dq->front = newNode;
    }
    dq->count++;
}

void pushBack(struct Deque* dq, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) return; // Memory allocation failed
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = dq->rear;

    if (dq->rear == NULL) {
        dq->front = dq->rear = newNode;
    } else {
        dq->rear->next = newNode;
        dq->rear = newNode;
    }
    dq->count++;
}

int popFront(struct Deque* dq) {
    if (dq->front == NULL) {
        printf("Deque Underflow\n");
        return -1;
    }

    struct Node* temp = dq->front;
    int data = temp->data;
    
    if (dq->front == dq->rear) {
        dq->front = dq->rear = NULL;
    } else {
        dq->front = dq->front->next;
        dq->front->prev = NULL;
    }
    free(temp);
    dq->count--;
    return data;
}

int popBack(struct Deque* dq) {
    if (dq->rear == NULL) {
        printf("Deque Underflow\n");
        return -1;
    }

    struct Node* temp = dq->rear;
    int data = temp->data;

    if (dq->front == dq->rear) {
        dq->front = dq->rear = NULL;
    } else {
        dq->rear = dq->rear->prev;
        dq->rear->next = NULL;
    }
    free(temp);
    dq->count--;
    return data;
}

int main() {
    struct Deque dq;
    initializeDeque(&dq);

    pushFront(&dq, 10);
    pushBack(&dq, 20);
    pushFront(&dq, 5);

    printf("Popped from front: %d\n", popFront(&dq));
    printf("Popped from back: %d\n", popBack(&dq));

    return 0;
}

Advantages

• Efficiency: Allows O(1) time complexity for insertions and deletions at both ends.
• Flexibility: Ideal for scenarios requiring flexible access to elements from either end.

Applications

• Undo/Redo Mechanisms: In text editors and software applications.
• Breadth-first Search (BFS): Utilized in graph algorithms.
• Sliding Window Algorithms: Used for maintaining windows like sums or other properties over arrays or lists.

Priority Queue

A Priority Queue is a specialized data structure that manages a collection of elements, each associated with a priority value. Elements are served based on their priority, with higher-priority elements typically being served before lower-priority ones.

Properties

• Ordered by Priority: Higher-priority elements take precedence.
• Heap-Based Implementation: Common to achieve efficient operations.
• Dynamic Size: Elements can be added or removed as needed.

Types

• Max-Priority Queue: The element with the highest priority is served first.
• Min-Priority Queue: The element with the lowest priority is served first.

Operations

1. Insert: Adds an element to the queue.
2. Peek/Find Max/Min: Retrieves the element with the highest/lowest priority without removing it.
3. Extract Max/Min: Removes and returns the element with the highest/lowest priority.
4. Delete: Removes a specific element, often accompanied by heap restructuring.
5. Change Priority: Adjusts the priority of an existing element, may involve restructuring.
6. Empty: Checks if the priority queue is empty.
7. Size: Returns the number of elements in the priority queue.

Implementation in C using Binary Heap

A binary heap is commonly used to implement a priority queue efficiently. The root of the heap holds the maximum (or minimum) element depending on the type.

Max-Priority Queue Implementation Using Binary Heap:

#include <stdio.h>
#include <limits.h>

struct PriorityQueue {
    int capacity;
    int size;
    int* elements;
};

struct PriorityQueue* createPriorityQueue(int capacity) {
    struct PriorityQueue* pq = (struct PriorityQueue*)malloc(sizeof(struct PriorityQueue));
    pq->capacity = capacity;
    pq->size = 0;
    pq->elements = (int*)malloc(capacity * sizeof(int));
    return pq;
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int getParentIndex(int index) { return (index - 1) / 2; }
int getLeftChildIndex(int index) { return 2 * index + 1; }
int getRightChildIndex(int index) { return 2 * index + 2; }

void heapifyUp(struct PriorityQueue* pq, int index) {
    int parentIndex = getParentIndex(index);
    while (index > 0 && pq->elements[index] > pq->elements[parentIndex]) {
        swap(&pq->elements[index], &pq->elements[parentIndex]);
        index = parentIndex;
        parentIndex = getParentIndex(index);
    }
}

void heapifyDown(struct PriorityQueue* pq, int index) {
    int left = getLeftChildIndex(index), right = getRightChildIndex(index);
    int largest = index;

    if (left < pq->size && pq->elements[left] > pq->elements[largest]) largest = left;
    if (right < pq->size && pq->elements[right] > pq->elements[largest]) largest = right;

    if (largest != index) {
        swap(&pq->elements[index], &pq->elements[largest]);
        heapifyDown(pq, largest);
    }
}

void insert(struct PriorityQueue* pq, int data) {
    if (pq->size >= pq->capacity) return; // Priority Queue Overflow
    pq->elements[pq->size++] = data;
    heapifyUp(pq, pq->size - 1);
}

int peek(struct PriorityQueue* pq) {
    if (pq->size <= 0) {
        printf("Priority Queue is empty\n");
        return INT_MIN;
    }
    return pq->elements[0];
}

int extractMax(struct PriorityQueue* pq) {
    if (pq->size <= 0) {
        printf("Priority Queue is empty\n");
        return INT_MIN;
    }

    int maxItem = pq->elements[0];
    pq->elements[0] = pq->elements[pq->size - 1];
    pq->size--;

    heapifyDown(pq, 0);
    return maxItem;
}

int main() {
    struct PriorityQueue* pq = createPriorityQueue(10);

    insert(pq, 10);
    insert(pq, 20);
    insert(pq, 30);

    printf("Max element is: %d\n", peek(pq));
    printf("Extracted Max: %d\n", extractMax(pq));

    return 0;
}

Advantages

• Efficiency: Insertion, deletion, and retrieval of the highest/lowest priority element are efficient (O(log n)).
• Simplicity: Simple using binary heaps, which are inherently well-suited for these operations.
• Applications in Scheduling: Common in operating systems for task management.

Disadvantages

• Complexity: Maintaining the heap property during insertions and deletions can be complex.
• Random Access Limited: Direct access to any element is not easily possible.

Applications

• Event-driven Systems: Such as simulations and GUI libraries.
• Dijkstra's Algorithm: For finding shortest paths in graphs.
• Huffman Coding: Used in efficient data compression techniques.

Use Case Comparison

• Deque:

  • When you need a data structure that supports efficient insertion and deletion from both ends.
  • Useful in rolling windows, undo mechanisms, and BFS-like scenarios where two-way access benefits performance.

• Priority Queue:

  • When tasks or events need to be processed based on priority.
  • Useful in scheduling problems, pathfinding algorithms (like Dijkstra), and resource allocation scenarios.

By understanding these data structures and their implementations in C, you can effectively manage various computational requirements, optimizing code performance in scenarios where deque and priority queue behaviors are advantageous.