Skip to content

Queues: Introduction and implementation in C

Queues

In computer programming as well as in Embedded Systems, understanding data structures is essential for solving complex problems. One such fundamental data structure is the queue. This article aims to introduce you to the concept of queues and provide a basic example of implementing a queue in C.

What is a Queue?

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. In a queue, elements are added (enqueued) at the rear (end) and removed (dequeued) from the front (beginning). The element that has been in the queue for the longest time will be dequeued first.

A real-world example of a queue is a line of people waiting at a bus stop. The person who arrives first gets on the bus first, and new people join the line at the end.

Why Use Queues?

Queues are used in various applications, such as:

  • Managing tasks in an operating system
  • Simulating real-world scenarios, like waiting in line
  • Buffering data between processes or threads
  • Handling requests in web servers

Implementing Queues in C

In C, we can implement a queue using an array or a linked list. For simplicity, we’ll use an array in our example. Note that this example uses structures and pointers.

Queue Data Structure

Let’s define a structure for our queue:

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

#define MAX_SIZE 10

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

Here, we create a structure called Queue that contains an array named data, an integer front representing the index of the front element, and an integer rear representing the index of the rear element. We also define a constant MAX_SIZE to set the maximum capacity of the queue.

Queue Operations

Now, let’s implement some basic queue operations:

Initialize Queue

Create a function to initialize the queue:

Queue* create_queue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

Check if Queue is Empty

Create a function to check if the queue is empty:

bool is_empty(Queue* queue) {
    return queue->front == -1;
}

Check if Queue is Full

Create a function to check if the queue is full:

bool is_full(Queue* queue) {
    return (queue->rear + 1) % MAX_SIZE == queue->front;
}

Enqueue

Create a function to add an element to the rear of the queue:

void enqueue(Queue* queue, int value) {
    if (is_full(queue)) {
        printf("Queue is full!\n");
        return;
    }

    if (is_empty(queue)) {
        queue->front = 0;
    }

    queue->rear = (queue->rear + 1) % MAX_SIZE;
    queue->data[queue->rear] = value;
}

Dequeue

Create a function to remove an element from the front of the queue:

int dequeue(Queue* queue) {
    if (is_empty(queue)) {
        printf("Queue is empty!\n");
        return -1;
    }

    int value = queue->data[queue->front];

    if (queue->front == queue->rear) {
        queue->front = -1;
        queue->rear = -1;
    } else {
        queue->front = (queue->front + 1) % MAX_SIZE;
    }

    return value;
}

Example Usage of the Queue

Now, let’s use the queue operations we’ve implemented in a simple example:

int main() {
    Queue* my_queue = create_queue();

    enqueue(my_queue, 1);
    enqueue(my_queue, 2);
    enqueue(my_queue, 3);

    printf("Dequeued: %d\n", dequeue(my_queue));
    printf("Dequeued: %d\n", dequeue(my_queue));

    enqueue(my_queue, 4);

    printf("Dequeued: %d\n", dequeue(my_queue));
    printf("Dequeued: %d\n", dequeue(my_queue));

    free(my_queue);

    return 0;
}

In this example, we create a queue and enqueue the values 1, 2, and 3. Then, we dequeue two elements and display their values. After that, we enqueue the value 4, and then dequeue and display the remaining elements.

The output of this example should be:

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4

Conclusion

Understanding the concept of queues and how to implement them in C is essential for any programmer. Queues are used in various applications and provide a simple way to manage tasks and data in a sequential manner. By following the example provided in this article, you can easily implement a basic queue in C and use it in your own projects.

Read Next – POSIX Queues in C: A Complete Guide to Understand and Implement – NerdyElectronics

Leave a Reply

Your email address will not be published. Required fields are marked *