用一个数组表示循环队列 请编写算法实现循环队列的初始化 入队和出队操作 使用C++

循环队列是一种特殊的线性表，它通过将队列的一端与另一端相连来模拟队列的“先进先出”（FIFO）特性。在数组中实现循环队列通常涉及到两个关键变量：头指针front和尾指针rear，它们分别指向队列的第一个元素和最后一个元素（下一个将入队的位置）。由于是循环结构，当 rear 达到数组末尾时，我们将它回溯到数组的起始位置。

以下是使用C++实现循环队列的基本步骤：

1. **初始化循环队列**:

class CircularQueue {
private:
    int capacity; // 队列容量
    int front; // 队首指针
    int rear; // 队尾指针

    static const int DEFAULT_CAPACITY = 100; // 默认容量
    int* queue; // 数组存储队列数据

public:
    CircularQueue() : front(0), rear(0), capacity(DEFAULT_CAPACITY), queue(new int[capacity]) {}
    ~CircularQueue() { delete[] queue; } // 析构函数释放内存
};

这里我们创建了一个构造函数，在构造时动态分配了队列数组，并初始化头尾指针。

2. **入队（enqueue）操作**:

void enqueue(int value) {
    if ((rear + 1) % capacity == front) { // 当队满时，需要扩展容量
        expandCapacity();
    }
    queue[rear] = value;
    rear = (rear + 1) % capacity; // 更新尾部指针，保持循环
}

入队操作检查是否已满，如果满则扩容，然后直接将元素存入并更新尾部指针。

3. **出队（dequeue）操作**:

int dequeue() {
    if (front == rear) { // 队空处理
        return -1; // 或者抛异常，取决于需求
    }
    int value = queue[front];
    front = (front + 1) % capacity; // 更新头部指针
    return value;
}

出队操作检查队列是否为空，如果不空就取出第一个元素，更新头部指针，并返回元素值。

4. **扩展容量（expandCapacity）**:

void expandCapacity() {
    int newCapacity = capacity * 2;
    int* newArray = new int[newCapacity];
    for (int i = front; i != rear; ++i) {
        newArray[i] = queue[(i + 1) % capacity]; // 将旧队列元素复制到新队列
    }
    newArray[rear] = queue[front]; // 如果有未移除的元素，复制一次
    delete[] queue;
    front = rear = 0;
    capacity = newCapacity;
    queue = newArray;
}

当队列满时，创建一个新的更大的数组，将旧队列元素复制到新数组，然后更新头尾指针、容量和引用指向新数组。