浅谈环形队列数据结构

环形队列（Circular Queue），也被称为环形缓冲区（Circular Buffer）或环状缓冲区（Ring Buffer）。这是一个在高性能计算、底层驱动和实时系统中极为重要和常见的数据结构。环形队列有很多应用，比如音视频处理中的平滑地处理数据流，防止卡顿；操作系统内核中的I/O缓冲区、管道(Pipe)的实现；网络通信中用于收发网络数据包的缓冲区；以及使用内存映射文件进行进程间通讯时，使用环形缓冲区能够减少锁占用。

一个永不“碰壁”的队列

想象一下一个普通的队列，就像在超市排队结账。它有一个队头（Head）和一个队尾（Tail）。新来的人排在队尾，结完账的人从队头离开。在计算机中，我们通常用数组来实现队列。但会遇到一个问题：

当元素不断地“入队”和“出队”后，Head 和 Tail 指针会一直向数组的末端移动。
即使数组前面已经空出了很多位置，当 Tail 指针到达数组的末端时，我们就无法再添加新元素了，除非我们进行一次昂贵的“数据搬移”，把所有元素都移回数组的开头。

环形缓冲区就是为了解决这个问题而生的。它的核心思想是：将数组的头和尾逻辑上连接起来，形成一个环。 当指针移动到数组的末端时，它会自动“绕”回到数组的开头，继续移动。这样，数组的空间就可以被无限次地重复利用，只要队列不满，就总有地方放新数据。

结构组成

一个环形缓冲区主要由以下几个部分组成：

一块连续的内存空间：这通常是一个固定大小的数组或在共享内存中分配的一块缓冲区。其大小被称为 容量 (Capacity)。
头指针 (front)：指向队列中第一个有效元素的位置。这是数据"被读取（出队）"的地方。
尾指针 (rear)：指向队列中最后一个有效元素之后的那个空位置。这是新数据"被写入（入队）"的地方。

环形队列在物理上仍然是基于一个定长的数组来存储数据，它的内存地址是连续的。通过指针的移动和取模运算，它在逻辑上表现为一个首尾相连的环。

工作原理与核心操作

环形缓冲区的精髓在于指针的移动方式，它依赖于模运算 (%)。模运算可以优雅地实现“绕回”这个功能。假设我们有一个容量为 N 的数组 buffer。

a) 入队 (Enqueue / Write)

检查是否已满：在写入新数据前，必须先检查缓冲区是否已满（稍后会详细讨论如何判断“满”）。如果满了，就不能再写入。
放入数据：将新数据放入 rear 指针指向的位置：buffer[rear] = data。
移动尾指针：将 rear 指针向前移动一位，如果到达末尾就绕回到开头：rear = (rear + 1) % Capacity。

b) 出队 (Dequeue / Read)

检查是否为空：在读取数据前，必须检查缓冲区是否为空。当 front == rear 时，缓冲区为空。
取出数据：从 front 指针指向的位置读取数据：data = buffer[front]。
移动头指针：将 front 指针向前移动一位，同样在需要时绕回：front = (front + 1) % Capacity。

如何区分“空”与“满”？

如何判断环形队列是“空”还是“满”是其设计的关键所在，因为 front 和 rear 指针相等时，既可能表示队列为空，也可能表示队列为满。

1. 队空 (Queue Empty) 的判断

无论采用哪种实现方式，队空的条件都是一致的： front == rear

当队头和队尾指针指向同一个位置时，表示队列中没有任何有效元素。

2. 队满 (Queue Full) 的判断

队满的判断是区分不同实现方式的关键。主要有两种经典方法：

方案一：牺牲一个存储单元（The "Wasted Slot" Method）

这是最常用、最经典的方法是：当队尾指针rear在循环意义上追上队头指针front时，即队尾指针的下一个位置是队头时，认为队列已满。

换句话说，缓冲区最多只能存储 Capacity - 1 个元素。我们永远不让 rear 指针追上 front 指针。即(rear + 1) % Capacity == front

优点：逻辑简单，只用 rear 和 head 两个指针就能完成所有判断。缺点：浪费了一个存储单元的空间，队列的最大容量是 Capacity - 1。

方案二：使用一个额外的计数器（counter/size）

可以引入一个变量 Count 来记录缓冲区中有效元素的数量。

