Lecture 257:- Queue using Linked List

Here's a C++ implementation of a Queue using a linked list:

cppCopy code

#include <iostream> class Node { public:    int data;    Node* next;    Node(int data) {        this->data = data;        next = nullptr;    } }; class Queue { private:    Node* frontNode;    Node* rearNode; public:    Queue() {        frontNode = nullptr;        rearNode = nullptr;    }    bool isEmpty() {        return frontNode == nullptr;    }    void enqueue(int data) {        Node* newNode = new Node(data);        if (isEmpty()) {            frontNode = newNode;            rearNode = newNode;        } else {            rearNode->next = newNode;            rearNode = newNode;        }    }    void dequeue() {        if (isEmpty()) {            std::cout << "Queue is empty. Cannot dequeue." << std::endl;            return;        }        Node* temp = frontNode;        frontNode = frontNode->next;        delete temp;        if (frontNode == nullptr) {            rearNode = nullptr;        }    }    int front() {        if (isEmpty()) {            std::cout << "Queue is empty." << std::endl;            return -1; // Assuming -1 is not a valid element in the queue.        }        return frontNode->data;    }    int size() {        int count = 0;        Node* current = frontNode;        while (current != nullptr) {            count++;            current = current->next;        }        return count;    } }; int main() {    Queue queue;    queue.enqueue(10);    queue.enqueue(20);    queue.enqueue(30);    std::cout << "Front element: " << queue.front() << std::endl;    queue.dequeue();    std::cout << "Front element after dequeue: " << queue.front() << std::endl;    std::cout << "Queue size: " << queue.size() << std::endl;    return 0; }

In this implementation, we define a Node class to represent the nodes of the linked list. Each node contains an integer data and a pointer next to the next node in the list.

The Queue class contains two pointers, frontNode and rearNode, representing the front and rear of the queue, respectively. The frontNode points to the first element of the queue, and the rearNode points to the last element of the queue.

The member functions isEmpty(), enqueue(), dequeue(), front(), and size() work similarly to the array-based queue implementation.

In the main function, we demonstrate how to use the Queue by enqueueing and dequeueing elements and checking the front element and queue size.