Queue (Linked List Implementation), Code ↔ Language

Creation of Queue (Linked List Implementation)

class Queue {
private:
    struct Node {
        int data;
        Node* next;
        Node(int val) {
            data = val;
            next = nullptr;
        }
    };

    Node* front;
    Node* rear;

public:
    // Constructor to initialize queue
    Queue() {
        front = nullptr;
        rear = nullptr;
    }
};

1. First, we will create a class named Queue.

2. It will contain a struct Node with the following properties:

   • int data: Stores the value of the node.
   • Node* next: Points to the next node in the queue.
   • Node(int val): Constructor to initialize data with val and next with nullptr.

3. It will contain two properties:

   • Node* front: Points to the front node of the queue.
   • Node* rear: Points to the rear node of the queue.

4. We will declare a constructor Queue():

   • It will initialize both front and rear pointers to nullptr, indicating an empty queue.

Enqueue Operation

void enqueue(int item) {
    Node* newNode = new Node(item);
    if (isEmpty()) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

We will define a method enqueue(int item):

• It will take an integer item as input, which is the value to be added to the queue.
• We will create a new node with the given item.
• If the queue is empty (checked using isEmpty()), we will set both front and rear to point to the new node.
• If the queue is not empty, we will link the current rear node's next to the new node and then update rear to point to the new node.

Dequeue Operation

void dequeue() {
    if (isEmpty()) {
        cout << "Queue is empty. Cannot dequeue." << endl;
        return;
    }
    Node* temp = front;
    front = front->next;
    if (front == nullptr) {
        rear = nullptr;
    }
    delete temp;
}

We will define a method dequeue():

• It will remove an element from the front of the queue.
• We will check if the queue is empty (using isEmpty()); if so, it will print "Queue is empty. Cannot dequeue." and return.
• Otherwise, we will store the front node in a temporary variable temp, then update front to point to the next node in the queue.
• If front becomes nullptr after updating (indicating the queue is now empty), we will also set rear to nullptr.
• Finally, we will delete the temporary temp node to free the memory.

isEmpty Operation

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

We will define a method isEmpty():

• It will return true if front is nullptr, indicating that the queue is empty.
• Otherwise, it will return false.

Full Code Implementation

#include <iostream>
using namespace std;

class Queue {
private:
    struct Node {
        int data;
        Node* next;
        Node(int val) {
            data = val;
            next = nullptr;
        }
    };

    Node* front;
    Node* rear;

public:
    // Constructor to initialize queue
    Queue() {
        front = nullptr;
        rear = nullptr;
    }

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

    // Enqueue operation
    void enqueue(int item) {
        Node* newNode = new Node(item);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    // Dequeue operation
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty. Cannot dequeue." << endl;
            return;
        }
        Node* temp = front;
        front = front->next;
        if (front == nullptr) {
            rear = nullptr;
        }
        delete temp;
    }

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