C Programming data structures Deque and Priority Queue Step by step Implementation and Top 10 Questions and Answers
 .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION.    Last Update: April 01, 2025      14 mins read      Difficulty-Level: beginner

C Programming Data Structures: Deque and Priority Queue

Data structures are fundamental components in the field of computer programming, providing efficient ways to organize data to perform operations like insertion, deletion, search, etc. Two such important data structures in C programming are Deque (Double-ended Queue) and Priority Queue. Let's delve into these structures in detail, including their characteristics, uses, and implementations in C.

1. Deque (Double-ended Queue)

A Deque, short for Double-ended Queue, is a data structure that extends the concept of standard queues by allowing elements to be added or removed from both the front and the back ends of the queue. This flexibility makes it highly versatile for solving complex problems where both FIFO (First-In-First-Out) and LIFO (Last-In-First-Out) operations are required.

Characteristics:

  • Insertions and Deletions: Supported at both ends (front and back).
  • Dynamically Sizable: Memory can be allocated and deallocated based on requirements.
  • Time Complexity: Typically O(1) for insertions and deletions at both ends.

Use Cases:

  • Sliding Window Algorithms: Efficiently finding maximum/minimum in a subarray.
  • Undo Mechanism in Applications: Allowing undo and redo actions.
  • Queue-based Breadth-First Search (BFS): Efficiently managing queue operations in graph algorithms.

Implementation: In C, a deque can be implemented using arrays (with resizing) or linked lists. Below is a simple implementation using doubly linked lists:

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

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

typedef struct Deque {
    Node* front;
    Node* rear;
} Deque;

// Function prototypes
Deque* createDeque();
void insertFront(Deque* dq, int data);
void insertRear(Deque* dq, int data);
int deleteFront(Deque* dq);
int deleteRear(Deque* dq);
void freeDeque(Deque* dq);

Deque* createDeque() {
    Deque* dq = (Deque*)malloc(sizeof(Deque));
    dq->front = dq->rear = NULL;
    return dq;
}

Node* getNewNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

void insertFront(Deque* dq, int data) {
    Node* newNode = getNewNode(data);
    if (dq->front == NULL)
        dq->front = dq->rear = newNode;
    else {
        newNode->next = dq->front;
        dq->front->prev = newNode;
        dq->front = newNode;
    }
}

void insertRear(Deque* dq, int data) {
    Node* newNode = getNewNode(data);
    if (dq->rear == NULL)
        dq->front = dq->rear = newNode;
    else {
        newNode->prev = dq->rear;
        dq->rear->next = newNode;
        dq->rear = newNode;
    }
}

int deleteFront(Deque* dq) {
    if (dq->front == NULL) {
        printf("Deque underflow\n");
        return -1;
    }
    Node* temp = dq->front;
    int data = temp->data;
    dq->front = dq->front->next;
    if (dq->front == NULL)
        dq->rear = NULL;
    else
        dq->front->prev = NULL;
    free(temp);
    return data;
}

int deleteRear(Deque* dq) {
    if (dq->rear == NULL) {
        printf("Deque underflow\n");
        return -1;
    }
    Node* temp = dq->rear;
    int data = temp->data;
    dq->rear = dq->rear->prev;
    if (dq->rear == NULL)
        dq->front = NULL;
    else
        dq->rear->next = NULL;
    free(temp);
    return data;
}

void freeDeque(Deque* dq) {
    while (dq->front != NULL)
        deleteFront(dq);
    free(dq);
}

int main() {
    Deque* dq = createDeque();
    insertFront(dq, 5);
    insertRear(dq, 10);
    insertFront(dq, 2);
    printf("Deleted front: %d\n", deleteFront(dq));
    printf("Deleted rear: %d\n", deleteRear(dq));
    freeDeque(dq);
    return 0;
}

2. Priority Queue

A Priority Queue is an abstract data type similar to a regular queue or stack, but each element has a priority associated with it. An element with high priority is served before an element with low priority. If two elements have the same priority, they are served based on their order in the queue.

Characteristics:

  • Heap Implementation: Commonly implemented using binary heaps (binary heap can be max-heap or min-heap).
  • Dynamic Resizing: Supports dynamic resizing based on the number of elements.
  • Time Complexity: Insertion and deletion operations typically have a time complexity of O(log n).

Use Cases:

  • Job Schedulers: Managing tasks based on priority.
  • Network Routing: Prioritizing packets in network traffic.
  • Real-time Systems: Ensuring critical operations have higher response times.

Implementation: In C, a priority queue can be efficiently implemented using a binary heap. Here’s an example using binary heap with array representation:

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

typedef struct MaxHeap {
    int size;
    int capacity;
    int* arr;
} MaxHeap;

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

MaxHeap* createMaxHeap(int capacity) {
    MaxHeap* maxHeap = (MaxHeap*)malloc(sizeof(MaxHeap));
    maxHeap->capacity = capacity;
    maxHeap->size = 0;
    maxHeap->arr = (int*)malloc(sizeof(int) * capacity);
    return maxHeap;
}

