How to Implement a Queue Using a Linked List in C++

When it comes to data structures, queues play a crucial role in managing data in an orderly fashion. Unlike stacks, which operate on a last-in, first-out (LIFO) principle, queues follow a first-in, first-out (FIFO) approach. They are widely used in various applications, such as scheduling tasks, managing requests in servers, and facilitating breadth-first search algorithms. In this article, we will explore how to implement a queue using a linked list in C++, providing clear code examples and step-by-step instructions.

Understanding the Queue Data Structure

What is a Queue?

A queue is a linear data structure that allows insertion of elements at one end (rear) and removal of elements from the other end (front). This characteristic makes queues ideal for scenarios where order matters. In C++, queues can be implemented using arrays or linked lists, with linked lists offering dynamic memory management and efficient insertion and deletion operations.

Use Cases for Queues

Queues have numerous applications in computer science and programming, including:

• Task Scheduling: Managing processes in operating systems.
• Print Spooling: Organizing print jobs in printers.
• Breadth-First Search: Navigating graphs and trees.
• Customer Service Systems: Handling service requests in order.

Why Use a Linked List for Queue Implementation?

Using a linked list to implement a queue offers several advantages:

• Dynamic Size: Unlike arrays, linked lists can grow and shrink dynamically, making them more memory efficient.
• Efficient Insertions and Deletions: Linked lists allow O(1) time complexity for insertions and deletions at both ends, which is essential for queue operations.

Implementing a Queue Using a Linked List in C++

Step 1: Define the Node Structure

The first step in implementing a queue using a linked list is to define a Node structure. Each node will contain data and a pointer to the next node.

struct Node {
    int data;
    Node* next;

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

Step 2: Define the Queue Class

Next, we will create a Queue class that will handle the queue operations, including enqueue, dequeue, and checking if the queue is empty.

class Queue {
private:
    Node* front;
    Node* rear;

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

    // Method to add an element to the queue
    void enqueue(int value);

    // Method to remove an element from the queue
    int dequeue();

    // Method to check if the queue is empty
    bool isEmpty();

    // Destructor to clean up memory
    ~Queue();
};

Step 3: Implementing the Enqueue Operation

The enqueue function adds an element to the rear of the queue. If the queue is empty, both the front and rear pointers will point to the new node.

void Queue::enqueue(int value) {
    Node* newNode = new Node(value);
    if (rear) {
        rear->next = newNode; // Link the old rear to the new node
    }
    rear = newNode; // Update the rear pointer
    if (!front) {
        front = rear; // If the queue was empty, front points to the new node
    }
}

Step 4: Implementing the Dequeue Operation

The dequeue function removes an element from the front of the queue. If the queue becomes empty after the operation, we need to reset the rear pointer.

int Queue::dequeue() {
    if (isEmpty()) {
        throw std::out_of_range("Queue is empty");
    }
    int value = front->data; // Get the data from the front node
    Node* temp = front; // Temporary pointer to delete the front node
    front = front->next; // Move the front pointer to the next node
    if (!front) {
        rear = nullptr; // If the queue is now empty, reset rear
    }
    delete temp; // Free the memory of the old front
    return value;
}

Step 5: Implementing the isEmpty Method

The isEmpty method checks whether the queue is empty by verifying if the front pointer is null.

bool Queue::isEmpty() {
    return front == nullptr;
}

Step 6: Destructor for Memory Management

Finally, we need to implement a destructor to free up the memory used by the queue.

Queue::~Queue() {
    while (!isEmpty()) {
        dequeue(); // Dequeue all elements
    }
}

Complete Code Example

Here’s the complete code for implementing a queue using a linked list in C++:

#include <iostream>
#include <stdexcept>

struct Node {
    int data;
    Node* next;

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

class Queue {
private:
    Node* front;
    Node* rear;

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

    void enqueue(int value);
    int dequeue();
    bool isEmpty();
    ~Queue();
};

void Queue::enqueue(int value) {
    Node* newNode = new Node(value);
    if (rear) {
        rear->next = newNode;
    }
    rear = newNode;
    if (!front) {
        front = rear;
    }
}

int Queue::dequeue() {
    if (isEmpty()) {
        throw std::out_of_range("Queue is empty");
    }
    int value = front->data;
    Node* temp = front;
    front = front->next;
    if (!front) {
        rear = nullptr;
    }
    delete temp;
    return value;
}

bool Queue::isEmpty() {
    return front == nullptr;
}

Queue::~Queue() {
    while (!isEmpty()) {
        dequeue();
    }
}

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

    std::cout << "Dequeued: " << q.dequeue() << std::endl; // Output: 10
    std::cout << "Dequeued: " << q.dequeue() << std::endl; // Output: 20

    return 0;
}

Conclusion

Implementing a queue using a linked list in C++ is a powerful technique that leverages the advantages of dynamic memory allocation and efficient operations. By following the outlined steps, you can create a robust queue that can handle various tasks in your applications. Whether you're managing tasks in a scheduler or navigating through complex data structures, understanding queues will enhance your programming toolkit. Happy coding!