Data Structures and Algorithms in C (DSA)

📘 Queue (Simple, Circular, Deque)

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. The element added first is removed first — like a real-life line (queue) at a ticket counter.

📌 Real-World Applications

• Printer task scheduling
• Operating system job scheduling
• Data buffering (e.g., keyboard buffer, IO queues)
• Customer service request handling

🔢 Basic Operations

• Enqueue: Insert item at rear
• Dequeue: Remove item from front
• Front: Access front element
• isEmpty / isFull: Check state of queue

🔧 Queue Using Array (Static Queue)

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

void enqueue(int val) {
    if (rear == SIZE - 1)
        printf("Queue Overflow\n");
    else {
        if (front == -1) front = 0;
        queue[++rear] = val;
    }
}

int dequeue() {
    if (front == -1 || front > rear)
        printf("Queue Underflow\n");
    else
        return queue[front++];
}
  

🔁 Circular Queue

A Circular Queue connects rear back to front in a circular fashion to efficiently use space.

• Prevents wasted space when front index moves forward
• Common in IO buffers

⏪ Double Ended Queue (Deque)

Deque stands for Double-Ended Queue — where insertion and deletion can occur at both ends.

• Input-restricted: insertion at one end, deletion both ends
• Output-restricted: deletion at one end, insertion both ends

🧱 Queue Using Linked List (Dynamic Queue)

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

struct Node *front = NULL, *rear = NULL;

void enqueue(int val) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = val;
    newNode->next = NULL;
    if (rear == NULL) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

int dequeue() {
    if (front == NULL) return -1;
    int val = front->data;
    struct Node* temp = front;
    front = front->next;
    if (front == NULL) rear = NULL;
    free(temp);
    return val;
}
  

📚 Practice Tasks

• Implement static queue using array
• Write circular queue functions
• Use deque to check palindrome efficiently
• Simulate job queue with priority insertion (as bonus)

✅ Summary

• Queues follow FIFO order
• Can be static (array) or dynamic (linked list)
• Variants include Circular and Deque
• Widely used in scheduling and buffering problems

📤 Coming Next

In the next chapter, we will explore searching techniques — starting with Linear and Binary Search.