Queues in C

In programming, data structures are fundamental for organizing and managing data efficiently. One of the most important data structures is the queue. In this blog post, we will explore what a queue is, its characteristics, and how to implement a queue in C. Whether you’re a beginner or experienced programmer, this guide will help you understand queues and their implementation 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 is the first one to be removed. A queue can be thought of as a waiting line: the first person to enter the line is the first to be served.

Queues are used in various applications, such as:

• Task scheduling in operating systems
• Breadth-First Search (BFS) in graph algorithms
• Message queues in communication systems

Queue Operations

A queue supports the following basic operations:

1. Enqueue: Adds an element to the rear of the queue.
2. Dequeue: Removes an element from the front of the queue.
3. Peek/Front: Returns the front element of the queue without removing it.
4. isEmpty: Checks if the queue is empty.
5. isFull: Checks if the queue is full (in the case of a fixed-size queue).

Types of Queues

1. Simple Queue: A standard queue that only supports enqueue and dequeue operations.
2. Circular Queue: A type of queue in which the last position is connected to the first position, making it circular. This helps avoid wasted space in a static queue.
3. Priority Queue: A queue where each element has a priority associated with it. Elements with higher priority are dequeued before elements with lower priority.

In this blog post, we will focus on the simple queue and how to implement it in C.

Implementing a Queue in C

To implement a queue in C, we can use either an array or a linked list. We’ll start by implementing a queue using an array.

Queue Implementation using an Array

Here is a simple implementation of a queue in C using an array:

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

#define MAX 5  // Maximum size of the queue

// Queue structure
struct Queue {
    int items[MAX];
    int front, rear;
};

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

// Check if the queue is full
int isFull(struct Queue* q) {
    return (q->rear == MAX - 1);
}

// Check if the queue is empty
int isEmpty(struct Queue* q) {
    return (q->front == -1);
}

// Add an element to the queue (Enqueue)
void enqueue(struct Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full! Cannot enqueue %d\n", value);
        return;
    }
    
    if (q->front == -1) {
        q->front = 0;  // First element
    }
    q->rear++;
    q->items[q->rear] = value;
    printf("%d enqueued to the queue\n", value);
}

// Remove an element from the queue (Dequeue)
int dequeue(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty! Cannot dequeue\n");
        return -1;
    }
    
    int item = q->items[q->front];
    
    if (q->front == q->rear) {
        q->front = q->rear = -1;  // Queue becomes empty
    } else {
        q->front++;
    }
    
    return item;
}

// Peek at the front element of the queue
int front(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->items[q->front];
}

// Display the elements of the queue
void displayQueue(struct Queue* q) {
    if (isEmpty(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 q;
    initializeQueue(&q);

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

    displayQueue(&q);

    printf("%d dequeued from the queue\n", dequeue(&q));

    displayQueue(&q);

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

    enqueue(&q, 60);
    displayQueue(&q);

    return 0;
}

Code Explanation

1. Queue Structure: We define a structure Queue with an array items[] to store the elements, and two integers front and rear to track the positions of the front and rear of the queue.
2. Initialization: The initializeQueue function sets both front and rear to -1, indicating that the queue is initially empty.
3. isFull & isEmpty: These functions check if the queue is full or empty. isFull checks if rear has reached MAX-1, while isEmpty checks if front is -1.
4. Enqueue: The enqueue function adds an element to the rear of the queue. If the queue is full, it prints a message indicating that the enqueue operation is not possible.
5. Dequeue: The dequeue function removes and returns the front element of the queue. If the queue is empty, it returns -1.
6. Front: The front function returns the front element without removing it.
7. Display: The displayQueue function prints the elements in the queue from front to rear.

Output of the Program

When you run the program, it will display the following output:

10 enqueued to the queue
20 enqueued to the queue
30 enqueued to the queue
40 enqueued to the queue
50 enqueued to the queue
Queue elements: 10 20 30 40 50
10 dequeued from the queue
Queue elements: 20 30 40 50
Front element is: 20
60 enqueued to the queue
Queue elements: 20 30 40 50 60

Advantages of Using a Queue

• Efficient: Queues are great for managing tasks that need to be processed in a specific order, such as in a task scheduling system or resource management system.
• FIFO Behavior: Queues ensure that tasks are handled in the order they arrive, which is often important in real-time applications like networking or CPU scheduling.

Conclusion

Queues are an essential data structure in computer science, and their implementation in C is straightforward. We’ve discussed how to create a simple queue, perform enqueue and dequeue operations, and manage the front and rear of the queue. With this knowledge, you can easily incorporate queues into your applications for tasks that require first-in, first-out (FIFO) processing.

If you’re interested in more advanced queue variations such as circular queues or priority queues, you can explore more in-depth topics in data structures. Happy coding!