入队操作：成功放入一个元素后，Count++。
出队操作：成功取出一个元素后，Count--。

这样判断就非常直观了：

判空条件: Count == 0
判满条件: Count == Capacity

优点：充分利用了所有存储空间。缺点：需要额外维护一个 Count 变量。在多线程并发场景下，对 Count 的读写也需要加锁或使用原子操作，可能会引入额外的性能开销。

两种实现

根据如何区分“空”与“满”，环形队列可以分为两种不同的实现，下面是C#实现。

方案一：牺牲一个存储单元（The "Wasted Slot" Method）

这种实现方式非常常见。

using System;

public class CircularQueueByWastingSpace<T>
{
    private T[] _queue;
    private int _front;
    private int _rear;
    private int _capacity;

    /// <summary>
    /// 构造函数，初始化队列
    /// </summary>
    /// <param name="capacity">队列的容量，实际可存储元素数量为 capacity - 1</param>
    public CircularQueueByWastingSpace(int capacity = 8)
    {
        // 实际数组大小需要比容量大1
        _capacity = capacity + 1;
        _queue = new T[_capacity];
        _front = 0;
        _rear = 0;
    }

    /// <summary>
    /// 获取队列中元素的数量
    /// </summary>
    public int Count
    {
        get { return (_rear - _front + _capacity) % _capacity; }
    }

    /// <summary>
    /// 检查队列是否已满
    /// </summary>
    public bool IsFull()
    {
        // 队尾指针的下一个位置是队头，则队列已满
        return (_rear + 1) % _capacity == _front;
    }

    /// <summary>
    /// 检查队列是否为空
    /// </summary>
    public bool IsEmpty()
    {
        // 队头和队尾指针相遇，则队列为空
        return _front == _rear;
    }

    /// <summary>
    /// 入队操作
    /// </summary>
    /// <param name="item">要入队的元素</param>
    /// <returns>成功返回 true，失败（队列已满）返回 false</returns>
    public bool Enqueue(T item)
    {
        if (IsFull())
        {
            Console.WriteLine("Queue is full. Enqueue failed.");
            return false;
        }
        _queue[_rear] = item;
        _rear = (_rear + 1) % _capacity; // 队尾指针后移
        return true;
    }

    /// <summary>
    /// 出队操作
    /// </summary>
    /// <param name="item">用于接收出队元素的变量</param>
    /// <returns>成功返回 true，失败（队列为空）返回 false</returns>
    public bool Dequeue(out T item)
    {
        if (IsEmpty())
        {
            Console.WriteLine("Queue is empty. Dequeue failed.");
            item = default(T);
            return false;
        }
        item = _queue[_front];
        _front = (_front + 1) % _capacity; // 队头指针后移
        return true;
    }
    
    /// <summary>
    /// 查看队头元素但不移除
    /// </summary>
    public T Peek()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty.");
        }
        return _queue[_front];
    }
}

以上代码中：

_capacity = capacity + 1;: 这是关键。如果用户期望容量为8，我们创建大小为9的数组来牺牲一个空间。
IsFull(): (_rear + 1) % _capacity == _front 是这种实现方式的核心判断逻辑。
IsEmpty(): _front == _rear 是通用的队空判断。
Enqueue 和 Dequeue: 内部都使用了 % _capacity 来实现指针的循环移动。
Count: (_rear - _front + _capacity) % _capacity 是一个计算当前元素数量的技巧。加上 _capacity 是为了防止 _rear < _front 时结果为负数。

实现二：使用计数器变量 (The "Using a Counter" Method)

这种方式在工程实践中更为常见，因为它直观且不浪费空间。

using System;

public class CircularQueueByCounter<T>
{
    private T[] _queue;
    private int _front;
    private int _rear;
    private int _count;
    private int _capacity;

    /// <summary>
    /// 构造函数，初始化队列
    /// </summary>
    /// <param name="capacity">队列的容量</param>
    public CircularQueueByCounter(int capacity = 8)
    {
        _capacity = capacity;
        _queue = new T[_capacity];
        _front = 0;
        _rear = 0;
        _count = 0;
    }

    /// <summary>
    /// 获取队列中元素的数量
    /// </summary>
    public int Count
    {
        get { return _count; }
    }

