Mastering Queue Implementation in C++: A Comprehensive Guide

Queues in C++ resemble real-life queues in a lot of things. Queues work on the principle of FIFO(First In First Out). The element that enters the queue first exits the queue First. We add elements to the rear and remove elements from the first. Today we are going to be implementing the list using nodes. the implementation is using linked list. We are using nodes. If you do not know how the node class works or how nodes work you can check this article out. It is about how to rotate a Singly Linked List but it has an explanation of the Node class in it. The code also has comments so that would help you too let’s start first we will create a node class.

class node { // node class
private: 
    int data;//data part
    node* next;//address part
public:
    node() {
        data = 0;//initializing data with 0
        next = NULL;//pointing to NULL.
    }
    node(int data) {
        this->data = data;//assigning data to data variable
        this->next = NULL;//pointing to NULL
    }
    void setdata(int data) {//setter for data
        this->data = data;
    }
    void setnext(node* next) {//setter for address
        this->next = next;
    }
    int getdata() {//getter for data
        return this->data;
    }
    node* getnext() {//getter for address
        return this->next;
    }
};

What this code is doing if you don’t Understand? We are creating a class node. Now I do want to mention you might see many implementations of this using struct Online on many platforms I did it with class because I find it Simpler This way. So the code has 2 variables one is int type to store data the other One is a pointer of the class Node Type so it can store the address of the next node in the linked list. It has a default constructor to initialize the variables the pointer is pointed to null because we cannot know what we will be pointing to beforehand. Moving on we will create the QUEUE class.

class queue {
private:
    node* front;//queue start
    node* rear;//queue end
public:
    queue() {
        this->front = NULL;//pointing front to NULL
        this->rear = NULL;//pointing end to NULL
    }
    void enqueue(int data) {
        node* New = new node(data);//new node with the data.
        if (rear == NULL) {//if the end is NULL means the queue is empty
            front = New;//front is the new node
            rear = New;//end is also the new node
        }
        else {
            rear->setnext(New);// else last node points to the ne node
            rear = New;// and the new node is now the last node
        }
    }
    void dequeue(){

        /*Queues work on the concept of First IN First Out that is 
        why we will dequeue from the start*/

        node* temp = front;//Starting from front
        front = front->getnext();//move front one step Ahead
        delete(temp);//freeing memory from the spot that is just dequeued
    }
    void display() {
        //we display from start
        node* temp = front;//getting a temp pointer pointing to front
        while (temp != NULL) {//while temp does not reaches end 
            cout << temp->getdata() << endl;//we print its data
            temp = temp->getnext();//we move temp to next data.
        }
    }
};

In this queue Class, we are creating two dynamic node-type objects called front and rear to track the front and the rear of the Queue. The default constructor initializes both Pointers as NULL. In the enqueue function we create a new dynamic type node and initialize it with data. then we check if (rear == NULL) this means the queue is yet Empty because the end has not moved forward yet. so we initialize the front of the queue and the rear of the queue to the same Node.

In the Else Part, we are pointing the current rear node whichever it is to the new node and after that, we are going to be setting the new node as the rear node. Take it like this we are using the rear Dynamic Node-type object to point to the new node and then we need to shift the end to the new Node.

As pointed out by a valued reader Pm that the queue would leak its content if its destroyed when it has elements in it. And it was indeed a part which I missed in my original article so this part is added as correction where we will be implementing a Deconstructor for the queue class you can see the code below.

~queue() {
  node* current = front;//starting from the front
  while (current) { //while current is not NULL
   cout << "Node destroyed" << endl;//just so we get a noti that node is destroyed
   node* next = current->getnext();//have a pointer pointing to next node
   delete current; //delete the current node
   current = next; //move current to next
  }

1. node* current = front;: This line initializes a pointer current and sets it to point to the front node of the queue. This is the starting point for iterating through the linked list.
2. while (current): This condition ensures that the loop continues as long as the current pointer is not NULL. In other words, it iterates through the linked list until the end is reached (i.e., the current pointer becomes NULL).
3. node* next = current->getnext();: Here, a pointer next is created and assigned the address of the next node in the linked list. This is achieved by invoking the getnext() function on the current node, which returns a pointer to the next node.
4. delete current;: This line deletes the current node, freeing the memory allocated for it. This ensures that memory resources are properly released.
5. current = next;: After deleting the current node, the current pointer is updated to point to the next node (next). This step allows the loop to progress forward through the linked list.
6. cout << "Node destroyed" << endl;: This line simply outputs a message indicating that a node has been destroyed. It provides a notification or debugging information to indicate that the destruction process is taking place.

By repeating steps 2 to 6 until the end of the linked list is reached, this destructor deallocates memory for each node in the queue, effectively destroying the entire linked list. The code ensures that no memory leaks occur by properly freeing the memory for each node.

check out timelapse of this code below