How can I implement queues using lists in C++?

How can I implement queues using lists in C++?

You can implement a queue using a linked list by creating a Node structure and maintaining pointers for the front and rear.

Can you show me a simple code example?

Sure! Here's a basic implementation:

struct Node {
    int data;
    Node* next;
};

class Queue {
    Node* front;
    Node* rear;
public:
    Queue() : front(nullptr), rear(nullptr) {}

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

    void dequeue() {
        if (front) {
            Node* temp = front;
            front = front->next;
            delete temp;
            if (!front) rear = nullptr;
        }
    }
};

This code defines a simple queue with enqueue and dequeue operations.

What if I want to implement additional features like size or isEmpty?

You can add a size variable to keep track of the number of elements and an isEmpty method to check if the queue is empty. Here's how:

class Queue {
    Node* front;
    Node* rear;
    int size;
public:
    Queue() : front(nullptr), rear(nullptr), size(0) {}

    void enqueue(int value) {
        Node* newNode = new Node{value, nullptr};
        if (rear) {
            rear->next = newNode;
        } else {
            front = newNode;
        }
        rear = newNode;
        size++;
    }

    void dequeue() {
        if (front) {
            Node* temp = front;
            front = front->next;
            delete temp;
            size--;
            if (!front) rear = nullptr;
        }
    }

    int getSize() const { return size; }
    bool isEmpty() const { return size == 0; }
};

Thanks! This is really helpful.