    /// <summary>
    /// 检查队列是否已满
    /// </summary>
    public bool IsFull()
    {
        return _count == _capacity;
    }

    /// <summary>
    /// 检查队列是否为空
    /// </summary>
    public bool IsEmpty()
    {
        return _count == 0;
    }

    /// <summary>
    /// 入队操作
    /// </summary>
    /// <param name="item">要入队的元素</param>
    /// <returns>成功返回 true，失败（队列已满）返回 false</returns>
    public bool Enqueue(T item)
    {
        if (IsFull())
        {
            Console.WriteLine("Queue is full. Enqueue failed.");
            return false;
        }

        // 注意：在这种实现下，rear指向的是下一个可插入的位置
        // 如果front和rear的定义是都指向元素，则逻辑会略有不同
        _queue[_rear] = item;
        _rear = (_rear + 1) % _capacity;
        _count++;
        return true;
    }

    /// <summary>
    /// 出队操作
    /// </summary>
    /// <param name="item">用于接收出队元素的变量</param>
    /// <returns>成功返回 true，失败（队列为空）返回 false</returns>
    public bool Dequeue(out T item)
    {
        if (IsEmpty())
        {
            Console.WriteLine("Queue is empty. Dequeue failed.");
            item = default(T);
            return false;
        }

        item = _queue[_front];
        _front = (_front + 1) % _capacity;
        _count--;
        return true;
    }
    
    /// <summary>
    /// 查看队头元素但不移除
    /// </summary>
    public T Peek()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty.");
        }
        return _queue[_front];
    }
}

以上代码中：

_count: 引入了 _count 变量。
IsFull(): 判断条件简化为 _count == _capacity。
IsEmpty(): 判断条件简化为 _count == 0。
Enqueue: 每次入队成功后，_count 加一。
Dequeue: 每次出队成功后，_count 减一。
这里的 _rear 同样指向下一个可插入的位置。当队列满时，_front 和 _rear 可能会重合（比如队列满，然后出队一个，再入队一个），但因为有 _count 的存在，不会产生混淆。

逻辑指针和物理指针

上述的rear或head也可以分为两种实现，一种是记录逻辑指针，一种是记录物理指针。

逻辑指针 (Logical Pointer)：逻辑指针是一个只增不减的 long 类型整数，代表着自程序启动以来写入的数据总量的“逻辑位置”。它的值可以远远超过缓冲区的实际容量。我们称之为“代时钟(Epoch Clock)”或“逻辑时钟”。
物理指针 (Physical Pointer)：这是数据在物理内存（即我们分配的数组或共享内存块）中的实际偏移量。我们通过 逻辑指针 % 容量 来得到它。

可以把逻辑指针想象成汽车的总里程表，而物理指针是它在一个环形赛道上的当前位置。只记录赛道位置，你无法知道车已经跑了多少圈，也无法知道它和前车的真实差距。而总里程表记录了全部的历史和状态，让一切计算都变得简单和明确，如果我们只是实现简单的功能，那么只记录物理指针即可。但是如果需要实现复杂的功能，比如判断头和尾的先后顺序，那就需要使用到逻辑指针。一个使用场景是：两个线程分别对一个环形缓冲区进行读和写，如果读的速度过慢，导致Head和Tail的差距过大，写入的内容可能会充满整个环形缓冲区，那么可以让写入减速一点，要实现这种功能，就需要使用逻辑指针，它很简单明了的计算两个指针的位置大小，而不用考虑“套圈”现象。

下面就物理指针和逻辑指针的分别实现：

方式一：使用物理指针 (Physical Pointers) - 主流实现

这就是我们之前讨论并编码实现的方式。

1. 指针的定义与更新

front 和 rear 变量存储的是数组的下标。
更新方式：指针的移动必须包含取模运算，以实现“环形”效果。
- front = (front + 1) % array.Length;
- rear = (rear + 1) % array.Length;

2. C# 示例回顾 (关键部分)

using System;

public class CircularQueueByPhysicalPointers<T>
{
    private T[] _queue;
    private int _front;     // 物理指针: 队头在数组中的索引
    private int _rear;      // 物理指针: 队尾下一个位置在数组中的索引
    private int _count;     // 计数器
    private int _capacity;  // 数组的总大小

