DEV Community

Harsh Mishra
Harsh Mishra

Posted on

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;
    }
};
Enter fullscreen mode Exit fullscreen mode
  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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)