Queue in C - FIFO Data Structure Implementation

📋 Table of Contents

1. Queue Basics
2. Queue Operations
3. Array Implementation
4. Linked List Implementation
5. Circular Queue
6. Deque (Double Ended Queue)
7. Priority Queue
8. Queue Applications
9. Complexity Analysis
10. Summary

1. Queue Basics

A queue is a linear data structure that follows the FIFO (First In First Out) principle. The first element added to the queue will be the first one to be removed. Think of a queue at a ticket counter - the person who arrives first gets served first.

📊 Queue Visualization (FIFO)

Operation      Queue State                 Front    Rear
---------      -----------                 -----    ----
Enqueue(10)    [10]                        ↑10      ↑10
Enqueue(20)    [10, 20]                     10       ↑20
Enqueue(30)    [10, 20, 30]                 10        30
Dequeue()      [20, 30]        ← returns 10   ↑20       30
Dequeue()      [30]            ← returns 20   ↑30       ↑30
Enqueue(40)    [30, 40]                     30        40

Key Characteristics

Linear Structure - Elements arranged sequentially
FIFO Order - First In First Out
Two Ends - Front (deletion) and Rear (insertion)
Dynamic Size - Can grow/shrink as needed (in linked implementation)

Queue Analogy

🎫 Ticket Counter

People stand in line; first person gets ticket first

🚗 Toll Booth

Cars enter in order and pay in the same order

🖨️ Printer Queue

Documents print in the order they were submitted

📞 Call Center

Calls answered in order of arrival

2. Queue Operations

Primary Operations

Operation	Description	Position	Action
Enqueue	Insert element	Rear	Add to end
Dequeue	Delete element	Front	Remove from beginning
Front/Peek	View front element	Front	Read without removal
Rear	View rear element	Rear	Read last element

Auxiliary Operations

Operation	Description	Purpose
IsEmpty	Check if queue is empty	Prevent underflow
IsFull	Check if queue is full	Prevent overflow
Size	Return number of elements	Track queue length

Algorithm: Enqueue Operation

📝 Step-by-Step Algorithm

Algorithm Enqueue(Q, value):
    1. IF Q.rear == MAX_SIZE - 1
           PRINT "Queue Overflow"
           RETURN
    2. IF Q.front == -1
           Q.front = 0
    3. Q.rear = Q.rear + 1
    4. Q.arr[Q.rear] = value
    5. PRINT "Element inserted"

Algorithm: Dequeue Operation

📝 Step-by-Step Algorithm

Algorithm Dequeue(Q):
    1. IF Q.front == -1 OR Q.front > Q.rear
           PRINT "Queue Underflow"
           RETURN -1
    2. value = Q.arr[Q.front]
    3. IF Q.front == Q.rear
           Q.front = -1
           Q.rear = -1
       ELSE
           Q.front = Q.front + 1
    4. RETURN value

3. Array Implementation

Queue can be implemented using an array with two pointers: front and rear. The array implementation is simple but has the limitation of fixed size.

Complete Menu-Driven Queue Program

queue_array.c

#include <stdio.h>
#include <stdbool.h>
#define MAX 100

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

// Initialize queue
void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// Check if queue is empty
bool isEmpty(Queue* q) {
    return (q->front == -1 || q->front > q->rear);
}

// Check if queue is full
bool isFull(Queue* q) {
    return (q->rear == MAX - 1);
}

// Get size of queue
int size(Queue* q) {
    if (isEmpty(q))
        return 0;
    return (q->rear - q->front + 1);
}

// Enqueue - Add element at rear
void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("❌ Queue Overflow! Cannot insert %d\n", value);
        return;
    }
    
    // First element
    if (q->front == -1) {
        q->front = 0;
    }
    
    q->rear++;
    q->arr[q->rear] = value;
    printf("✅ Enqueued: %d\n", value);
}

// Dequeue - Remove element from front
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("❌ Queue Underflow! Queue is empty\n");
        return -1;
    }
    
    int value = q->arr[q->front];
    q->front++;
    
    // Reset if queue becomes empty
    if (q->front > q->rear) {
        q->front = -1;
        q->rear = -1;
    }
    
    printf("✅ Dequeued: %d\n", value);
    return value;
}

// Peek - Get front element without removing
int peek(Queue* q) {
    if (isEmpty(q)) {
        printf("❌ Queue is empty!\n");
        return -1;
    }
    return q->arr[q->front];
}

// Get rear element
int getRear(Queue* q) {
    if (isEmpty(q)) {
        printf("❌ Queue is empty!\n");
        return -1;
    }
    return q->arr[q->rear];
}

// Display queue elements
void display(Queue* q) {
    if (isEmpty(q)) {
        printf("📭 Queue is empty\n");
        return;
    }
    
    printf("📊 Queue contents (Front to Rear):\n");
    printf("   FRONT -> ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("[%d]", q->arr[i]);
        if (i < q->rear)
            printf(" -> ");
    }
    printf(" <- REAR\n");
    printf("   Size: %d elements\n", size(q));
}