    public CircularQueueByPhysicalPointers(int capacity = 8)
    {
        _capacity = capacity;
        _queue = new T[_capacity];
        _front = 0;
        _rear = 0;
        _count = 0;
    }

    /// <summary>
    /// 队列中实际元素的数量
    /// </summary>
    public int Count => _count;

    /// <summary>
    /// 检查队列是否已满
    /// </summary>
    public bool IsFull() => _count == _capacity;

    /// <summary>
    /// 检查队列是否为空
    /// </summary>
    public bool IsEmpty() => _count == 0;

    // --- 新增属性 ---

    /// <summary>
    /// 获取队列中已使用的空间数。
    /// 在物理指针+计数器的实现中，这直接就是元素的数量。
    /// </summary>
    public int UsedSpace => _count;

    /// <summary>
    /// 获取队列中剩余的可用空间数。
    /// </summary>
    public int RemainingSpace => _capacity - _count;


    public bool Enqueue(T item)
    {
        if (IsFull())
        {
            Console.WriteLine("Queue is full. Enqueue failed.");
            return false;
        }
        _queue[_rear] = item;
        _rear = (_rear + 1) % _capacity; // 物理指针循环移动
        _count++;
        return true;
    }

    public bool Dequeue(out T item)
    {
        if (IsEmpty())
        {
            item = default(T);
            return false;
        }
        item = _queue[_front];
        _front = (_front + 1) % _capacity; // 物理指针循环移动
        _count--;
        return true;
    }
    
    public T Peek()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty.");
        }
        return _queue[_front];
    }
}

使用物理指针的优点是：

直观：指针的值直接告诉我们元素在数组中的哪个位置，便于调试和理解。
高效：对于CPU来说，直接使用索引访问数组是非常快的操作。

方式二：使用逻辑指针 (Logical Pointers)

这种方式不那么常见，但在某些特定场景下（例如需要知道队列历史上一共操作了多少个元素）可能会派上用场。

1. 指针的定义与更新

front 和 rear 变量是单调递增的计数器。它们代表了从队列创建以来，总共有多少元素被出队（front）和入队（rear）。
更新方式：指针的移动就是简单的自增。
- front++;
- rear++;
物理地址转换：在实际存取数组元素时，需要将逻辑指针转换为物理索引。
- physical_index = logical_pointer % array.Length;

2. C# 示例实现

让我们用逻辑指针的方式重写“计数器法”的环形队列。

using System;

public class CircularQueueByLogicalPointers<T>
{
    private readonly T[] _queue;
    private readonly int _capacity;
    
    // front 和 rear 是逻辑指针，它们会一直增长
    private long _front; // 使用 long 类型防止溢出
    private long _rear;  // 使用 long 类型防止溢出

    public CircularQueueByLogicalPointers(int capacity = 8)
    {
        _capacity = capacity;
        _queue = new T[_capacity];
        _front = 0;
        _rear = 0;
    }

    /// <summary>
    /// 获取队列中元素的数量
    /// </summary>
    public int Count
    {
        // 逻辑指针的差值就是当前元素数量
        get { return (int)(_rear - _front); }
    }

    /// <summary>
    /// 检查队列是否已满
    /// </summary>
    public bool IsFull()
    {
        return Count == _capacity;
    }

    /// <summary>
    /// 检查队列是否为空
    /// </summary>
    public bool IsEmpty()
    {
        return _rear == _front; // 或者 Count == 0
    }

    /// <summary>
    /// 获取队列中已使用的空间数。
    /// 在逻辑指针实现中，这通过两个指针的差值直接计算得出。
    /// </summary>
    public int UsedSpace => (int)(_rear - _front);

    /// <summary>
    /// 获取队列中剩余的可用空间数。
    /// </summary>
    public int RemainingSpace => _capacity - (int)(_rear - _front);

    /// <summary>
    /// 入队操作
    /// </summary>
    public bool Enqueue(T item)
    {
        if (IsFull())
        {
            Console.WriteLine("Queue is full. Enqueue failed.");
            return false;
        }

        // 1. 将逻辑指针 rear 转换为物理索引
        int physicalIndex = (int)(_rear % _capacity);
        
        // 2. 在物理位置上存储元素
        _queue[physicalIndex] = item;
        
        // 3. 更新逻辑指针（简单自增）
        _rear++;
        
        return true;
    }

