C++ 模板类实现循环队列 - 代码详解与示例 - 常规

C++ 模板类实现循环队列 - 代码详解与示例

本文将详细解释使用 C++ 模板类实现循环队列的代码，并附带示例说明。

循环队列是一种线性数据结构，它允许在队列末尾添加元素，并在队列头部删除元素。循环队列使用数组实现，并且在数组已满时，可以将队尾指向数组的头部，从而实现循环的效果。

代码:

template <typename T>
class CircularQueue {
private:
    vector<T> data;
    int head;
    int tail;
    int size;
public:
    CircularQueue(int k) {
        data.resize(k);
        head = -1;
        tail = -1;
        size = k;
    }
    bool enqueue(T item) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = item;
        return true;
    }
    bool dequeue() {
        if (isEmpty()) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }
    T front() {
        if (isEmpty()) {
            return T();
        }
        return data[head];
    }
    bool isFull() {
        return (tail + 1) % size == head;
    }
    bool isEmpty() {
        return head == -1;
    }
};

代码解释:

template <typename T>: 声明一个模板类，T 代表数据类型，可以是任何类型。
class CircularQueue { ... }: 定义一个名为 CircularQueue 的循环队列类。
private:: 定义私有成员，这些成员只能被类内部访问。
- vector<T> data;: 使用 vector 容器存储队列中的数据，T 代表数据类型。
- int head;: 记录队列头部的索引。
- int tail;: 记录队列尾部的索引。
- int size;: 记录队列的大小（即数组的大小）。
public:: 定义公有成员，这些成员可以被外部访问。
- CircularQueue(int k): 构造函数，初始化一个大小为 k 的循环队列。
  - data.resize(k);: 将 vector 容器的大小调整为 k。
  - head = -1;: 初始化队列头部索引为 -1，表示队列为空。
  - tail = -1;: 初始化队列尾部索引为 -1，表示队列为空。
  - size = k;: 记录队列的大小。
- bool enqueue(T item): 入队操作，将元素 item 添加到队列的尾部。
  - if (isFull()) { ... }: 判断队列是否已满，如果已满，则返回 false，表示入队失败。
  - if (isEmpty()) { ... }: 判断队列是否为空，如果为空，则将头部索引设置为 0。
  - tail = (tail + 1) % size;: 将尾部索引移动到下一个位置，并使用模运算 % 来实现循环，如果尾部索引超出数组边界，则将它循环到数组的头部。
  - data[tail] = item;: 将元素 item 存储到尾部索引位置。
  - return true;: 表示入队成功。
- bool dequeue(): 出队操作，从队列的头部删除一个元素。
  - if (isEmpty()) { ... }: 判断队列是否为空，如果为空，则返回 false，表示出队失败。
  - if (head == tail) { ... }: 判断队列中是否只有一个元素，如果只有一个元素，则将头部索引和尾部索引都设置为 -1，表示队列为空。
  - head = (head + 1) % size;: 将头部索引移动到下一个位置，并使用模运算 % 来实现循环。
  - return true;: 表示出队成功。
- T front(): 获取队列头部的元素。
  - if (isEmpty()) { ... }: 判断队列是否为空，如果为空，则返回 T 类型对象的默认值。
  - return data[head];: 返回队列头部的元素。
- bool isFull(): 判断队列是否已满。
  - return (tail + 1) % size == head;: 如果尾部索引的下一个位置等于头部索引，则表示队列已满。
- bool isEmpty(): 判断队列是否为空。
  - return head == -1;: 如果头部索引为 -1，则表示队列为空。

示例:

int main() {
    CircularQueue<int> q(5); // 初始化一个大小为 5 的循环队列
    q.enqueue(1); // 入队元素 1
    q.enqueue(2); // 入队元素 2
    q.enqueue(3); // 入队元素 3
    cout << q.front() << endl; // 输出队列头部的元素，输出结果为 1
    q.dequeue(); // 出队一个元素
    cout << q.front() << endl; // 输出队列头部的元素，输出结果为 2
    return 0;
}

总结:

本文详细解释了使用 C++ 模板类实现循环队列的代码，并附带示例说明。循环队列是一种重要的数据结构，可以用于实现各种应用，例如缓存、生产者-消费者模型等。