int main() {
    Queue q;
    initQueue(&q);
    
    int choice, value;
    
    printf("╔════════════════════════════════════╗\n");
    printf("║     Queue Operations (Array)       ║\n");
    printf("╚════════════════════════════════════╝\n\n");
    
    while (1) {
        printf("\n📋 Menu:\n");
        printf("1️⃣  Enqueue\n");
        printf("2️⃣  Dequeue\n");
        printf("3️⃣  Peek (Front)\n");
        printf("4️⃣  Get Rear\n");
        printf("5️⃣  Check if Empty\n");
        printf("6️⃣  Check if Full\n");
        printf("7️⃣  Get Size\n");
        printf("8️⃣  Display Queue\n");
        printf("9️⃣  Exit\n");
        printf("\nEnter your choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter value to enqueue: ");
                scanf("%d", &value);
                enqueue(&q, value);
                break;
                
            case 2:
                dequeue(&q);
                break;
                
            case 3:
                value = peek(&q);
                if (value != -1)
                    printf("👁️  Front element: %d\n", value);
                break;
                
            case 4:
                value = getRear(&q);
                if (value != -1)
                    printf("👁️  Rear element: %d\n", value);
                break;
                
            case 5:
                if (isEmpty(&q))
                    printf("✓ Queue is empty\n");
                else
                    printf("✗ Queue is not empty\n");
                break;
                
            case 6:
                if (isFull(&q))
                    printf("✓ Queue is full\n");
                else
                    printf("✗ Queue is not full\n");
                break;
                
            case 7:
                printf("📏 Queue size: %d\n", size(&q));
                break;
                
            case 8:
                display(&q);
                break;
                
            case 9:
                printf("👋 Exiting...\n");
                return 0;
                
            default:
                printf("❌ Invalid choice! Please try again.\n");
        }
    }
    
    return 0;
}

Sample Output

╔════════════════════════════════════╗
║     Queue Operations (Array)       ║
╚════════════════════════════════════╝

📋 Menu:
1️⃣  Enqueue
2️⃣  Dequeue
3️⃣  Peek (Front)
...
Enter your choice: 1
Enter value to enqueue: 10
✅ Enqueued: 10

📋 Menu:
Enter your choice: 1
Enter value to enqueue: 20
✅ Enqueued: 20

📋 Menu:
Enter your choice: 8
📊 Queue contents (Front to Rear):
   FRONT -> [10] -> [20] <- REAR
   Size: 2 elements

📋 Menu:
Enter your choice: 2
✅ Dequeued: 10

📋 Menu:
Enter your choice: 9
👋 Exiting...

4. Linked List Implementation

Dynamic queue implementation using linked list overcomes the size limitation of array implementation. Elements are stored in nodes with pointers connecting them.

📊 Linked Queue Structure

Memory Layout:

    FRONT                                      REAR
      ↓                                          ↓
    +------+------+    +------+------+    +------+------+
    |  10  | next |--->|  20  | next |--->|  30  | NULL |
    +------+------+    +------+------+    +------+------+
         ↑
    Dequeue here                    Enqueue here

Complete Linked List Queue Program

queue_linked_list.c

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

// Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Queue structure
typedef struct {
    Node* front;
    Node* rear;
    int size;
} QueueLL;

// Initialize queue
void initQueueLL(QueueLL* q) {
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}

// Check if queue is empty
bool isEmptyLL(QueueLL* q) {
    return (q->front == NULL);
}

// Enqueue - Add element at rear
void enqueueLL(QueueLL* q, int value) {
    // Create new node
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("❌ Memory allocation failed!\n");
        return;
    }
    
    newNode->data = value;
    newNode->next = NULL;
    
    // If queue is empty
    if (isEmptyLL(q)) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        // Add at rear
        q->rear->next = newNode;
        q->rear = newNode;
    }
    
    q->size++;
    printf("✅ Enqueued: %d\n", value);
}

// Dequeue - Remove element from front
int dequeueLL(QueueLL* q) {
    if (isEmptyLL(q)) {
        printf("❌ Queue Underflow! Queue is empty\n");
        return -1;
    }
    
    Node* temp = q->front;
    int value = temp->data;
    
    q->front = q->front->next;
    
    // If queue becomes empty, update rear
    if (q->front == NULL) {
        q->rear = NULL;
    }
    
    free(temp);
    q->size--;
    
    printf("✅ Dequeued: %d\n", value);
    return value;
}

// Peek - Get front element
int peekLL(QueueLL* q) {
    if (isEmptyLL(q)) {
        printf("❌ Queue is empty!\n");
        return -1;
    }
    return q->front->data;
}

// Get rear element
int getRearLL(QueueLL* q) {
    if (isEmptyLL(q)) {
        printf("❌ Queue is empty!\n");
        return -1;
    }
    return q->rear->data;
}

// Get size
int getSizeLL(QueueLL* q) {
    return q->size;
}

