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

Queues are fundamental data structures used in computer science to manage data in a FIFO (First-In-First-Out) manner. In C++, implementing a queue using linked lists is a great way to understand both queues and linked lists. This article will guide you through the process, providing clear explanations, code snippets, and practical insights.

What is a Queue?

A queue is a linear data structure that follows the FIFO principle. This means that the first element added to the queue will be the first one to be removed. Queues are widely used in various applications such as:

• Task scheduling in operating systems
• Handling requests in web servers
• Managing print jobs in printers

Key Operations of a Queue

1. Enqueue: Add an element to the back of the queue.
2. Dequeue: Remove an element from the front of the queue.
3. Peek: View the front element without removing it.
4. IsEmpty: Check if the queue is empty.

Why Use Linked Lists for Queues?

While arrays can be used to implement queues, linked lists offer several advantages:

• Dynamic Size: Linked lists can grow or shrink in size as needed, unlike arrays that have a fixed size.
• Efficient Insertions/Deletions: Adding or removing elements from the front or back of a linked list is more efficient than in an array, where shifting elements is required.

Implementing a Queue Using Linked Lists in C++

Let’s implement a queue using a singly linked list in C++. We will define a Node structure to represent each element in the list and a Queue class that will manage the linked list operations.

Step 1: Define the Node Structure

The Node structure will hold the 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

The Queue class will have pointers to the front and rear of the queue, along with methods for the queue operations.

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

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

    // Function to check if the queue is empty
    bool isEmpty() {
        return front == nullptr;
    }

    // Function to add an element to the queue
    void enqueue(int value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    // Function to remove an element from the queue
    int dequeue() {
        if (isEmpty()) {
            throw std::out_of_range("Queue is empty!");
        }
        int value = front->data;
        Node* temp = front;
        front = front->next;
        delete temp;
        return value;
    }

    // Function to get the front element
    int peek() {
        if (isEmpty()) {
            throw std::out_of_range("Queue is empty!");
        }
        return front->data;
    }

    // Destructor to free the allocated memory
    ~Queue() {
        while (!isEmpty()) {
            dequeue();
        }
    }
};

Step 3: Code Explanation

• Node Structure: Each node stores an integer data and a pointer to the next node.
• Queue Constructor: Initializes the front and rear pointers to nullptr.
• isEmpty(): Checks if the queue is empty by verifying if the front pointer is nullptr.
• enqueue(int value): Adds a new node at the rear of the queue. If the queue is empty, the new node becomes both the front and rear.
• dequeue(): Removes the node from the front, returns its data, and deletes the node from memory.
• peek(): Returns the data of the front node without removing it.
• Destructor: Ensures that all nodes are deleted when the queue goes out of scope.

Step 4: Testing the Queue Implementation

Here’s how you can test the queue implementation:

#include <iostream>

int main() {
    Queue q;

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

    std::cout << "Front element: " << q.peek() << std::endl; // Outputs 10

    std::cout << "Dequeued: " << q.dequeue() << std::endl; // Outputs 10
    std::cout << "Front element: " << q.peek() << std::endl; // Outputs 20

    return 0;
}

Troubleshooting Common Issues

• Memory Leaks: Always ensure that the nodes are deleted to prevent memory leaks. Use the destructor to clean up.
• Null Pointer Exceptions: Always check if the queue is empty before performing dequeue or peek operations.

Conclusion

Implementing a queue using linked lists in C++ is a valuable exercise that enhances your understanding of data structures. This implementation is efficient, flexible, and demonstrates essential programming concepts. By following the steps outlined in this article, you can create a robust queue that can be used in various real-world applications. Whether you're working on project development or preparing for interviews, mastering this implementation will significantly enhance your programming skills. Happy coding!