What is Queue in C?

Understanding Queues in C Programming

Queues are an essential data structure in computer science and are widely used in various applications, from operating systems to network buffering. This article will delve into the concept of queues, how they are implemented in C, and their applications.

Queue in C

What is a Queue?

A queue is a linear 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. Think of a queue as a line of people waiting for a service; the person who arrives first is served first.

Key Operations of a Queue

1. Enqueue: Adding an element to the end of the queue.
2. Dequeue: Removing an element from the front of the queue.
3. Front: Getting the element at the front of the queue without removing it.
4. Rear: Getting the element at the end of the queue.
5. IsEmpty: Checking if the queue is empty.
6. IsFull: Checking if the queue is full (in case of fixed-size implementation).

Implementing a Queue in C

Queues can be implemented in C using arrays or linked lists. Below, we will cover both methods.

Queue Using Arrays

Using arrays is the simplest way to implement a queue. However, it has a limitation of fixed size, which means you need to define the maximum size of the queue at the beginning.

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

#define MAX 100

typedef struct Queue {
int items[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 (isEmpty(q)) {
q->front = 0;
}
q->items[++q->rear] = value;
printf(“Inserted %d\n”, value);
}

int dequeue(Queue *q) {
if (isEmpty(q)) {
printf(“Queue is empty!\n”);
return -1;
}
int item = q->items[q->front++];
if (q->front > q->rear) {
q->front = q->rear = -1;
}
return item;
}

int front(Queue *q) {
if (isEmpty(q)) {
printf(“Queue is empty!\n”);
return -1;
}
return q->items[q->front];
}

int rear(Queue *q) {
if (isEmpty(q)) {
printf(“Queue is empty!\n”);
return -1;
}
return q->items[q->rear];
}

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

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

printf(“Front element is %d\n”, front(&q));
printf(“Rear element is %d\n”, rear(&q));

printf(“Dequeued element is %d\n”, dequeue(&q));

return 0;
}

Queue Using Linked Lists

Using linked lists for queue implementation overcomes the fixed-size limitation. It allows the queue to grow dynamically as elements are added.

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

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

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

void initializeQueue(Queue* q) {
q->front = 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 (isEmpty(q)) {
q->front = q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
printf(“Inserted %d\n”, value);
}

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

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

int rear(Queue* q) {
if (isEmpty(q)) {
printf(“Queue is empty!\n”);
return -1;
}
return q->rear->data;
}

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

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

printf(“Front element is %d\n”, front(&q));
printf(“Rear element is %d\n”, rear(&q));

printf(“Dequeued element is %d\n”, dequeue(&q));

return 0;
}

Applications of Queues

Queues are used in a variety of real-world and computational scenarios:

1. CPU Scheduling: Managing processes in an operating system.
2. Disk Scheduling: Organizing read/write requests in a storage system.
3. Network Buffers: Handling packets in network routers.
4. Print Spooling: Managing print jobs in a printer queue.
5. Breadth-First Search (BFS): In graph algorithms.

Conclusion

Understanding Queues in C and their implementation in C is fundamental for any programmer. Whether you use arrays for simple, fixed-size queues or linked lists for more flexible implementations, mastering queues will enhance your ability to handle data efficiently in various applications. By practicing and experimenting with the provided code examples, you can gain a deeper insight into the mechanics and utilities of queues in programming.