What is Queue in C?

A queue in C is a fundamental data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are widely used in computer science for various applications such as task scheduling, breadth-first search in graphs, and buffering data streams.

Definition and Basic Operations

A queue typically supports the following primary operations:

1. Enqueue:

Adds an element to the end of the queue.

2. Dequeue:

Removes an element from the front of the queue.

3. Peek/Front:

Retrieves, but does not remove, the front element of the queue.

4. IsEmpty:

Checks if the queue is empty.

5. IsFull:

Checks if the queue is full (applicable in fixed-size queue implementations).

Types of Queues

There are several types of queues, each suited for different use cases:

1. Linear Queue:

The most basic form where elements are added at the rear and removed from the front.

2. Circular Queue:

A more efficient version of the linear queue where the last position is connected back to the first position to make a circle. This helps in utilizing the storage more efficiently.

3. Priority Queue:

Elements are added with a priority and dequeued based on priority rather than the order of arrival.

4. Double-ended Queue (Deque):

Allows insertion and deletion of elements from both ends.

Implementation of Queue in C

Queues can be implemented in C using arrays or linked lists. Below are the basic implementations:

Array-Based Implementation

This approach uses a fixed-size array to store the elements. Here’s a simple implementation:

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

#define MAX 100

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

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(Queue *q) {
    return q->rear == MAX - 1;
}

int isEmpty(Queue *q) {
    return q->front == -1 || q->front > q->rear;
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (q->front == -1) q->front = 0;
    q->data[++q->rear] = value;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->data[q->front++];
}

int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->data[q->front];
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("Front element is %d\n", peek(&q));

    printf("Removed %d\n", dequeue(&q));
    printf("Front element is %d\n", peek(&q));

    return 0;
}

Linked List-Based Implementation

This approach uses nodes dynamically allocated in memory. Here’s an implementation:

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

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

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

void initializeQueue(Queue *q) {
    q->front = NULL;
    q->rear = NULL;
}

int isEmpty(Queue *q) {
    return q->front == NULL;
}

void enqueue(Queue *q, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    Node *temp = q->front;
    int data = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return data;
}

int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->front->data;
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("Front element is %d\n", peek(&q));

    printf("Removed %d\n", dequeue(&q));
    printf("Front element is %d\n", peek(&q));

    return 0;
}

Advantages and Disadvantages

Advantages:

• Order:
  Maintains the order of elements as they are processed.

• Fairness:
  Ensures that each element gets processed in the order it was added.

• Simplicity:
  Simple to implement and understand.

Disadvantages:

• Fixed Size (Array-Based):
  Requires predefined size, which can lead to inefficient use of space or overflow.

• Memory Management (Linked List-Based):
  Dynamic allocation requires careful memory management to avoid leaks.

Applications

Queues are used in various scenarios such as:

1. Task Scheduling:
In operating systems, Queues in C are used for managing tasks in the CPU.
Data Streaming: Buffers data streams where data arrives at different rates.

2. Breadth-First Search:
In graph algorithms, queues help traverse levels.

In conclusion, queues are a vital data structure in C programming, offering a way to manage data in a structured and efficient manner. Understanding their implementation and applications is crucial for effective problem-solving in software development.