// Display queue
void displayLL(QueueLL* q) {
    if (isEmptyLL(q)) {
        printf("📭 Queue is empty\n");
        return;
    }
    
    printf("📊 Queue contents (Front to Rear):\n");
    printf("   FRONT -> ");
    
    Node* temp = q->front;
    while (temp != NULL) {
        printf("[%d]", temp->data);
        temp = temp->next;
        if (temp != NULL)
            printf(" -> ");
    }
    
    printf(" <- REAR\n");
    printf("   Size: %d elements\n", q->size);
}

// Free all nodes
void destroyQueueLL(QueueLL* q) {
    while (!isEmptyLL(q)) {
        dequeueLL(q);
    }
}

int main() {
    QueueLL q;
    initQueueLL(&q);
    
    int choice, value;
    
    printf("╔════════════════════════════════════════╗\n");
    printf("║   Queue Operations (Linked List)       ║\n");
    printf("╚════════════════════════════════════════╝\n\n");
    
    while (1) {
        printf("\n📋 Menu:\n");
        printf("1️⃣  Enqueue\n");
        printf("2️⃣  Dequeue\n");
        printf("3️⃣  Peek (Front)\n");
        printf("4️⃣  Get Rear\n");
        printf("5️⃣  Check if Empty\n");
        printf("6️⃣  Get Size\n");
        printf("7️⃣  Display Queue\n");
        printf("8️⃣  Exit\n");
        printf("\nEnter your choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter value to enqueue: ");
                scanf("%d", &value);
                enqueueLL(&q, value);
                break;
                
            case 2:
                dequeueLL(&q);
                break;
                
            case 3:
                value = peekLL(&q);
                if (value != -1)
                    printf("👁️  Front element: %d\n", value);
                break;
                
            case 4:
                value = getRearLL(&q);
                if (value != -1)
                    printf("👁️  Rear element: %d\n", value);
                break;
                
            case 5:
                if (isEmptyLL(&q))
                    printf("✓ Queue is empty\n");
                else
                    printf("✗ Queue is not empty\n");
                break;
                
            case 6:
                printf("📏 Queue size: %d\n", getSizeLL(&q));
                break;
                
            case 7:
                displayLL(&q);
                break;
                
            case 8:
                destroyQueueLL(&q);
                printf("👋 Exiting...\n");
                return 0;
                
            default:
                printf("❌ Invalid choice!\n");
        }
    }
    
    return 0;
}

Advantages of Linked Implementation

Dynamic Size - No fixed size limitation
Memory Efficient - Only uses needed memory
No Overflow - Until system memory exhausts
Flexible - Easy to grow/shrink

5. Circular Queue

Problem with Linear Queue

In a linear queue using array, after several enqueue and dequeue operations, the front moves forward, leaving empty spaces at the beginning that cannot be used. This is called "false overflow".

❌ False Overflow Problem

Array Size: 5

Step 1: Enqueue 10, 20, 30, 40, 50
        [10][20][30][40][50]  ← Full
         ↑              ↑
       Front          Rear

Step 2: Dequeue, Dequeue
        [__][__][30][40][50]  ← Spaces wasted!
                 ↑        ↑
               Front    Rear

Step 3: Try Enqueue 60
        ❌ OVERFLOW! (Rear at end, but spaces available)

Circular Queue Solution

A circular queue treats the array as circular, where the last position connects back to the first. We use modulo arithmetic: (rear + 1) % MAX

✅ Circular Queue Concept

Circular Array (Size = 5):

    +---+---+---+---+---+
    | 0 | 1 | 2 | 3 | 4 |
    +---+---+---+---+---+
      ↑               ↑
    Front connects back to 0 when Rear is at 4

Operations:
• Enqueue: rear = (rear + 1) % MAX
• Dequeue: front = (front + 1) % MAX

Initial: front = -1, rear = -1
Empty: front == -1
Full: (rear + 1) % MAX == front

Complete Circular Queue Program

circular_queue.c

#include <stdio.h>
#include <stdbool.h>
#define MAX 5

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

// Initialize queue
void initCircularQueue(CircularQueue* q) {
    q->front = -1;
    q->rear = -1;
}

// Check if empty
bool isCircularEmpty(CircularQueue* q) {
    return (q->front == -1);
}

// Check if full
bool isCircularFull(CircularQueue* q) {
    return ((q->rear + 1) % MAX == q->front);
}

// Get count
int circularCount(CircularQueue* q) {
    if (isCircularEmpty(q))
        return 0;
    if (q->rear >= q->front)
        return (q->rear - q->front + 1);
    return (MAX - q->front + q->rear + 1);
}

// Enqueue - Circular increment
void enqueueCircular(CircularQueue* q, int value) {
    if (isCircularFull(q)) {
        printf("❌ Queue is full! Cannot insert %d\n", value);
        return;
    }
    
    // First element
    if (isCircularEmpty(q)) {
        q->front = 0;
    }
    
    // Circular increment
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = value;
    
    printf("✅ Enqueued: %d at position %d\n", value, q->rear);
}

