循环队列扩容实现方案咨询——已掌握基于数组的线性队列扩容方法

循环队列的核心是利用数组的环形特性，通过front（队头索引）和rear（队尾下一个位置索引）标记有效元素范围，直接套用线性队列的扩容逻辑会破坏环形结构的设计初衷，正确的扩容实现如下：

核心思路 #

1. 扩容策略：将新容量设为原容量的2倍（而非每次+1），减少频繁扩容带来的性能损耗；若初始容量为0则默认设为1。
2. 元素迁移：原队列的有效元素可能分布在[front, 原容量-1]和[0, rear-1]两个连续区间，需分两段将元素复制到新数组的起始位置，消除环形分布。
3. 指针重置：扩容后将front置为0，rear置为当前元素总数，后续入队/出队仍通过取模运算维持环形逻辑。

示例代码 #

假设循环队列类包含以下成员变量：

• T* array：存储元素的数组指针
• uint32_t m_capacity：数组总容量
• uint32_t m_count：当前队列元素总数
• uint32_t m_front：队头元素的索引
• uint32_t m_rear：队尾下一个位置的索引

对应的扩容函数实现：

template <typename T>
void Queue<T>::Grow() {
    // 确定新容量：原容量为0则设为1，否则扩容为2倍
    const uint32_t newCapacity = m_capacity == 0 ? 1 : m_capacity * 2;
    T* newArray = new T[newCapacity];

    // 分两段复制有效元素到新数组起始位置
    uint32_t firstSegmentLen = m_capacity - m_front;
    // 复制从front到原数组末尾的元素
    std::copy(array + m_front, array + m_front + firstSegmentLen, newArray);
    // 复制从原数组开头到rear的剩余元素
    std::copy(array, array + m_rear, newArray + firstSegmentLen);

    // 释放原数组资源
    delete[] array;

    // 更新队列状态
    array = newArray;
    m_capacity = newCapacity;
    m_front = 0;
    m_rear = m_count;
}

关键说明 #

• 使用std::copy替代手动循环，代码更简洁且效率更高；
• 扩容后新数组的有效元素线性排列在起始位置，后续操作仍通过(m_rear + 1) % m_capacity这类取模运算维持环形特性；
• 明确区分m_capacity（数组总容量）和m_count（当前元素数），避免与线性队列中命名混淆的m_size变量冲突。

内容的提问来源于stack exchange，提问作者zen