Queue

Before we dive into circular queue, let's understand the queue data structure.

In simple terms, a queue is a linear data structure that follows the FIFO (First In First Out) principle. The elements are inserted at the rear end and removed from the front end. An example of a queue is a line of people.

Line of People

Imagine a line of people waiting to buy tickets. The person who comes first will get the ticket first. The person who comes last will get the ticket last. This is the First In First Out principle. When the line grows, new people join the line from the rear end (end of the line) and people leave the line from the front end (start of the line). These operations are called enqueue and dequeue respectively, in the queue data structure.

Circular Queue

As the name suggests, a circular queue is a queue with a circular structure - the rear end is connected to the front end.

A circular line of people may not be appealing in real life, hence we will consider a bus route with stops, where the bus starts from the first stop after the last stop. A circular route.

Circular Bus Route

Imagine a bus route with 7 stops. Namely Arch Gate, Library, Techpark, Hospital, Canteen & Playground. The bus starts from the Main Gate and goes through all the stops. After the Playground, the bus returns to the Arch Gate. This is a circular route.

The route is illustrated below:

Now, let's give a life to the bus route by implementing a circular queue.

Operations

For our bus route to function efficiently, we need to perform the following operations:

1. Enqueue: Add stops to the bus route.
2. Dequeue: Remove stops from the bus route.
3. Display: Display the bus route.

Implementation

Before implementing the bus route, let's understand the structure of the data we are trying to implement.

Bus Stop Structure

The bus stop structure will have the following fields:

1. Name: Name of the bus stop.
2. Next: Pointer to the next bus stop.

Bus Route Structure

The bus route structure is simply a collection of bus stops. In our implementation (i.e., linked list), we will use pointers front and rear to manage our stops.

Implementation

Now, let's implement the bus route structure. But hold on, what is the data type of the bus route structure? int is for integers, float is for floating-point numbers, char is for characters; what about the bus route structure? We need to define a new data type for it.

struct

In C, we can use the struct keyword to define a new data type. The struct keyword allows us to combine data items of different types.

Defining Bus Stop

As discussed earlier, the bus stop structure will have two fields: name and next. Let's define the bus stop structure.

struct stop {
    char name[20];
    struct stop *next;
};

In this snippet, we define a structure stop with two fields: name and next. The name field is an array of characters. These structures are also called self-referential structures since they contain pointers to their own type.

Defining Bus Route

Now, let's define how we manage our stops using pointers:

struct stop *front = NULL;
struct stop *rear = NULL;

This defines pointers for managing our queue's front and rear ends.

Add Stop

To add a stop to the bus route is to enqueue a bus stop. The operation is similar to adding a node to the end of the linked list.

Basically, we have to:

1. Creating a new bus stop.
2. Connecting it appropriately based on whether it's empty or not.
3. Updating pointers accordingly.

The C equivalent of the above steps is:

void enqueue(char name[]) {
    struct stop *new_stop = (struct stop *)malloc(sizeof(struct stop));
    strcpy(new_stop->name, name);

    if (front == NULL) {
        front = new_stop;
        rear = new_stop;
        rear->next = front; // Circular link
    } else {
        rear->next = new_stop; // Link current rear to new stop
        rear = new_stop; // Move rear to new stop
        rear->next = front; // Complete circular link
    }
}

In this code snippet, we define a function enqueue that takes the name of the bus stop as an argument and manages adding it correctly within our circular queue structure.

Remove Stop

To remove a stop from the bus route is to dequeue a bus stop. The operation is similar to removing a node from the beginning of the linked list.

Basically, we have to:

1. Checking if there are any stops.
2. Updating pointers accordingly.
3. Freeing memory for removed stops.

The C equivalent of the above steps is:

void dequeue() {
    if (front == NULL) return; // If empty, do nothing

    struct stop *to_delete = front;

    if (front == rear) { // Only one element in the queue
        free(to_delete);
        front = NULL;
        rear = NULL;
    } else {
        front = front->next; // Move front to next stop
        rear->next = front; // Update rear's next to point to new front
        free(to_delete); // Free old front
    }
}

In this snippet, we define a function dequeue that removes and manages memory for stops in our circular queue.