// Dequeue - Circular increment
int dequeueCircular(CircularQueue* q) {
    if (isCircularEmpty(q)) {
        printf("❌ Queue is empty!\n");
        return -1;
    }
    
    int value = q->arr[q->front];
    
    // Only one element
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        // Circular increment
        q->front = (q->front + 1) % MAX;
    }
    
    printf("✅ Dequeued: %d\n", value);
    return value;
}

// Peek
int peekCircular(CircularQueue* q) {
    if (isCircularEmpty(q)) {
        printf("❌ Queue is empty!\n");
        return -1;
    }
    return q->arr[q->front];
}

// Display circular queue
void displayCircular(CircularQueue* q) {
    if (isCircularEmpty(q)) {
        printf("📭 Queue is empty\n");
        return;
    }
    
    printf("📊 Circular Queue Contents:\n");
    printf("   Front = %d, Rear = %d\n", q->front, q->rear);
    printf("   FRONT -> ");
    
    int i = q->front;
    while (true) {
        printf("[%d]", q->arr[i]);
        if (i == q->rear)
            break;
        printf(" -> ");
        i = (i + 1) % MAX;
    }
    
    printf(" <- REAR\n");
    printf("   Count: %d/%d elements\n", circularCount(q), MAX);
}

// Visual representation
void visualizeCircular(CircularQueue* q) {
    printf("\n   Circular Array Visualization:\n");
    printf("   ");
    for (int i = 0; i < MAX; i++) {
        printf("+------+");
    }
    printf("\n   ");
    for (int i = 0; i < MAX; i++) {
        if (i == q->front && i == q->rear && !isCircularEmpty(q))
            printf("|F/R%2d|", q->arr[i]);
        else if (i == q->front && !isCircularEmpty(q))
            printf("|FRONT%1d|", q->arr[i]);
        else if (i == q->rear && !isCircularEmpty(q))
            printf("|REAR%2d|", q->arr[i]);
        else
            printf("|  %2d  |", q->arr[i]);
    }
    printf("\n   ");
    for (int i = 0; i < MAX; i++) {
        printf("+------+");
    }
    printf("\n      0      1      2      3      4\n");
}

int main() {
    CircularQueue q;
    initCircularQueue(&q);
    
    int choice, value;
    
    printf("╔════════════════════════════════════════╗\n");
    printf("║       Circular Queue Operations        ║\n");
    printf("╚════════════════════════════════════════╝\n\n");
    
    while (1) {
        printf("\n📋 Menu:\n");
        printf("1️⃣  Enqueue\n");
        printf("2️⃣  Dequeue\n");
        printf("3️⃣  Peek\n");
        printf("4️⃣  Display\n");
        printf("5️⃣  Visualize\n");
        printf("6️⃣  Exit\n");
        printf("\nEnter choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter value: ");
                scanf("%d", &value);
                enqueueCircular(&q, value);
                break;
            case 2:
                dequeueCircular(&q);
                break;
            case 3:
                value = peekCircular(&q);
                if (value != -1)
                    printf("👁️  Front element: %d\n", value);
                break;
            case 4:
                displayCircular(&q);
                break;
            case 5:
                visualizeCircular(&q);
                break;
            case 6:
                printf("👋 Exiting...\n");
                return 0;
            default:
                printf("❌ Invalid choice!\n");
        }
    }
    
    return 0;
}

Advantages of Circular Queue

No Wasted Space - Reuses empty positions at front
No False Overflow - Can use all array positions
Efficient - O(1) for all operations
Better Memory Utilization - Circular nature prevents fragmentation

6. Deque (Double Ended Queue)

Definition

A Deque (Double Ended Queue) is a generalized queue where insertion and deletion can be performed at both ends (front and rear). It combines features of both stack and queue.

📊 Deque Structure

    Insert/Delete           Insert/Delete
        ↓                       ↓
      FRONT                   REAR
        ↓                       ↓
    +---+---+---+---+---+---+---+---+
    | 10| 20| 30| 40| 50| 60| 70|   |
    +---+---+---+---+---+---+---+---+
    
Operations allowed:
• Insert at Front ✓    • Delete from Front ✓
• Insert at Rear  ✓    • Delete from Rear  ✓

Types of Deque

📥 Input Restricted Deque

Insertion: Only at one end (Rear)
Deletion: Both ends allowed

📤 Output Restricted Deque

Insertion: Both ends allowed
Deletion: Only at one end (Front)

Complete Deque Implementation

deque.c

#include <stdio.h>
#include <stdbool.h>
#define MAX 100

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

// Initialize deque
void initDeque(Deque* dq) {
    dq->front = -1;
    dq->rear = -1;
}

// Check if empty
bool isDequeEmpty(Deque* dq) {
    return (dq->front == -1);
}

// Check if full
bool isDequeFull(Deque* dq) {
    return ((dq->front == 0 && dq->rear == MAX - 1) || 
            (dq->front == dq->rear + 1));
}

