Hello there! Today, we will unveil Queues in coding, likening them to a line in a coffee shop or a queue of print requests. Queues in computer science are First-In, First-Out (FIFO) structures. Consider this example: you're at a theme park — the first person in line for the roller coaster gets on first. Today's lesson revolves around this straightforward yet powerful concept. So, let's dive in!

Let's explore the implementation of Queues in C++. An array or a linked list is ideal for implementing a Queue, but we'll showcase a simple array-based implementation for clarity. Let's define the Queue:

C++
Copy to clipboard
1#include <iostream>
2using namespace std;
3
4class Queue {
5    int front, rear, size, capacity;
6    int* array;
7
8public:
9    Queue(int capacity) {
10        this->capacity = capacity;  // Set the max size
11        front = size = 0;  // Initialize front and size
12        rear = capacity - 1; // Initialize rear
13        array = new int[this->capacity];
14    }
15
16    // Destructor to clean up resources
17    ~Queue() {
18        delete[] array;
19    }
20
21    // Will return true if the Queue is full
22    bool isFull() {
23        return (size == capacity);
24    }
25    
26    // Will return true if the Queue is empty
27    bool isEmpty() {
28        return (size == 0);
29    }
30};

In the Queue class above, the isFull() method checks if our queue is already at maximum capacity, and isEmpty() checks if the queue is empty.

When implementing classes that manage dynamic memory in C++, the Rule of Three becomes crucial. This rule indicates that if a class requires a custom destructor, it likely also requires a user-defined copy constructor and copy assignment operator. This trio of special member functions ensures that objects manage their resources correctly, preventing memory leaks and undefined behavior during object copying or assignment.

Here's how the Rule of Three applies to our Queue implementation:

C++
Copy to clipboard
1Queue(const Queue& other) : front(other.front), rear(other.rear), size(other.size), capacity(other.capacity) {
2    array = new int[capacity];
3    std::copy(other.array, other.array + capacity, array);
4}
5
6Queue& operator=(const Queue& other) {
7    if (this != &other) {
8        delete[] array;
9        front = other.front;
10        rear = other.rear;
11        size = other.size;
12        capacity = other.capacity;
13        array = new int[capacity];
14        std::copy(other.array, other.array + capacity, array);
15    }
16    return *this;
17}

Copy Constructor Queue(const Queue& other): This constructor initializes a new Queue object using an existing Queue, copying all properties: front, rear, size, and capacity, as well as dynamically allocating a new array and copying the data from the original queue. This ensures that both queues maintain their data integrity independently without sharing memory.

Copy Assignment Operator Queue& operator=(const Queue& other): It checks for self-assignment before proceeding. The operator deletes the existing array memory of the target object, then copies the attributes and data from another Queue. Memory allocation and element copying ensure that the assigning queue's contents replace the existing queue's data safely and efficiently.

By implementing the Rule of Three, our Queue class avoids potential pitfalls associated with resource management, such as memory leaks or dangling pointers, and ensures that each Queue instance can be independently managed and safely destroyed.

Enqueue, a fancy term, denotes adding an item to the queue — the item lines up at the rear. Here's how it plays out in our Queue class:

C++
Copy to clipboard
1void enqueue(int item) {
2    if (isFull()) { // Check if the queue is full
3        cout << "Queue is full\n";
4        return;
5    }
6    rear = (rear + 1) % capacity; // Move rear
7    array[rear] = item; // Add item at rear position
8    size = size + 1; // increment size
9    cout << item << " enqueued to queue\n";
10}

rear = (rear + 1) % capacity uses the modulo operator to calculate the new position for the rear pointer, ensuring it wraps around to the start of the queue when it surpasses the maximum index, thereby maintaining a circular behavior.

Just as Enqueue adds an element to our queue, Dequeue removes it. It extracts the element at the queue's front, reducing its size. However, we encounter an underflow condition if there are no elements to remove.

C++
Copy to clipboard
1int dequeue() {
2    if (isEmpty()) { // Check if the queue is empty
3        cout << "Queue is empty\n";
4        return INT_MIN;
5    }
6
7    int item = array[front]; // Item at front
8    front = (front + 1) % capacity; // Move front
9    size = size - 1; // decrement size
10    return item; // return removed item
11}

The dequeue() method checks for emptiness before fetching the item.

While it is essential to understand the queue's inner structure, we won't implement it ourselves in most cases. Instead, we will use C++'s built-in std::queue class. Think of any system that needs to handle requests in a fair, first-come-first-served order. These are all excellent candidates for using a queue. Here's how you can declare, initialize, and utilize a std::queue using C++:

C++
Copy to clipboard
1#include <iostream>
2#include <queue>
3
4int main() {
5    std::queue<int> queue;
6
7    // Add elements {0, 1, 2, 3, 4} to queue 
8    for (int i = 0; i < 5; i++)
9        queue.push(i);
10
11    // Display and remove contents of the queue.
12    std::cout << "Elements of queue: ";
13    while (!queue.empty()) {
14        std::cout << queue.front() << " ";
15        queue.pop();
16    }
17    std::cout << std::endl;
18
19    return 0;
20}

In the above example, we create an instance of std::queue<int> using C++. Key Queue operations include:

• push(): Inserts the specified element into the Queue.
• pop(): Removes the head of the Queue.
• front(): Retrieves the element at the head of the Queue without removing it.
• empty(): Checks if the Queue is empty.

C++'s std::queue class is versatile and can accommodate diverse data types.

We've learned about the Queue, its operations, and its implementation in C++. Furthermore, these techniques are fundamental for smooth functioning in daily life. They are invaluable and versatile in various applications, from data buffering in hardware to process scheduling in operating systems.

With your newfound knowledge of the Queue data structure using C++, it's time to level up! Next are some practice problems to enhance your understanding of these concepts. Let's dive in!