How to implement a queue in C?

Queues are fundamental data structures that follow the First-In-First-Out (FIFO) principle, making them suitable for scenarios where the order of processing matters.

This comprehensive guide explores the implementation of queues in C, covering the basics of queues, operations, and a practical example to illustrate their usage.

1. Introduction to Queues

A queue is a linear data structure that follows the FIFO principle. Elements are added at the rear (enqueue) and removed from the front (dequeue). This ensures that the first element added is the first to be processed.

2. Basic Operations on Queues

2.1. Enqueue Operation

Enqueue adds an element to the rear of the queue.

void enqueue(int data);

2.2. Dequeue Operation

Dequeue removes an element from the front of the queue.

int dequeue();

2.3. Front Operation

Front retrieves the front element without removing it.

int front();

2.4. Is Empty Operation

Is Empty checks if the queue is empty.

int is_empty();

2.5. Is Full Operation (Optional)

For a fixed-size queue, Is Full checks if the queue has reached its capacity.

int is_full();

3. Implementation of a Queue in C

Let's implement a basic queue using an array:

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

#define MAX_SIZE 100

struct Queue {
    int items[MAX_SIZE];
    int front;
    int rear;
};

// Function to initialize an empty queue
void initialize(struct Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// Function to check if the queue is empty
int is_empty(struct Queue* q) {
    return (q->front == -1 && q->rear == -1);
}

// Function to check if the queue is full
int is_full(struct Queue* q) {
    return (q->rear == MAX_SIZE - 1);
}

// Function to add an element to the rear of the queue
void enqueue(struct Queue* q, int value) {
    if (is_full(q)) {
        printf("Queue is full. Cannot enqueue.\n");
        return;
    }

    if (is_empty(q)) {
        q->front = 0;
        q->rear = 0;
    } else {
        q->rear++;
    }

    q->items[q->rear] = value;
    printf("%d enqueued to the queue.\n", value);
}

// Function to remove an element from the front of the queue
int dequeue(struct Queue* q) {
    int removed;

    if (is_empty(q)) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1;  // Return an error value
    } else if (q->front == q->rear) {
        removed = q->items[q->front];
        q->front = -1;
        q->rear = -1;
    } else {
        removed = q->items[q->front];
        q->front++;
    }

    printf("%d dequeued from the queue.\n", removed);
    return removed;
}

// Function to retrieve the front element without removing it
int front(struct Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty.\n");
        return -1;  // Return an error value
    }

    return q->items[q->front];
}

// Function to display the elements of the queue
void display(struct Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty.\n");
        return;
    }

    printf("Queue elements: ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->items[i]);
    }
    printf("\n");
}

int main() {
    struct Queue myQueue;
    initialize(&myQueue);

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

    display(&myQueue);

    int frontElement = front(&myQueue);
    printf("Front element: %d\n", frontElement);

    int dequeued = dequeue(&myQueue);
    printf("Dequeued element: %d\n", dequeued);

    display(&myQueue);

    return 0;
}

In this example, we've implemented a queue using an array and provided functions for basic operations.

The initialize function sets the initial state of the queue, and the display function shows the elements currently in the queue.

4. Conclusion

Queues are versatile data structures with applications ranging from task scheduling to printer queues.

Understanding the basics of queues and their implementation in C enables programmers to efficiently handle scenarios where the order of processing is crucial.

By incorporating enqueue, dequeue, and other operations, C developers can create robust queue-based solutions, contributing to the effectiveness and efficiency of their programs.