// Insert at front
void insertFront(Deque* dq, int value) {
    if (isDequeFull(dq)) {
        printf("❌ Deque is full! Cannot insert at front\n");
        return;
    }
    
    // First element
    if (isDequeEmpty(dq)) {
        dq->front = 0;
        dq->rear = 0;
    }
    // Front is at first position, wrap around
    else if (dq->front == 0) {
        dq->front = MAX - 1;
    }
    // Normal case
    else {
        dq->front--;
    }
    
    dq->arr[dq->front] = value;
    printf("✅ Inserted %d at FRONT\n", value);
}

// Insert at rear
void insertRear(Deque* dq, int value) {
    if (isDequeFull(dq)) {
        printf("❌ Deque is full! Cannot insert at rear\n");
        return;
    }
    
    // First element
    if (isDequeEmpty(dq)) {
        dq->front = 0;
        dq->rear = 0;
    }
    // Rear is at last position, wrap around
    else if (dq->rear == MAX - 1) {
        dq->rear = 0;
    }
    // Normal case
    else {
        dq->rear++;
    }
    
    dq->arr[dq->rear] = value;
    printf("✅ Inserted %d at REAR\n", value);
}

// Delete from front
int deleteFront(Deque* dq) {
    if (isDequeEmpty(dq)) {
        printf("❌ Deque is empty!\n");
        return -1;
    }
    
    int value = dq->arr[dq->front];
    
    // Only one element
    if (dq->front == dq->rear) {
        dq->front = -1;
        dq->rear = -1;
    }
    // Front at end, wrap around
    else if (dq->front == MAX - 1) {
        dq->front = 0;
    }
    // Normal case
    else {
        dq->front++;
    }
    
    printf("✅ Deleted %d from FRONT\n", value);
    return value;
}

// Delete from rear
int deleteRear(Deque* dq) {
    if (isDequeEmpty(dq)) {
        printf("❌ Deque is empty!\n");
        return -1;
    }
    
    int value = dq->arr[dq->rear];
    
    // Only one element
    if (dq->front == dq->rear) {
        dq->front = -1;
        dq->rear = -1;
    }
    // Rear at beginning, wrap around
    else if (dq->rear == 0) {
        dq->rear = MAX - 1;
    }
    // Normal case
    else {
        dq->rear--;
    }
    
    printf("✅ Deleted %d from REAR\n", value);
    return value;
}

// Get front element
int getFront(Deque* dq) {
    if (isDequeEmpty(dq)) {
        printf("❌ Deque is empty!\n");
        return -1;
    }
    return dq->arr[dq->front];
}

// Get rear element
int getRear(Deque* dq) {
    if (isDequeEmpty(dq)) {
        printf("❌ Deque is empty!\n");
        return -1;
    }
    return dq->arr[dq->rear];
}

// Display deque
void displayDeque(Deque* dq) {
    if (isDequeEmpty(dq)) {
        printf("📭 Deque is empty\n");
        return;
    }
    
    printf("📊 Deque contents:\n");
    printf("   FRONT -> ");
    
    int i = dq->front;
    while (true) {
        printf("[%d]", dq->arr[i]);
        if (i == dq->rear)
            break;
        printf(" -> ");
        i = (i + 1) % MAX;
    }
    
    printf(" <- REAR\n");
}

int main() {
    Deque dq;
    initDeque(&dq);
    
    int choice, value;
    
    printf("╔════════════════════════════════════════╗\n");
    printf("║        Deque Operations                ║\n");
    printf("║  (Double Ended Queue)                  ║\n");
    printf("╚════════════════════════════════════════╝\n\n");
    
    while (1) {
        printf("\n📋 Menu:\n");
        printf("1️⃣  Insert at Front\n");
        printf("2️⃣  Insert at Rear\n");
        printf("3️⃣  Delete from Front\n");
        printf("4️⃣  Delete from Rear\n");
        printf("5️⃣  Get Front Element\n");
        printf("6️⃣  Get Rear Element\n");
        printf("7️⃣  Display Deque\n");
        printf("8️⃣  Exit\n");
        printf("\nEnter choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter value: ");
                scanf("%d", &value);
                insertFront(&dq, value);
                break;
            case 2:
                printf("Enter value: ");
                scanf("%d", &value);
                insertRear(&dq, value);
                break;
            case 3:
                deleteFront(&dq);
                break;
            case 4:
                deleteRear(&dq);
                break;
            case 5:
                value = getFront(&dq);
                if (value != -1)
                    printf("👁️  Front element: %d\n", value);
                break;
            case 6:
                value = getRear(&dq);
                if (value != -1)
                    printf("👁️  Rear element: %d\n", value);
                break;
            case 7:
                displayDeque(&dq);
                break;
            case 8:
                printf("👋 Exiting...\n");
                return 0;
            default:
                printf("❌ Invalid choice!\n");
        }
    }
    
    return 0;
}

Applications of Deque

