C Program to Implement a Queue Using Union

Welcome to another exciting blog post where we will explore the implementation of a queue using a union in the C programming language. If you are new to programming or want to learn more about queues and unions, you’ve come to the right place. By the end of this post, you will have a solid understanding of how to create a queue using a union in C.

Introduction to Queues

Before we dive into the implementation details, let’s first understand what a queue is. A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Just like waiting in a queue in real life, the items you add first will be the first ones to be removed.

Imagine a line of people waiting for a concert. The person who arrived first will enter the concert first, followed by the second person, and so on. In programming terms, each person waiting in the line represents an element in a queue.

Queues are commonly used in various algorithms, such as breadth-first search, job scheduling, and many more. Understanding queues and their implementation is essential for any programmer.

Implementing a Queue Using Union

To implement a queue using a union, we will utilize C’s powerful data type called union. A union is a user-defined data type that allows storing different types of data in the same memory location. This flexibility makes unions particularly useful when dealing with different types of data, such as integers, characters, and pointers.

Our queue implementation will consist of a union called QueueNode and a structure called Queue. The QueueNode union will store the data and a pointer to the next node, while the Queue structure will keep track of the front and rear pointers of the queue.

Let’s look at the code implementation:

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

union QueueNode {
    int data;
    struct QueueNode* next;
};

typedef struct Queue {
    struct QueueNode *front, *rear;
} Queue;

In the code snippet above, we have defined the QueueNode union which can hold either an integer value or a pointer to the next node. We have also defined the Queue structure which holds pointers to the front and rear nodes of the queue.

Initializing an Empty Queue

To start using our queue, we need to initialize it by assigning NULL to both front and rear pointers. This indicates that the queue is empty. We can achieve this by creating a function called initializeQueue.

void initializeQueue(Queue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

The initializeQueue function takes a pointer to a Queue structure as its parameter and assigns NULL to both the front and rear pointers.

Enqueue – Adding Elements to the Queue

When we enqueue an element, we are adding it to the rear of the queue. To accomplish this, we need to create a function called enqueue that takes the queue and the data to be added as parameters.

void enqueue(Queue* queue, int data) {
    struct QueueNode* newNode = (struct QueueNode*) malloc(sizeof(struct QueueNode));
    newNode->data = data;
    newNode->next = NULL;

    if (queue->rear == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

In the enqueue function, we first allocate memory for a new node using the malloc function. We assign the data and set the next pointer to NULL. If the queue is empty (i.e., rear is NULL), we update both the front and rear pointers to point to the new node. Otherwise, we update the rear’s next pointer to the new node and move the rear pointer forward.

Dequeue – Removing Elements from the Queue

When we dequeue an element, we are removing it from the front of the queue. To implement this functionality, we need to create a function called dequeue.

int dequeue(Queue* queue) {
    if (queue->front == NULL) {
        printf("Queue is empty.\n");
        return -1;
    }

    int data = queue->front->data;
    struct QueueNode* temp = queue->front;

    queue->front = queue->front->next;
    free(temp);

    if (queue->front == NULL) {
        queue->rear = NULL;
    }

    return data;
}

In the dequeue function, we first check if the queue is empty by checking if the front pointer is NULL. If it is, we print a message indicating that the queue is empty and return -1 (assuming -1 is not a valid data value). Otherwise, we store the data from the front of the queue, update the front pointer to point to the next node, free the memory of the previous front node, and update the rear pointer if the queue becomes empty.

Viewing the Front Element

To get the element at the front of the queue without removing it, we can create a function called peek.

int peek(Queue* queue) {
    if (queue->front == NULL) {
        printf("Queue is empty.\n");
        return -1;
    }

    return queue->front->data;
}

The peek function first checks if the front pointer is NULL to determine if the queue is empty. If it is, we print a message and return -1. Otherwise, we return the data value from the front of the queue.

Checking if the Queue is Empty

To verify if the queue is empty, we can create a function called isEmpty.

int isEmpty(Queue* queue) {
    return queue->front == NULL;
}

The isEmpty function simply checks if the front pointer is NULL and returns 1 if it is, indicating that the queue is empty. Otherwise, it returns 0 to indicate that the queue is not empty.

Putting it All Together

Now that we have implemented the necessary functions to create, enqueue, dequeue, peek, and check if the queue is empty, let’s see how we can use these functions to manipulate a queue.

int main() {
    Queue queue;
    initializeQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Front element: %d\n", peek(&queue));

    printf("Dequeued elements: %d ", dequeue(&queue));
    printf("%d ", dequeue(&queue));
    printf("%d\n", dequeue(&queue));

    if (isEmpty(&queue)) {
        printf("Queue is empty.\n");
    } else {
        printf("Queue is not empty.\n");
    }

    return 0;
}

In the main function, we declare a Queue structure and initialize it using the initializeQueue function. We then enqueue three elements into the queue using enqueue. We print the front element of the queue using peek.

Next, we dequeue all the elements from the queue, printing each value as we go. After dequeuing all the elements, we check if the queue is empty using isEmpty and print the appropriate message.

Conclusion

Congratulations! You have successfully implemented a queue using a union in the C programming language. We covered the basics of queues, their importance, and how to create a queue using a union. We explored functions to initialize, enqueue, dequeue, peek, and check the emptiness of a queue. You are now equipped with the knowledge to work with queues in your own programs.

Now that you have a solid understanding of queues, feel free to explore more advanced queue operations and algorithms. You can also apply the concepts learned here to solve programming problems that involve queues. Keep practicing, and happy coding!