Queues | Data Structures

Introduction

A queue is a linear data structure that follows the First In First Out (FIFO) principle. In a FIFO data structure, the first element added to the queue will be the first one to be removed. Queues are widely used in many applications such as scheduling, buffering, and in the implementation of other data structures.

Basic Operations

The basic operations of a queue are:

Enqueue: Add an element to the end of the queue.
Dequeue: Remove an element from the front of the queue.
Front: Get the front element of the queue.
Rear: Get the last element of the queue.
isEmpty: Check if the queue is empty.
isFull: Check if the queue is full (for queues with capacity).

Queue Implementation using Arrays

Let's implement a queue using an array in C.

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

#define MAX 100

typedef struct {
    int items[MAX];
    int front, 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;
}

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

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));

    printf("After dequeue, front element is %d\n", front(&q));

    return 0;
}

Queue Implementation using Linked List

Let's implement a queue using a linked list in C.

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

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

typedef struct {
    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;
    }
}

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;
    free(temp);

    if (q->front == NULL) {
        q->rear = NULL;
    }
    return data;
}

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));

    printf("After dequeue, front element is %d\n", front(&q));

    return 0;
}

Applications of Queues

Queues are used in various applications such as:

CPU scheduling: Queues are used to manage processes in various scheduling algorithms.
Disk scheduling: Queues help in managing the order of disk access requests.
Print spooling: Print jobs are managed using queues.
Handling of interrupts: Queues manage the sequence of interrupt handling.
Breadth-First Search (BFS): BFS algorithm uses queues to explore graph nodes level by level.

Queues in C

Introduction

Basic Operations

Queue Implementation using Arrays

Queue Implementation using Linked List

Applications of Queues