Implementing a Queue Using Linked Lists in C++

Queues are fundamental data structures used in various applications, such as scheduling processes in operating systems, managing requests in web servers, and handling asynchronous data. While arrays can be used to implement queues, using linked lists offers flexibility in memory management and dynamic resizing. In this article, we will explore how to implement a queue using linked lists in C++, covering key concepts, use cases, and providing actionable code snippets.

Understanding Queues and Linked Lists

What is a Queue?

A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. The primary operations associated with a queue are:

• Enqueue: Adding an element to the end of the queue.
• Dequeue: Removing an element from the front of the queue.
• Peek: Viewing the front element without removing it.
• IsEmpty: Checking if the queue is empty.

What is a Linked List?

A linked list is a data structure composed of nodes, where each node contains data and a pointer (or reference) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements since elements can be added or removed without the need for resizing, unlike arrays.

Why Use Linked Lists for Queues?

Using linked lists to implement a queue provides several advantages:

• Dynamic Size: Unlike an array, a linked list can grow or shrink as needed, making it suitable for scenarios where the maximum size of the queue is unknown.
• Efficient Operations: Adding and removing elements can be done in constant time, O(1), since we only need to update pointers.

Implementing a Queue Using Linked Lists in C++

Now that we understand the basics, let's dive into the implementation. We will create a simple queue class using a singly linked list.

Step 1: Define the Node Structure

First, we need to define a node structure for our linked list. Each node will hold data and a pointer to the next node.

struct Node {
    int data;      // Data part
    Node* next;   // Pointer to the next node

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

Step 2: Create the Queue Class

Next, we will create the Queue class, which will manage the linked list. This class will include methods for enqueueing, dequeueing, peeking, and checking if the queue is empty.

class Queue {
private:
    Node* front;  // Pointer to the front of the queue
    Node* rear;   // Pointer to the rear of the queue

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

    // Enqueue operation
    void enqueue(int value) {
        Node* newNode = new Node(value);
        if (rear == nullptr) {
            front = rear = newNode; // Queue is empty
            return;
        }
        rear->next = newNode; // Link the new node at the end
        rear = newNode;       // Update the rear
    }

    // Dequeue operation
    int dequeue() {
        if (front == nullptr) {
            throw std::runtime_error("Queue is empty!"); // Error handling
        }
        int value = front->data;
        Node* temp = front;
        front = front->next; // Move front to the next node
        if (front == nullptr) {
            rear = nullptr; // If the queue is now empty
        }
        delete temp; // Free memory
        return value;
    }

    // Peek operation
    int peek() {
        if (front == nullptr) {
            throw std::runtime_error("Queue is empty!"); // Error handling
        }
        return front->data;
    }

    // Check if queue is empty
    bool isEmpty() {
        return front == nullptr;
    }

    // Destructor to free memory
    ~Queue() {
        while (!isEmpty()) {
            dequeue(); // Deallocate each node
        }
    }
};

Step 3: Testing the Queue Implementation

Now let's test our Queue implementation to ensure it functions correctly.

#include <iostream>

int main() {
    Queue q;

    // Enqueue elements
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

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

    // Dequeue elements
    std::cout << "Dequeued: " << q.dequeue() << std::endl; // Should print 10
    std::cout << "Front element is: " << q.peek() << std::endl; // Should print 20

    std::cout << "Dequeued: " << q.dequeue() << std::endl; // Should print 20
    std::cout << "Dequeued: " << q.dequeue() << std::endl; // Should print 30

    // Check if queue is empty
    std::cout << "Is queue empty? " << (q.isEmpty() ? "Yes" : "No") << std::endl; // Should print Yes

    return 0;
}

Conclusion

Implementing a queue using linked lists in C++ offers a flexible and efficient way to manage a collection of items. This approach not only provides dynamic memory management but also ensures that queue operations remain efficient and straightforward. In this article, we covered the essential concepts of queues and linked lists, walked through a step-by-step implementation, and tested our code.

Key Takeaways:

• Queues are essential for managing data in a FIFO manner.
• Linked Lists provide dynamic sizing and efficient operations.
• The Queue class we created offers all necessary functionalities, including enqueue, dequeue, peek, and isEmpty checks.

By understanding and implementing queues with linked lists, you can enhance your programming skills and apply these concepts in various real-world scenarios. Happy coding!