B3616 【模板】队列

队列是一种常见的数据结构，它基于先进先出（FIFO）的原则。通常，我们可以将队列想象成排队等候的人群，新来的人会排在队尾，而离开队列的人会从队头出去。

在编程中，可以使用数组或链表来实现队列。队列有两个基本操作：入队（enqueue）和出队（dequeue）。入队操作将元素添加到队列的末尾，而出队操作则从队列的头部移除一个元素。

以下是一个简单的队列模板的示例代码：

template <typename T>
class Queue {
private:
    struct Node {
        T data;
        Node* next;
        Node(T d) : data(d), next(nullptr) {}
    };

    Node* front;
    Node* rear;

public:
    Queue() : front(nullptr), rear(nullptr) {}

    ~Queue() {
        while (!isEmpty()) {
            dequeue();
        }
    }

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

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

    T getFront() {
        if (isEmpty()) {
            throw std::runtime_error("Queue is empty.");
        }
        return front->data;
    }

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

这是一个基于链表实现的队列模板，可以存储任意类型的数据。你可以使用该模板创建一个队列对象，并使用enqueue、dequeue、getFront等函数进行操作。