    /// <summary>
    /// 出队操作
    /// </summary>
    public bool Dequeue(out T item)
    {
        if (IsEmpty())
        {
            Console.WriteLine("Queue is empty. Dequeue failed.");
            item = default(T);
            return false;
        }

        // 1. 将逻辑指针 front 转换为物理索引
        int physicalIndex = (int)(_front % _capacity);
        
        // 2. 从物理位置上取出元素
        item = _queue[physicalIndex];
        
        // 3. 更新逻辑指针（简单自增）
        _front++;
        
        return true;
    }
}

使用逻辑指针的优点是：

逻辑清晰：_rear - _front 直接等于队列中的元素数量，判断空 (_rear == _front) 和满 (_rear - _front == _capacity) 的逻辑非常非常清晰，甚至不需要额外的 count 变量。
附带信息：_rear 和 _front 的值本身就包含了历史信息，例如 _rear 代表了总入队数。
代码简洁：更新指针的操作只是 ++，比取模运算更简单。

但也有缺点：

整型溢出风险（实际存在）：由于 _front 和 _rear 会持续增长，如果队列的操作次数非常多，它们可能会超出 int 甚至 long 的最大值，导致溢出和错误。因此通常需要使用 long 类型，但这会占用更多内存。
性能开销：每次读写数组都需要进行一次取模运算 (%)，而取模运算通常比简单的加法和比较要慢。对于性能要求极高的场景，这可能会成为瓶颈。

应用

环形队列的核心优势在于其高效的空间利用率和稳定的操作性能（入队和出队操作的时间复杂度均为 O(1)），这使得它非常适合于处理需要缓冲、限流或异步处理的“生产者-消费者”模型。以下是一些典型的应用场景：

1. 操作系统与底层系统

IO 缓冲区 (I/O Buffer)：这是环形队列最经典的应用之一。例如，当用户程序请求写入数据到磁盘时，操作系统并不会立即写入，而是先把数据放入一个环形缓冲区。磁盘驱动作为消费者，会从这个缓冲区中不断取出数据并写入物理设备。同理，从键盘、鼠标、网卡接收到的数据也会先被放入一个缓冲区，等待上层应用程序来消费。为什么用环形队列？ 因为IO设备和CPU的速度严重不匹配。缓冲区可以平滑这种速度差异，防止高速的生产者（CPU）因等待低速的消费者（IO设备）而阻塞，也防止消费者在没有数据时空转。环形结构确保了缓冲区空间可以被持续循环利用。
进程间通信 (Inter-Process Communication, IPC)：在操作系统中，不同进程间需要交换数据时，可以使用一段共享内存（Shared Memory）并将其组织成环形队列。一个进程（生产者）向队列中写入数据，另一个进程（消费者）从中读取数据。这种方式被称为“管道（Pipe）”的底层实现之一。

2. 网络与并发编程

网络数据包收发：网卡驱动程序在接收数据包时，会将它们放入一个环形队列。网络协议栈的更高层次会作为消费者来处理这些数据包。发送数据时亦然，应用程序生成的数据包被放入发送队列，等待网卡驱动程序发送出去。为什么用环形队列？ 网络数据包的到达具有突发性，可能瞬间流量很大。环形队列可以作为“蓄水池”，缓冲这些突发流量，防止数据包因来不及处理而被丢弃（Packet Loss）。
线程池的任务队列 (Task Queue)：在并发编程中，线程池通常会有一个任务队列来存放待处理的任务。当一个新任务被提交时，它被放入任务队列（生产者）。线程池中的工作线程（消费者）会不断从队列中取出任务并执行。为什么用环形队列？ 它能够解耦任务的提交者和执行者。提交者可以快速地提交任务而无需等待任务立即执行。环形队列的高效性保证了任务分发的低延迟。很多高性能的线程池，如Java的Disruptor框架，其核心就是一种高度优化的环形队列。

3. 嵌入式系统与硬件

