What Is Queue in Data Structure Using C?

What Is Queue in Data Structure Using C?

A queue is a linear data structure in computer science that follows the First In First Out (FIFO) principle. It is an ordered collection of elements where insertions are done at one end, called the rear, and deletions are done at the other end, known as the front. In this tutorial, we will explore how to implement a queue in C programming language.

The Basic Operations on a Queue

A queue supports two primary operations:

• Enqueue: This operation adds an element to the rear of the queue.
• Dequeue: This operation removes an element from the front of the queue.

Implementation of a Queue in C

To implement a queue in C, we can use an array or linked list. Here, we will demonstrate the array-based implementation.

We start by defining a structure that represents a queue:

struct Queue {
    int capacity; // maximum number of elements in the queue
    int front; // index of the front element
    int rear; // index of the rear element
    int size; // current size of the queue
    int* array; // dynamically allocated array to store elements
};

The above structure contains various members:

• capacity: It represents the maximum number of elements that can be stored in the queue.
• front: It keeps track of the index of the front element.
• rear: It keeps track of the index of the rear element.
• size: It represents the current size of the queue.
• array: It is a dynamically allocated array used to store elements.

We can initialize a queue using the following function:

struct Queue* createQueue(int capacity) {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = 0;
    queue->rear = -1;
    queue->size = 0;
    queue->array = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

This function dynamically allocates memory for the structure and array, initializes the front, rear, and size, and returns a pointer to the created queue.

The Enqueue Operation

The enqueue operation adds an element to the rear of the queue. It involves checking if there is space available in the queue and updating relevant indices and size information. Here’s how we can implement it:

void enqueue(struct Queue* queue, int item) {
    if (queue->rear == queue->capacity - 1) {
        printf("Queue is full. Unable to enqueue.\n");
        return;
    }
  
    // Increment rear index and add item at that index
    ++(queue->rear);
    queue->array[queue->rear] = item;
  
    // Increment size
    ++(queue->size);
}

If the rear index is equal to (capacity – 1), it means that the queue is full, and further insertions are not possible. In such a case, we display an appropriate message and return. Otherwise, we increment the rear index, assign the item to the corresponding index in the array, and increment the size.

The Dequeue Operation

The dequeue operation removes an element from the front of the queue. It involves checking if there are any elements in the queue and updating relevant indices and size information. Here’s how we can implement it:

int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty. Unable to dequeue.\n");
        return INT_MIN;
    }
  
    int item = queue->array[queue->front];
  
    // Increment front index
    ++(queue->front);
  
    // Decrement size
    --(queue->size);
  
    return item;
}

If the queue is empty (size is 0), we display an appropriate message and return INT_MIN (a constant representing an integer not present in the queue). Otherwise, we retrieve the item at the front index, increment the front index, decrement the size, and return the item.

Conclusion

In this tutorial, you learned about queues in data structures using C programming language. We explored basic operations such as enqueue and dequeue and implemented a queue using an array-based approach. Queues are widely used in various applications where FIFO behavior is required, such as print spooling systems, task scheduling algorithms, and more.

By mastering queues and their implementations in C, you will have a powerful tool at your disposal for solving a wide range of problems efficiently.

Happy coding!