Palindrome Checker - Can check from both ends
Undo/Redo Operations - Add operations at both ends
Job Scheduling - Priority jobs from front, normal from rear
Sliding Window Problems - Efficient max/min tracking
A-Steal Algorithm - Used in multiprocessor scheduling

7. Priority Queue

Definition

A Priority Queue is a special queue where elements are served based on their priority, not just FIFO. Higher priority elements are processed before lower priority ones.

Types of Priority Queue

Ascending Priority Queue - Lower value = Higher priority
Descending Priority Queue - Higher value = Higher priority

📊 Priority Queue Concept (Descending)

Insertion Order: Job A(3), Job B(1), Job C(5), Job D(2)
                    ↑ Priority

Internal Order (by priority):
    +---+---+---+---+
    | C | A | D | B |  ← C (priority 5) is at front
    | 5 | 3 | 2 | 1 |
    +---+---+---+---+
      ↑
    Highest Priority - Served First

Dequeue Order: C → A → D → B

Complete Priority Queue Implementation

priority_queue.c

#include <stdio.h>
#include <stdbool.h>
#define MAX 100

// Element with priority
typedef struct {
    int data;
    int priority;
} PQElement;

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

// Initialize priority queue
void initPQ(PriorityQueue* pq) {
    pq->size = 0;
}

// Check if empty
bool isPQEmpty(PriorityQueue* pq) {
    return (pq->size == 0);
}

// Check if full
bool isPQFull(PriorityQueue* pq) {
    return (pq->size == MAX);
}

// Insert with priority (Descending - higher value = higher priority)
void enqueuePQ(PriorityQueue* pq, int data, int priority) {
    if (isPQFull(pq)) {
        printf("❌ Priority Queue is full!\n");
        return;
    }
    
    int i = pq->size - 1;
    
    // Shift elements to make room (higher priority first)
    while (i >= 0 && pq->arr[i].priority < priority) {
        pq->arr[i + 1] = pq->arr[i];
        i--;
    }
    
    // Insert at correct position
    pq->arr[i + 1].data = data;
    pq->arr[i + 1].priority = priority;
    pq->size++;
    
    printf("✅ Enqueued: Data=%d, Priority=%d\n", data, priority);
}

// Dequeue highest priority element
PQElement dequeuePQ(PriorityQueue* pq) {
    PQElement empty = {-1, -1};
    
    if (isPQEmpty(pq)) {
        printf("❌ Priority Queue is empty!\n");
        return empty;
    }
    
    // Highest priority is at index 0
    PQElement element = pq->arr[0];
    
    // Shift all elements
    for (int i = 0; i < pq->size - 1; i++) {
        pq->arr[i] = pq->arr[i + 1];
    }
    pq->size--;
    
    printf("✅ Dequeued: Data=%d, Priority=%d\n", element.data, element.priority);
    return element;
}

// Peek highest priority
PQElement peekPQ(PriorityQueue* pq) {
    PQElement empty = {-1, -1};
    
    if (isPQEmpty(pq)) {
        printf("❌ Priority Queue is empty!\n");
        return empty;
    }
    
    return pq->arr[0];
}

// Display priority queue
void displayPQ(PriorityQueue* pq) {
    if (isPQEmpty(pq)) {
        printf("📭 Priority Queue is empty\n");
        return;
    }
    
    printf("📊 Priority Queue Contents (Highest First):\n");
    printf("   +--------+----------+\n");
    printf("   |  Data  | Priority |\n");
    printf("   +--------+----------+\n");
    
    for (int i = 0; i < pq->size; i++) {
        printf("   |  %4d  |    %4d  |%s\n", 
               pq->arr[i].data, pq->arr[i].priority,
               (i == 0) ? " ← HIGHEST" : "");
    }
    
    printf("   +--------+----------+\n");
    printf("   Total elements: %d\n", pq->size);
}

// Change priority of an element
void changePriority(PriorityQueue* pq, int data, int newPriority) {
    int found = -1;
    
    // Find the element
    for (int i = 0; i < pq->size; i++) {
        if (pq->arr[i].data == data) {
            found = i;
            break;
        }
    }
    
    if (found == -1) {
        printf("❌ Element %d not found!\n", data);
        return;
    }
    
    // Remove from current position
    for (int i = found; i < pq->size - 1; i++) {
        pq->arr[i] = pq->arr[i + 1];
    }
    pq->size--;
    
    // Re-insert with new priority
    enqueuePQ(pq, data, newPriority);
    printf("✅ Priority changed for %d to %d\n", data, newPriority);
}