int parent(int i) { return (i - 1) / 2; }
int left(int i) { return (2 * i + 1); }
int right(int i) { return (2 * i + 2); }

void insertKey(MaxHeap* maxHeap, int k) {
    if (maxHeap->size == maxHeap->capacity) {
        printf("Overflow\n");
        return;
    }

    maxHeap->size++;
    int i = maxHeap->size - 1;
    maxHeap->arr[i] = k;

    while (i != 0 && maxHeap->arr[parent(i)] < maxHeap->arr[i]) {
        swap(&maxHeap->arr[i], &maxHeap->arr[parent(i)]);
        i = parent(i);
    }
}

int extractMax(MaxHeap* maxHeap) {
    if (maxHeap->size <= 0)
        return INT_MIN;
    if (maxHeap->size == 1) {
        maxHeap->size--;
        return maxHeap->arr[0];
    }

    int root = maxHeap->arr[0];
    maxHeap->arr[0] = maxHeap->arr[maxHeap->size - 1];
    maxHeap->size--;
    heapify(maxHeap, 0);
    return root;
}

void heapify(MaxHeap* maxHeap, int i) {
    int largest = i;
    int l = left(i);
    int r = right(i);

    if (l < maxHeap->size && maxHeap->arr[l] > maxHeap->arr[largest])
        largest = l;

    if (r < maxHeap->size && maxHeap->arr[r] > maxHeap->arr[largest])
        largest = r;

    if (largest != i) {
        swap(&maxHeap->arr[i], &maxHeap->arr[largest]);
        heapify(maxHeap, largest);
    }
}

void freeMaxHeap(MaxHeap* maxHeap) {
    free(maxHeap->arr);
    free(maxHeap);
}

int main() {
    MaxHeap* maxHeap = createMaxHeap(10);
    insertKey(maxHeap, 3);
    insertKey(maxHeap, 10);
    insertKey(maxHeap, 4);
    insertKey(maxHeap, 1);
    insertKey(maxHeap, 9);
    insertKey(maxHeap, 20);
    insertKey(maxHeap, 30);

    printf("Maximum Element: %d\n", extractMax(maxHeap));
    printf("Maximum Element: %d\n", extractMax(maxHeap));

    freeMaxHeap(maxHeap);
    return 0;
}

Summary

Both Deques and Priority Queues are essential data structures in C programming due to their unique properties and wide range of applications. Deques, with their ability to perform operations from both ends, provide solutions to scenarios needing flexible enqueue and dequeue operations. On the other hand, Priority Queues, leveraging heap-based implementations, ensure efficient priority-based access and manipulation of elements. These data structures are crucial tools for developers aiming to optimize data management and processing tasks in various computational scenarios.




Examples, Set Route and Run the Application then Data Flow Step-by-Step for Beginners: C Programming Data Structures - Deque and Priority Queue

Introduction

Data structures are crucial components in computer programming and play a significant role in creating efficient algorithms. Two commonly used data structures are the Deque (Double-ended Queue) and the Priority Queue. In this guide, we will explore these data structures through C programming with simple examples. We will set up a route to follow, run the application, and understand the data flow step-by-step.

Understanding Data Structures

Deque (Double-ended Queue):

  • A Deque is a linear data structure that allows insertions and deletions to be performed from both ends.
  • Common operations include enqueueFront(), enqueueRear(), dequeueFront(), dequeueRear(), and getFront(), getRear().

Priority Queue:

  • A Priority Queue is a special type of queue in which each element is associated with a priority and elements are served based on their priority.
  • Common operations include enqueue(), dequeue(), and peek() to fetch the element with the highest priority.

Setting Up the Environment

  1. Install a C Compiler:

    • For Windows, use MinGW or CLang.
    • For Mac or Linux, use GCC which is usually pre-installed.
    • Alternatively, use an IDE like Code::Blocks, Visual Studio, or Code::Blocks with the GCC plugin.

  2. Create a New Project:

    • Open your IDE or text editor and create a new C project or file.
    • Name it DataStructures or similar.

Example Code: Implementing Deque

Let's start by implementing a simple Deque using arrays.

  1. Define the Deque Structure:

    #define MAX 100

typedef struct {
    int arr[MAX];
    int front;
    int rear;
} Deque;

  2. Helper Functions:

    void initializeDeque(Deque *deque) {
    deque->front = -1;
    deque->rear = 0;
}

int isDequeFull(Deque *deque) {
    return (deque->front == (deque->rear + 1) % MAX);
}

int isDequeEmpty(Deque *deque) {
    return (deque->front == -1);
}

void enqueueFront(Deque *deque, int item) {
    if (isDequeFull(deque)) return;
    if (deque->front == -1) { // Deque is initially empty
        deque->front = 0;
        deque->rear = 0;
    } else {
        deque->front = (deque->front - 1 + MAX) % MAX;
    }
    deque->arr[deque->front] = item;
}