Display Bus Route

To display the bus route is to display the bus stops in the order they appear in the bus route.

Basically we have to:

1. Traverse the bus route from the Arch Gate to the last stop.
2. Display the name of each bus stop.

The C equivalent of the above steps is:

void displayRoute() {
    if (front == NULL) {
        printf("No stops available.\n");
        return;
    }

    struct stop *temp = front;
    do {
        printf("%s -> ", temp->name);
        temp = temp->next;
    } while (temp != front);

    printf("(back to %s)\n", front->name);
}

Why temp != front? Because the bus route is circular, the last stop is connected to the Arch Gate: temp->next will never be NULL. Hence, we are checking if the stop is the Arch Gate (front).

Simulate!

Now, let's simulate the bus route by adding stops, removing stops, and displaying the bus route, and finally, driving the bus!

We will assume that the bus is running at a constant speed and stops at each bus stop for 2 seconds, and the distance between each bus stop is 500 meters.

int main() {
    int speed;
    printf("Enter the speed of the bus: ");
    scanf("%d", &speed);

    int driveTime = 500 / speed;

    enqueue("Arch Gate");
    enqueue("Library");
    enqueue("Techpark");
    enqueue("Hospital");
    enqueue("Canteen");
    enqueue("Playground");

    displayQueue();

    dequeue(); // Remove a stop

    struct stop *temp = front;

    while (front != NULL) {
        printf("Bus is at %s\n", temp->name);
        temp = temp->next;
        sleep(2); 
        sleep(driveTime); 
    }

    return 0;
}

Final Implementation

The final implementation of the bus route is as follows:

#include <stdio.h>
#include <stdlib.h> // For malloc
#include <string.h> // For strcpy
#include <unistd.h> // For sleep

struct stop {
    char name[20];
    struct stop *next;
};

struct stop *front = NULL;
struct stop *rear = NULL;

void enqueue(char name[]) {
    struct stop *new_stop = (struct stop *)malloc(sizeof(struct stop));
    strcpy(new_stop->name, name);

    if (front == NULL) {
        front = new_stop;
        rear = new_stop;
        rear->next = front; // Circular link
    } else {
        rear->next = new_stop; // Link current rear to new stop
        rear = new_stop; // Move rear to new stop
        rear->next = front; // Complete circular link
    }
}

void dequeue() {
    if (front == NULL) return; // If the queue is empty, do nothing

    struct stop *to_delete = front;

    if (front == rear) { // Only one element in the queue
        free(to_delete);
        front = NULL;
        rear = NULL;
    } else {
        front = front->next; // Move front to next stop
        rear->next = front; // Update rear's next to point to new front
        free(to_delete); // Free old front
    }
}

void displayRoute() {
    if (front == NULL) {
        printf("No stops available.\n");
        return;
    }

    struct stop *temp = front;
    do {
        printf("%s -> ", temp->name);
        temp = temp->next;
    } while (temp != front);

    printf("(back to %s)\n", front->name);
}

int main() {
    int speed;
    printf("Enter the speed of the bus (m/s): ");
    scanf("%d", &speed);

    int driveTime = 500 / speed; // Time taken to travel 500 meters for the given speed

    enqueue("Temporary Stop"); // To be removed later
    enqueue("Arch Gate");
    enqueue("Library");
    enqueue("Techpark");
    enqueue("Hospital");
    enqueue("Canteen");
    enqueue("Playground");

    displayRoute();

    dequeue(); // Remove a stop from front

    struct stop *temp = front;

    while (front != NULL) {
        printf("Bus is at %s\n", temp->name);
        temp = temp->next;
        sleep(2); 
        sleep(driveTime); 
    }

    return 0;
}

Output

We have successfully implemented a circular queue using a linked list. The output of the program will be as follows:

Conclusion

In this post, we have understood and implemented a circular queue using a linked list. We have simulated a bus route with a fixed number of stops and implemented the operations enqueue, dequeue, and display. We have also driven the bus through the bus route (For a practical example).

I hope you enjoyed the post and learned something new. If you have any questions or feedback, feel free to leave a comment below.

Happy learning! 🚀