Implementing a Queue Data Structure in C++

Queues are fundamental data structures that play a crucial role in computer science, especially in scenarios involving scheduling, buffering, and handling requests. In this article, we’ll explore how to implement a queue data structure in C++, complete with definitions, use cases, and actionable coding insights.

What is a Queue?

A queue is an abstract data type 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. Queues are widely used in various applications, including:

• Task Scheduling: Managing tasks in operating systems.
• Data Streaming: Buffering data in applications like video streaming.
• Breadth-First Search: A graph traversal algorithm.

Basic Operations of a Queue

Before we dive into the implementation, it’s essential to understand the basic operations performed on 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/Front: Get the value of the front element without removing it.
4. IsEmpty: Check if the queue is empty.
5. Size: Get the number of elements in the queue.

Implementing a Queue in C++

Step 1: Choose Your Implementation Method

Queues can be implemented using different underlying data structures:

• Array-based Implementation: Fixed size, fast access, but can waste space.
• Linked List Implementation: Dynamic size, no wasted space, but requires more memory for pointers.

In this article, we’ll implement a queue using a linked list for its flexibility.

Step 2: Define the Node Structure

First, we need to define a node structure that will represent each element in the queue.

struct Node {
    int data;
    Node* next;

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

Step 3: Create the Queue Class

Now, we will create the Queue class that will encapsulate the queue's functionalities.

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

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

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

    void enqueue(int value);
    int dequeue();
    int peek();
    bool isEmpty();
    int size();
};

Step 4: Implementing Queue Operations

Now let’s implement the operations defined earlier.

Enqueue Operation

The enqueue method adds an element to the end of the queue.

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

    if (!front) {
        front = newNode;
    }
    count++;
}

Dequeue Operation

The dequeue method removes an element from the front of the queue.

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

    if (isEmpty()) {
        rear = nullptr;
    }
    return value;
}

Peek Operation

The peek method allows us to view the front element without removing it.

int Queue::peek() {
    if (isEmpty()) {
        throw std::out_of_range("Queue is empty");
    }
    return front->data;
}

IsEmpty and Size Methods

These methods check if the queue is empty and return the number of elements, respectively.

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

int Queue::size() {
    return count;
}

Step 5: Putting It All Together

Now that we have implemented the Queue class, let’s see how to use it in a sample program.

#include <iostream>
#include "Queue.h" // Assuming Queue class is in Queue.h

int main() {
    Queue q;

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

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

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

    return 0;
}

Conclusion

Implementing a queue data structure in C++ can be both an educational and practical exercise. By understanding and constructing a queue, you gain insight into memory management, data handling, and algorithm design. Whether it’s for task scheduling, managing data streams, or graph algorithms, queues are indispensable tools in a programmer’s toolkit.

Key Takeaways

• Choose the Right Implementation: Depending on your needs, choose between array-based or linked-list implementations.
• Understand Queue Operations: Know the basic operations and their time complexities.
• Practice: Try implementing additional features like resizing and error handling.

With this foundational knowledge, you’re now equipped to tackle a variety of problems that can benefit from queue data structures in C++. Happy coding!