void enqueueRear(Deque *deque, int item) {
    if (isDequeFull(deque)) return;
    if (deque->front == -1) { // Deque is initially empty
        deque->front = 0;
        deque->rear = 0;
    } else {
        deque->rear = (deque->rear + 1) % MAX;
    }
    deque->arr[deque->rear] = item;
}

int dequeueFront(Deque *deque) {
    int item;
    if (isDequeEmpty(deque)) return -1;
    item = deque->arr[deque->front];
    if (deque->front == deque->rear) { // Only one element
        deque->front = -1;
        deque->rear = -1;
    } else {
        deque->front = (deque->front + 1) % MAX;
    }
    return item;
}

int dequeueRear(Deque *deque) {
    int item;
    if (isDequeEmpty(deque)) return -1;
    item = deque->arr[deque->rear];
    if (deque->front == deque->rear) { // Only one element
        deque->front = -1;
        deque->rear = -1;
    } else {
        deque->rear = (deque->rear - 1 + MAX) % MAX;
    }
    return item;
}

int getFront(Deque *deque) {
    if (isDequeEmpty(deque)) return -1;
    return deque->arr[deque->front];
}

int getRear(Deque *deque) {
    if (isDequeEmpty(deque)) return -1;
    return deque->arr[deque->rear];
}

  3. Main Function to Test Deque:

    #include <stdio.h>

int main() {
    Deque deque;
    initializeDeque(&deque);
    enqueueFront(&deque, 10);
    enqueueRear(&deque, 20);
    enqueueFront(&deque, 5);
    printf("Front element: %d\n", getFront(&deque));
    printf("Rear element: %d\n", getRear(&deque));
    printf("Dequeued front: %d\n", dequeueFront(&deque));
    printf("Front element: %d\n", getFront(&deque));
    return 0;
}

Example Code: Implementing Priority Queue

Now, let's implement a simple Priority Queue using arrays. We'll keep higher priority numbers to indicate higher priority.

  1. Define the Priority Queue Structure:

    #define MAX 100

typedef struct {
    int arr[MAX];
    int size;
} PriorityQueue;

  2. Helper Functions:

    void initializePQ(PriorityQueue *pq) {
    pq->size = 0;
}

int isPQFull(PriorityQueue *pq) {
    return (pq->size == MAX);
}

int isPQEmpty(PriorityQueue *pq) {
    return (pq->size == 0);
}

void enqueue(PriorityQueue *pq, int item) {
    if (isPQFull(pq)) return;
    int i = pq->size - 1;
    while (i >= 0 && pq->arr[i] < item) {
        pq->arr[i + 1] = pq->arr[i];
        i--;
    }
    pq->arr[i + 1] = item;
    pq->size++;
}

int dequeue(PriorityQueue *pq) {
    if (isPQEmpty(pq)) return -1;
    int item = pq->arr[0];
    for (int i = 0; i < pq->size - 1; i++) {
        pq->arr[i] = pq->arr[i + 1];
    }
    pq->size--;
    return item;
}

int peek(PriorityQueue *pq) {
    if (isPQEmpty(pq)) return -1;
    return pq->arr[0];
}

  3. Main Function to Test Priority Queue:

    #include <stdio.h>

int main() {
    PriorityQueue pq;
    initializePQ(&pq);
    enqueue(&pq, 10);
    enqueue(&pq, 20);
    enqueue(&pq, 5);
    printf("Front element: %d\n", peek(&pq));
    printf("Dequeued: %d\n", dequeue(&pq));
    printf("Front element: %d\n", peek(&pq));
    return 0;
}

Running the Application

  1. Compile the Code:

    • For the Deque example, use: 
      gcc -o deque_example deque_example.c
    • For the Priority Queue example, use: 
      gcc -o pq_example pq_example.c

  2. Run the Executable:

    • Run the Deque example: 
      ./deque_example
    • Run the Priority Queue example: 
      ./pq_example

  3. Observe the Output:

    • For the Deque example, you should see: 
      Front element: 5
Rear element: 20
Dequeued front: 5
Front element: 10
    • For the Priority Queue example, you should see: 
      Front element: 20
Dequeued: 20
Front element: 10

Understanding the Data Flow

Deque:

  1. Initialize: deque.front = -1, deque.rear = 0.
  2. Enqueue at Front: Adjust deque.front and insert item.
  3. Enqueue at Rear: Adjust deque.rear and insert item.
  4. Dequeue at Front: Remove item and adjust deque.front.
  5. Dequeue at Rear: Remove item and adjust deque.rear.

Priority Queue:

  1. Initialize: pq.size = 0.
  2. Enqueue: Insert item based on priority.
  3. Dequeue: Remove item with highest priority (front of the queue).
  4. Peek: Return the item at the front of the queue.

Conclusion

With these examples, you have now learned how to implement basic Deque and Priority Queue data structures in C. You can expand on these examples by using linked lists for dynamic sizing or by using complex data types for more specific use cases. Practice is key, so keep experimenting and refining your understanding of these fundamental data structures.