C++ Program to Implement a Queue Using Linked List

A queue is a fundamental data structure that operates on a First In First Out (FIFO) principle. In this structure, elements are added at the rear and removed from the front. This article explores how to implement a queue using a linked list in C++, providing multiple examples to demonstrate various operations and their outputs.

Prerequisites

Before diving into the implementation, you should have:

1. Basic understanding of C++ programming.
2. Familiarity with pointers and dynamic memory allocation.
3. Knowledge of linked lists and basic queue operations.

With these prerequisites, you will be able to grasp the concepts and code implementations discussed here.

1. Basic Queue Implementation Using Linked List

1.1 Node Structure and Queue Initialization

Let’s start by defining the structure of a node and initializing the queue.

#include <iostream>

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

class Queue {
public:
    Queue() : front(nullptr), rear(nullptr) {}

    void enqueue(int data) {
        Node* newNode = new Node(data);
        if (rear == nullptr) {
            front = rear = newNode;
            return;
        }
        rear->next = newNode;
        rear = newNode;
    }

    void dequeue() {
        if (front == nullptr) {
            std::cout << "Queue is empty" << std::endl;
            return;
        }
        Node* temp = front;
        front = front->next;
        if (front == nullptr) {
            rear = nullptr;
        }
        delete temp;
    }

    void display() {
        if (front == nullptr) {
            std::cout << "Queue is empty" << std::endl;
            return;
        }
        Node* temp = front;
        while (temp != nullptr) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

private:
    Node* front;
    Node* rear;
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);

    std::cout << "Queue: ";
    q.display();

    return 0;
}

1.2 Output Explanation

In this example, the queue is structured as follows:

10 -> 20 -> 30 -> 40

The output will display: Queue: 10 20 30 40

2. Advanced Queue Operations

2.1 Enqueue and Dequeue Operations using C++

Let’s demonstrate the enqueue and dequeue operations with more details.

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);

    std::cout << "Queue after enqueuing 10, 20, 30, 40: ";
    q.display();

    q.dequeue();
    std::cout << "Queue after dequeuing one element: ";
    q.display();

    q.dequeue();
    std::cout << "Queue after dequeuing another element: ";
    q.display();

    return 0;
}

2.2 Output Explanation

In this example, the queue undergoes the following transformations:

• After enqueuing 10, 20, 30, 40:10 -> 20 -> 30 -> 40 The output will display: Queue after enqueuing 10, 20, 30, 40: 10 20 30 40
• After dequeuing one element:20 -> 30 -> 40 The output will display: Queue after dequeuing one element: 20 30 40
• After dequeuing another element:30 -> 40 The output will display: Queue after dequeuing another element: 30 40

3. Handling Edge Cases

3.1 Dequeue from an Empty Queue

Let’s handle the edge case where a dequeue operation is attempted on an empty queue.

int main() {
    Queue q;

    q.dequeue();  // Attempting to dequeue from an empty queue

    q.enqueue(10);
    q.enqueue(20);

    q.dequeue();
    q.dequeue();
    q.dequeue();  // Attempting to dequeue from an empty queue again

    return 0;
}

3.2 Output Explanation

In this example, attempting to dequeue from an empty queue will produce the following output:

Queue is empty
Queue is empty

This ensures that the program handles edge cases gracefully without crashing.

Conclusion

A C++ program to implement a queue using a linked list involves defining the node structure and implementing various operations such as enqueue, dequeue, and display. This article provided a detailed implementation of these operations along with multiple examples to illustrate their functionality