Mastering Queues in C: A Comprehensive Guide

Queues are a fundamental data structure in C, widely used for storing and manipulating data. They follow the First In First Out (FIFO) principle, meaning that the first element added is the first to be removed. To illustrate this, think of a bus-ticket booking system where tickets are served on a first-come, first-served basis. In this guide, we’ll explore how queues work in C and go through the steps to implement them using arrays.

Key Operations in a C Queue

In C, a queue allows for several operations to manage its data elements. These include:

• isEmpty(): Checks if the queue is empty.
• isFull(): Determines whether the queue has reached its capacity.
• dequeue(): Removes the first element from the queue.
• enqueue(): Adds a new element to the end of the queue.
• Front: Points to the first element of the queue.
• Rear: Points to the last element of the queue.

How a Queue Data Structure Works

The queue operates based on the FIFO principle. Here’s how the process works step-by-step:

1. Initialize the Queue: Set both the Front and Rear pointers to -1. This indicates that the queue is empty.
2. Enqueue Operation: When adding a new element, check for overflow (i.e., whether the queue is full). If it’s not, increment the Rear pointer and insert the new element at that position. For the first element, set the Front to 0.
3. Dequeue Operation: When removing an element, check for underflow (i.e., whether the queue is empty). If the queue contains elements, remove the element at the Front pointer and increment the Front index. If the last element is removed, reset both pointers to -1.

Implementing a Queue in C

Queues in C can be implemented using arrays. Below is an example of how to do this:

#include <stdio.h>
# define SIZE 100

void enqueue();
void dequeue();
void show();
int inp_arr[SIZE];
int Rear = - 1;
int Front = - 1;

main() {
    int ch;
    while (1) {
        printf("1.Enqueue Operation\n");
        printf("2.Dequeue Operation\n");
        printf("3.Display the Queue\n");
        printf("4.Exit\n");
        printf("Enter your choice of operations : ");
        scanf("%d", &ch);
        switch (ch) {
            case 1: enqueue(); break;
            case 2: dequeue(); break;
            case 3: show(); break;
            case 4: exit(0);
            default: printf("Incorrect choice \n");
        }
    }
}

void enqueue() {
    int insert_item;
    if (Rear == SIZE - 1)
       printf("Overflow \n");
    else {
        if (Front == - 1) Front = 0;
        printf("Element to be inserted in the Queue\n : ");
        scanf("%d", &insert_item);
        Rear = Rear + 1;
        inp_arr[Rear] = insert_item;
    }
}

void dequeue() {
    if (Front == - 1 || Front > Rear) {
        printf("Underflow \n");
        return;
    } else {
        printf("Element deleted from the Queue: %d\n", inp_arr[Front]);
        Front = Front + 1;
    }
}

void show() {
    if (Front == - 1) {
        printf("Empty Queue \n");
    } else {
        printf("Queue: \n");
        for (int i = Front; i <= Rear; i++) {
            printf("%d ", inp_arr[i]);
        }
        printf("\n");
    }
}

Implementing a Queue Using Stacks

Queues can also be implemented using stacks. For this, you’ll need two stacks (S1 and S2). The enqueue and dequeue operations can either be made costly, depending on the implementation method.

Method 1: Costly Enqueue

• Push all elements from S1 to S2.
• Push the new element to S1.
• Push all elements from S2 back to S1.
• Deque