C# 实现泛型动态循环数组队列的方法

核心设计思路

队列（Queue）是一种先进先出（FIFO）的数据结构。若使用普通数组实现，每次出队后整体移动元素会导致性能下降。采用循环数组可以复用空闲空间，但需解决以下两个问题：

• 索引循环计算：当索引到达数组末尾时，需回到开头继续存储或读取。
• 动态扩容与缩容：为防止内存溢出或浪费，需在容量不足时倍增扩容，在剩余元素较少时减半缩容。

基础版本：固定容量循环队列

首先实现一个基础框架，仅包含入队、出队、判空和计数功能，暂不包含自动扩容逻辑。

using System;

namespace DataStructure
{
    /// <summary>
    /// 固定容量的泛型循环数组队列
    /// </summary>
    public class ArrayQueue<T>
    {
        private int capacity;
        private int startIndex;
        private int endIndex;
        private int count;
        private T[] array;

        public ArrayQueue(int capacity)
        {
            this.capacity = capacity;
            this.array = new T[capacity];
        }

        public int Count => count;
        public bool IsFull => count == capacity;
        public bool IsEmpty => count == 0;

        /// <summary>
        /// 入队操作
        /// </summary>
        public void Enqueue(T element)
        {
            if (IsFull)
                throw new InvalidOperationException("The queue is full.");

            array[endIndex] = element;
            // 使用取模运算实现索引循环
            endIndex = (endIndex + 1) % capacity;
            count++;
        }

        /// <summary>
        /// 出队操作
        /// </summary>
        public T Dequeue()
        {
            if (IsEmpty)
                throw new InvalidOperationException("The queue is empty.");

            T result = array[startIndex];
            // 重置旧位置引用，辅助 GC（可选，视数据大小而定）
            array[startIndex] = default(T);
            
            startIndex = (startIndex + 1) % capacity;
            count--;
            return result;
        }
    }
}

第1步：添加元素

将元素写入当前 endIndex 指向的位置，随后更新 endIndex 以指向下一个可用空位。公式 (index + 1) % length 确保索引在边界处正确回绕。

第2步：移除元素

记录并返回 startIndex 处的值，随后更新 startIndex 向后移动一位。此时逻辑上的队列长度 count 减一，实际物理数组并未清空，等待后续覆盖或触发缩容。

进阶版本：支持动态扩容与缩容

在生产环境中，通常期望队列具备动态调整大小的能力。以下为完整的可复用实现，包含扩容与缩容逻辑。

using System;
using System.Text;

namespace DataStructrue
{
    /// <summary>
    /// 支持动态扩容/缩容的循环数组队列
    /// </summary>
    /// <typeparam name="E"></typeparam>
    class DynamicArrayQueue<E>
    {
        private E[] data;
        private int first;
        private int last;
        private int N; // 当前元素数量

        // 默认构造函数，初始容量为10
        public DynamicArrayQueue() : this(10) { }

        public DynamicArrayQueue(int capacity)
        {
            data = new E[capacity];
            first = 0;
            last = 0;
            N = 0;
        }

        public int Count { get { return N; } }
        public bool IsEmpty { get { return N == 0; } }
        public int Capacity { get { return data.Length; } }

        /// <summary>
        /// 向尾部添加元素
        /// </summary>
        public void Add(E e)
        {
            // 如果空间不足，扩容至两倍
            if (N == data.Length)
                Resize(data.Length * 2);

            data[last] = e;
            last = (last + 1) % data.Length;
            N++;
        }

        /// <summary>
        /// 从头部移除元素
        /// </summary>
        public E RemoveFirst()
        {
            if (N == 0)
                throw new ArgumentException("Queue is empty");

            // 当元素少于总容量的四分之一时，缩容至一半
            // 防止频繁交替插入删除导致反复扩容
            if (N <= data.Length / 4 && data.Length / 2 > 0)
                Resize(data.Length / 2);

            E ret = data[first];
            data[first] = default(E); // 辅助垃圾回收
            first = (first + 1) % data.Length;
            N--;
            return ret;
        }

        /// <summary>
        /// 查看队头元素（不移除）
        /// </summary>
        public E Peek()
        {
            if (N == 0)
                throw new ArgumentException("Queue is empty");
            return data[first];
        }

        /// <summary>
        /// 私有方法：调整数组容量
        /// 注意：必须保持元素的相对顺序
        /// </summary>
        private void Resize(int newSize)
        {
            E[] newData = new E[newSize];
            for (int i = 0; i < N; i++)
            {
                newData[i] = data[(first + i) % data.Length];
            }
            data = newData;
            first = 0;
            last = N;
        }

        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            res.AppendFormat("Queue: Count = {0}, Capacity = {1}\n[", N, data.Length);
            for (int i = 0; i < N; i++)
            {
                res.Append(data[(first + i) % data.Length]);
                if (i != N - 1)
                    res.Append(", ");
            }
            res.Append(']');
            return res.ToString();
        }
    }
}

第3步：处理扩容逻辑

当 Count == Capacity 时，说明物理空间已耗尽。此时创建一个新数组，长度为原长度的 2倍。由于原数组可能已经“首尾相接”，不能直接拷贝，而应通过 (first + i) % length 的顺序遍历原数组，并将元素连续存入新数组中。最后替换引用，并将 first 重置为 0。

第4步：处理缩容逻辑

为了防止用户在频繁入队和出队的场景下触发多次无意义的扩容（震荡），引入阈值判断。只有当元素数量小于容量的 1/4 且当前容量大于特定下限（如 2）时才执行缩容。缩容至原容量的 1/2。缩容同样需要重新排列元素，使其在新数组中连续存放。

性能对比与总结

1. 时间复杂度：Add 和 RemoveFirst 的平均时间复杂度均为 O(1)。仅在触发扩容或缩容时会产生 O(N) 的开销，但由于分摊到每次操作上，均摊复杂度仍为 O(1)。
2. 内存优势：相比普通线性数组队列（每次出队后移动元素），本实现无需移动数据，节省了内存带宽和 CPU 周期。
3. 局限性：该结构主要用于标准的队列场景。如果需要支持随机访问（通过索引获取任意位置元素），则需要额外的逻辑转换或改用 List 结构。