实时数据采集与处理：在嵌入式系统中，传感器（如温度、压力传感器）会以固定的频率产生数据（生产者）。主控制器（MCU）需要读取并处理这些数据（消费者）。使用环形队列可以在数据采集和数据处理两个不同频率的任务之间建立一个缓冲。为什么用环形队列？ 嵌入式系统的内存（RAM）资源非常宝贵。环形队列固定大小且空间利用率高的特点非常适合这种资源受限的环境。
音频/视频流处理：在播放音视频时，解码器（生产者）产生解码后的数据帧，播放器（消费者）消耗这些数据帧。这些数据帧被存放在一个环形队列中。为什么用环形队列？ 它可以有效地处理网络抖动或解码速度波动，保证播放的流畅性。如果队列中的数据低于某个“低水位”，播放器可以请求更多数据；如果高于某个“高水位”，可以通知解码器减慢速度，这实现了所谓的“流量控制”。

注意事项

虽然环形队列很高效，但在设计和使用时必须考虑以下几点，否则容易出错。

1. 队列大小（Capacity）的确定

过小：如果队列容量太小，无法有效缓冲生产和消费速率的差异。在生产高峰期，队列会迅速写满，导致生产者阻塞或数据丢失（取决于实现策略）。这会降低系统的吞吐量。
过大：如果队列容量过大，会不必要地占用过多内存。尤其是在有大量队列实例的系统中，内存开销会非常显著。此外，如果队列中积压了过多数据，可能会导致数据处理的延迟增高，数据的“新鲜度”下降。
建议：队列大小应根据生产者和消费者的平均速率差以及可容忍的突发流量峰值来综合评估。通常需要通过压力测试和性能监控来调整到一个合适的值。

2. 线程安全 (Thread Safety)

核心问题：标准的环形队列实现不是线程安全的。如果一个线程正在入队（修改rear指针和数组内容），同时另一个线程也在入队，或者一个线程在出队（修改front指针），就会导致数据竞争（Data Race），最终破坏队列的内部状态，导致数据错乱或程序崩溃。
解决方案：
- 加锁 (Locking)：最简单的方法是使用互斥锁（如C#中的 lock 关键字）来保护所有公共方法（Enqueue, Dequeue, IsEmpty, IsFull等）。这能保证同一时间只有一个线程能操作队列，但会牺牲一部分性能，因为锁会带来竞争和上下文切换的开销。
- 无锁队列 (Lock-Free Queue)：对于性能要求极高的场景，可以采用更复杂的无锁算法。这通常利用CPU提供的原子操作（如 Interlocked 类或 Compare-and-Swap指令）来实现。设计无锁队列非常复杂，容易出错，一般推荐使用经过严格测试的并发库，例如 .NET 中的 System.Collections.Concurrent.ConcurrentQueue<T>，其底层实现就类似于一个高效的并发队列。

3. 队满和队空的处理策略

队满时 (Queue is Full)：
- 阻塞等待：当生产者尝试入队但队列已满时，阻塞该线程，直到消费者取出元素腾出空间。这是最常见的策略。
- 丢弃数据：允许入队操作失败，并立即返回。调用者可以选择丢弃当前数据。根据业务需求，可以丢弃最旧的数据（覆盖式写入）或丢弃最新的数据。
- 抛出异常：向调用者抛出一个异常，表明队列已满。
队空时 (Queue is Empty)：
- 阻塞等待：当消费者尝试出队但队列为空时，阻塞该线程，直到生产者放入新元素。
- 返回特殊值：不阻塞，立即返回一个特殊值（如 null 或 false），告知调用者当前无数据可取。
- 抛出异常：抛出异常表明队列为空。

选择哪种策略完全取决于具体的业务需求。例如，任务队列通常采用阻塞策略，而日志系统在极端情况下可能会选择丢弃日志的策略。

4. 元素类型

值类型 (Value Types)：如果队列中存储的是值类型（如 int, struct），入队时会发生一次值拷贝。
引用类型 (Reference Types)：如果存储的是引用类型（如 class 对象），入队时只拷贝引用（地址）。这意味着队列内外的代码都指向同一个对象。如果在出队之前，外部代码修改了该对象的状态，那么消费者取出的将是被修改后的对象。这一点在使用时需要特别注意，确保对象的生命周期和状态管理是清晰的。

5. 两种经典实现的抉择

牺牲空间法：优点是无需额外变量，实现紧凑。缺点是浪费一个空间，对于元素体积很大或队列容量极小的情况，这个浪费可能值得关注。
计数器法：优点是空间利用率100%，逻辑直观。缺点是需要额外维护一个count变量，在并发环境下，这个count变量也需要被线程安全地更新。

码农兼一个普普通通小青年