int main() {
    PriorityQueue pq;
    initPQ(&pq);
    
    int choice, data, priority;
    
    printf("╔════════════════════════════════════════╗\n");
    printf("║     Priority Queue Operations          ║\n");
    printf("║  (Higher value = Higher priority)      ║\n");
    printf("╚════════════════════════════════════════╝\n\n");
    
    while (1) {
        printf("\n📋 Menu:\n");
        printf("1️⃣  Enqueue (with priority)\n");
        printf("2️⃣  Dequeue (highest priority)\n");
        printf("3️⃣  Peek (highest priority)\n");
        printf("4️⃣  Display Queue\n");
        printf("5️⃣  Change Priority\n");
        printf("6️⃣  Exit\n");
        printf("\nEnter choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter data: ");
                scanf("%d", &data);
                printf("Enter priority: ");
                scanf("%d", &priority);
                enqueuePQ(&pq, data, priority);
                break;
            case 2:
                dequeuePQ(&pq);
                break;
            case 3:
                {
                    PQElement elem = peekPQ(&pq);
                    if (elem.data != -1)
                        printf("👁️  Highest: Data=%d, Priority=%d\n", 
                               elem.data, elem.priority);
                }
                break;
            case 4:
                displayPQ(&pq);
                break;
            case 5:
                printf("Enter data to change: ");
                scanf("%d", &data);
                printf("Enter new priority: ");
                scanf("%d", &priority);
                changePriority(&pq, data, priority);
                break;
            case 6:
                printf("👋 Exiting...\n");
                return 0;
            default:
                printf("❌ Invalid choice!\n");
        }
    }
    
    return 0;
}

Applications of Priority Queue

⚡ CPU Scheduling

Higher priority processes execute first (Shortest Job First, Priority Scheduling)

🏥 Hospital Emergency

Critical patients treated before others regardless of arrival time

🌐 Network Routing

Higher priority packets sent first in congestion control

🎮 Game Development

Event handling based on priority (critical events first)

📊 Dijkstra's Algorithm

Priority queue for finding shortest path

🗜️ Huffman Coding

Building optimal prefix codes using min-priority queue

8. Queue Applications

1. CPU Scheduling

Operating systems use queues to manage processes:

Ready Queue - Processes waiting for CPU
Device Queue - Processes waiting for I/O devices
Job Queue - Batch jobs waiting to be loaded

📊 CPU Scheduling with Queues

+--------+    +------------------+    +--------+
|  Job   |--->|   Ready Queue    |--->|  CPU   |
| Queue  |    |  [P1][P2][P3]... |    | (Exec) |
+--------+    +------------------+    +--------+
                       |
                       v
                +------------------+
                |  Device Queue    |
                |  (Waiting I/O)   |
                +------------------+

Scheduling Algorithms:
• FCFS (First Come First Serve) - Simple queue
• Round Robin - Queue with time slicing
• Priority Scheduling - Priority queue

2. Breadth First Search (BFS)

BFS uses a queue to explore nodes level by level in graphs and trees.

bfs_using_queue.c

#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100

// Simple queue for BFS
int queue[MAX_VERTICES];
int front = -1, rear = -1;

void enqueue(int v) {
    if (rear == MAX_VERTICES - 1) return;
    if (front == -1) front = 0;
    queue[++rear] = v;
}

int dequeue() {
    if (front == -1 || front > rear) return -1;
    return queue[front++];
}

bool isQueueEmpty() {
    return (front == -1 || front > rear);
}

// BFS using queue
void BFS(int graph[MAX_VERTICES][MAX_VERTICES], 
         int vertices, int start) {
    bool visited[MAX_VERTICES] = {false};
    
    // Enqueue starting vertex
    enqueue(start);
    visited[start] = true;
    
    printf("BFS Traversal: ");
    
    while (!isQueueEmpty()) {
        int current = dequeue();
        printf("%d ", current);
        
        // Visit all adjacent vertices
        for (int i = 0; i < vertices; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                enqueue(i);
                visited[i] = true;
            }
        }
    }
    printf("\n");
}

int main() {
    // Adjacency matrix representation
    int graph[MAX_VERTICES][MAX_VERTICES] = {0};
    int vertices = 6;
    
    // Adding edges
    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[1][4] = graph[4][1] = 1;
    graph[2][5] = graph[5][2] = 1;
    
    printf("Graph edges: (0-1), (0-2), (1-3), (1-4), (2-5)\n\n");
    BFS(graph, vertices, 0);
    
    return 0;
}

3. Printer Spooling

Documents sent to a printer are stored in a queue (spool) and printed in FIFO order.

User A sends Doc1 ──┐
User B sends Doc2 ──┼──► Print Queue ──► Printer
User C sends Doc3 ──┘    [Doc1][Doc2][Doc3]

Print Order: Doc1 → Doc2 → Doc3 (FIFO)

4. Buffer Management

Data streams (audio, video, network) use queues as buffers:

Keyboard Buffer - Stores keystrokes
Network Buffer - Packet queuing
Audio Buffer - Smooth playback

5. Producer-Consumer Problem

Classic synchronization problem solved using a bounded buffer (queue).

producer_consumer.c

#include <stdio.h>
#include <stdbool.h>
#define BUFFER_SIZE 5

// Shared buffer (queue)
int buffer[BUFFER_SIZE];
int buffer_count = 0;
int buffer_in = 0;
int buffer_out = 0;

// Producer adds item
void produce(int item) {
    if (buffer_count == BUFFER_SIZE) {
        printf("❌ Buffer full! Producer waits...\n");
        return;
    }
    
    buffer[buffer_in] = item;
    printf("✅ Produced: %d at position %d\n", item, buffer_in);
    
    buffer_in = (buffer_in + 1) % BUFFER_SIZE;
    buffer_count++;
}

// Consumer removes item
int consume() {
    if (buffer_count == 0) {
        printf("❌ Buffer empty! Consumer waits...\n");
        return -1;
    }
    
    int item = buffer[buffer_out];
    printf("✅ Consumed: %d from position %d\n", item, buffer_out);
    
    buffer_out = (buffer_out + 1) % BUFFER_SIZE;
    buffer_count--;
    
    return item;
}

void displayBuffer() {
    printf("\n📊 Buffer State: ");
    if (buffer_count == 0) {
        printf("[EMPTY]\n");
        return;
    }
    
    printf("[");
    int i = buffer_out;
    int count = 0;
    while (count < buffer_count) {
        printf("%d", buffer[i]);
        i = (i + 1) % BUFFER_SIZE;
        count++;
        if (count < buffer_count) printf(", ");
    }
    printf("] Count: %d/%d\n", buffer_count, BUFFER_SIZE);
}

int main() {
    int choice, item;
    
    printf("╔════════════════════════════════════════╗\n");
    printf("║    Producer-Consumer Problem Demo       ║\n");
    printf("║         (Using Circular Queue)          ║\n");
    printf("╚════════════════════════════════════════╝\n\n");
    
    while (1) {
        printf("\n📋 Menu:\n");
        printf("1️⃣  Produce (Add item)\n");
        printf("2️⃣  Consume (Remove item)\n");
        printf("3️⃣  Display Buffer\n");
        printf("4️⃣  Exit\n");
        printf("\nEnter choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter item value: ");
                scanf("%d", &item);
                produce(item);
                break;
            case 2:
                consume();
                break;
            case 3:
                displayBuffer();
                break;
            case 4:
                printf("👋 Exiting...\n");
                return 0;
            default:
                printf("❌ Invalid choice!\n");
        }
    }
    
    return 0;
}

Other Applications

📧 Email Queues

Emails processed in order received

🔄 Task Scheduling

Background tasks in operating systems

🎮 Game Queues

Matchmaking systems, event handling

📱 Messaging

WhatsApp, chat message queues

9. Complexity Analysis

Simple Queue Operations

Operation	Array Implementation	Linked List Implementation	Space Complexity
Enqueue	O(1)	O(1)	O(1)
Dequeue	O(1)	O(1)	O(1)
Peek/Front	O(1)	O(1)	O(1)
IsEmpty	O(1)	O(1)	O(1)
IsFull	O(1)	O(1)*	O(1)

*Linked list IsFull depends on system memory availability

Circular Queue Operations

Operation	Time Complexity	Space Complexity
Enqueue	O(1)	O(1)
Dequeue	O(1)	O(1)
Peek	O(1)	O(1)
IsFull	O(1)	O(1)
Display (all n elements)	O(n)	O(1)

Deque Operations

Operation	Time Complexity	Space Complexity
InsertFront	O(1)	O(1)
InsertRear	O(1)	O(1)
DeleteFront	O(1)	O(1)
DeleteRear	O(1)	O(1)
GetFront/GetRear	O(1)	O(1)

Priority Queue Operations

Implementation	Enqueue	Dequeue	Peek
Unsorted Array	O(1)	O(n) - search max	O(n)
Sorted Array	O(n) - insert position	O(1)	O(1)
Heap (Binary)	O(log n)	O(log n)	O(1)
Linked List	O(n)	O(1)	O(1)

10. Summary Table

Topic	Key Concept	Time Complexity	Key Feature
Simple Queue	FIFO - First In First Out	O(1) for enqueue/dequeue	Front deletion, Rear insertion
Array Implementation	Fixed size with front/rear pointers	O(1)	Simple, cache friendly
Linked List Implementation	Dynamic nodes with next pointers	O(1)	Dynamic size, no overflow
Circular Queue	Uses modulo arithmetic	O(1)	No false overflow, efficient space
Deque	Double ended queue	O(1)	Insert/Delete at both ends
Priority Queue	Serves by priority, not order	O(1) to O(n)	Highest priority first

Quick Comparison: Queue vs Stack

Aspect	Stack	Queue
Principle	LIFO (Last In First Out)	FIFO (First In First Out)
Insertion	Top only	Rear only
Deletion	Top only	Front only
Analogy	Stack of plates	Queue at ticket counter
Pointer	Single (top)	Two (front, rear)

When to Use Which Queue?

📋 Simple Queue

Basic FIFO requirements, simple implementations

🔄 Circular Queue

Fixed size, memory efficiency needed

🔗 Linked Queue

Unknown size, frequent size changes

⚡ Priority Queue

Urgency-based processing required

↔️ Deque

Access needed from both ends