【C# 数据结构】队列 FIFO

队列的概念

队列和FIFO是什么关系？队列是一种数据结构。
FIFO是队列需要遵循的基本原则：First-In, First-Out。或者说FIFO是队列的基本特性！
C#中有个类叫做Queue，就是实现了队列这种数据结构的类，它遵循FIFO这个原则。

FIFO (First-In, First-Out)

FIFO（First In First Out，先进先出）是一种数据管理原则，就像排队一样：

• 先进入队列的数据先被处理。
• 后进入队列的数据后被处理。

在 FIFO 队列中，第一个进入队列的元素将是第一个被移除的元素。换句话说，队列中的元素按照它们被加入的顺序排列，最早加入的元素最先被取出。

Queue<T> 的工作原理：

• 入队 (Enqueue)：新元素被添加到队列的尾部。
• 出队 (Dequeue)：最早加入队列的元素从队列的头部移除，并返回该元素。

示例：

假设我们使用一个容量为 3 的队列，依次加入元素 1、2、3，然后进行 Dequeue() 操作：

Queue<int> queue = new Queue<int>();

// 入队操作
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

// 出队操作，按照 FIFO 顺序返回
Console.WriteLine(queue.Dequeue()); // 输出 1
Console.WriteLine(queue.Dequeue()); // 输出 2
Console.WriteLine(queue.Dequeue()); // 输出 3

解释：

• Enqueue(1) 将 1 加入队列的尾部。
• Enqueue(2) 将 2 加入队列的尾部。
• Enqueue(3) 将 3 加入队列的尾部。
• Dequeue() 返回并移除队列的头部元素，即最早加入的 1，然后是 2 和 3，遵循 FIFO 的顺序。

小结：

通过Queue<T> 的使用我们可以很好的理解 FIFO ，其中元素按照加入的顺序进行排队，最早加入的元素最先被取出。这使得它特别适用于处理排队和任务调度等场景。

环形队列

1. FIFO？

环状队列也是队列的一种，当然也遵循FIFO这个原则！

2. 环形缓冲队列如何实现FIFO？

环形缓冲队列是一种用固定大小的数组实现FIFO的方式。它通过两个指针（头指针和尾指针）来管理数据的入队和出队。

关键概念：

• 固定大小的数组：预分配一块连续的内存空间。
• 头指针（head）：指向下一个数据写入的位置。
• 尾指针（tail）：指向下一个数据读取的位置。
• 循环利用：当指针到达数组末尾时，会回到数组开头，形成一个“环”。

3. 环形缓冲队列的工作过程

让我们通过一个具体的例子来说明。

假设：

• 环形缓冲队列的容量为 5（即数组大小为5）。
• 初始状态：队列为空，head 和 tail 都指向位置 0。

操作步骤：

1. 入队（Enqueue）：

   • 将数据写入 head 指向的位置。
   • 然后 head 向前移动一位。
   • 如果 head 到达数组末尾，它会回到数组开头（循环特性）。

2. 出队（Dequeue）：

   • 从 tail 指向的位置读取数据。
   • 然后 tail 向前移动一位。
   • 如果 tail 到达数组末尾，它会回到数组开头。

4. 具体例子

初始状态：

数组索引： [0]  [1]  [2]  [3]  [4]
值：      None None None None None
head = 0, tail = 0

操作1：入队数据 A

• 将 A 写入 head 指向的位置（索引 0）。
• head 移动到下一个位置（索引 1）。

数组索引： [0]  [1]  [2]  [3]  [4]
值：       A    None None None None
head = 1, tail = 0

操作2：入队数据 B

• 将 B 写入 head 指向的位置（索引 1）。
• head 移动到下一个位置（索引 2）。

数组索引： [0]  [1]  [2]  [3]  [4]
值：       A     B    None None None
head = 2, tail = 0

操作3：出队

• 从 tail 指向的位置（索引 0）读取数据 A。
• tail 移动到下一个位置（索引 1）。

数组索引： [0]  [1]  [2]  [3]  [4]
值：       A     B    None None None
head = 2, tail = 1

操作4：入队数据 C, D, E

• 依次将 C, D, E 写入 head 指向的位置。
• head 移动到下一个位置。

数组索引： [0]  [1]  [2]  [3]  [4]
值：       A     B     C     D     E
head = 0, tail = 1

操作5：出队

• 从 tail 指向的位置（索引 1）读取数据 B。
• tail 移动到下一个位置（索引 2）。

数组索引： [0]  [1]  [2]  [3]  [4]
值：       A     B     C     D     E
head = 0, tail = 2

操作6：入队数据 F

• 将 F 写入 head 指向的位置（索引 0）。
• head 移动到下一个位置（索引 1）。

数组索引： [0]  [1]  [2]  [3]  [4]
值：       F     B     C     D     E
head = 1, tail = 2

操作7：出队

• 从 tail 指向的位置（索引 2）读取数据 C。
• tail 移动到下一个位置（索引 3）。

数组索引： [0]  [1]  [2]  [3]  [4]
值：       F     B     C     D     E
head = 1, tail = 3

5. 环形缓冲队列的FIFO特性

• 数据顺序：先入队的数据（如 A, B）先出队，后入队的数据（如 C, D, E）后出队。
• 循环利用：当 head 或 tail 到达数组末尾时，会回到数组开头，继续使用之前释放的空间。
• 固定容量：队列的大小是固定的，当队列满时，可以选择覆盖旧数据或报错。

6. 环形缓冲队列的FIFO优势

• 高效：入队和出队操作的时间复杂度都是 O(1)。
• 内存紧凑：数据连续存储，缓存友好。
• 适合实时系统：适合处理固定大小的数据流。

7. 小结

• 环形缓冲队列是FIFO的一种实现，它通过固定大小的数组和循环指针来实现先进先出的特性。
• 数据按顺序入队和出队，先进入队列的数据先被处理。
• 循环利用使得内存使用更高效，适合处理固定大小的数据流。
  通过理解环状队列你是不是对队列又有了更深的理解呢？ 😊

C# 如何通过代码实现环状队列？

之前说到，C# 中有个现成的类实现了队列就是Queue这个类。但是并没有现成的环状队列。

要手动实现环形缓冲队列（Circular Buffer）在 C# 中，可以通过结合 Queue<T> 或者直接使用一个固定大小的数组来模拟环形队列的行为。下面是两种常见的实现方式。

1. 使用 Queue<T> 实现环形缓冲队列

虽然 Queue<T> 本身并不是环形队列，但我们可以通过管理队列的最大容量和覆盖旧数据来模拟环形缓冲队列的行为。当队列满时，新的数据会覆盖最旧的数据。

public class CircularQueue<T>
{
    private readonly Queue<T> queue;
    private readonly int capacity;

    public CircularQueue(int capacity)
    {
        this.capacity = capacity;
        this.queue = new Queue<T>(capacity);
    }

    // 添加元素，如果队列已满，则移除最旧的元素
    public void Enqueue(T item)
    {
        if (queue.Count == capacity)
        {
            queue.Dequeue(); // 移除最旧的元素
        }
        queue.Enqueue(item);
    }

    // 从队列中取出元素
    public T Dequeue()
    {
        if (queue.Count == 0)
        {
            throw new InvalidOperationException("Queue is empty.");
        }
        return queue.Dequeue();
    }

    // 查看队列中的第一个元素
    public T Peek()
    {
        if (queue.Count == 0)
        {
            throw new InvalidOperationException("Queue is empty.");
        }
        return queue.Peek();
    }

    // 判断队列是否为空
    public bool IsEmpty() => queue.Count == 0;

    // 队列中的元素个数
    public int Count => queue.Count;
}

使用示例：

CircularQueue<int> circularQueue = new CircularQueue<int>(3);

circularQueue.Enqueue(1);
circularQueue.Enqueue(2);
circularQueue.Enqueue(3);

Console.WriteLine(circularQueue.Dequeue()); // 输出 1
circularQueue.Enqueue(4); // 现在队列已满，1 会被覆盖

Console.WriteLine(circularQueue.Dequeue()); // 输出 2
Console.WriteLine(circularQueue.Dequeue()); // 输出 3
Console.WriteLine(circularQueue.Dequeue()); // 输出 4

说明：

• Queue<T> 用于存储数据，最大容量为 capacity。
• 当队列满时（元素数量等于 capacity），通过 Dequeue() 移除最旧的元素，再插入新的元素，模拟环形缓冲的行为。

这种方式依赖于 Queue<T> 来管理队列的基本操作，简单易懂，但不能完全利用环形缓冲队列的内存高效性，尤其是在每次扩展队列容量时仍会引起内存分配。

2. 使用固定大小数组实现环形缓冲队列

这种方法通过手动管理队列的头尾指针和数组来实现环形缓冲区，避免了 Queue<T> 的扩展和额外的内存分配。下面是一个更低层次的实现方式：

public class CircularBuffer<T>
{
    private readonly T[] buffer;
    private int head;
    private int tail;
    private int size;
    private readonly int capacity;

    public CircularBuffer(int capacity)
    {
        this.capacity = capacity;
        this.buffer = new T[capacity];
        this.head = 0;
        this.tail = 0;
        this.size = 0;
    }

    // 添加元素到队列
    public void Enqueue(T item)
    {
        if (size == capacity)
        {
            // 队列已满，覆盖最旧的数据
            head = (head + 1) % capacity; // 更新头指针
        }
        else
        {
            size++;
        }
        
        buffer[tail] = item;
        tail = (tail + 1) % capacity; // 更新尾指针
    }

    // 从队列中取出元素
    public T Dequeue()
    {
        if (size == 0)
        {
            throw new InvalidOperationException("Queue is empty.");
        }

        T value = buffer[head];
        head = (head + 1) % capacity; // 更新头指针
        size--;
        return value;
    }

    // 查看队列的第一个元素
    public T Peek()
    {
        if (size == 0)
        {
            throw new InvalidOperationException("Queue is empty.");
        }

        return buffer[head];
    }

    // 判断队列是否为空
    public bool IsEmpty() => size == 0;

    // 队列中的元素个数
    public int Count => size;
}

使用示例：

CircularBuffer<int> buffer = new CircularBuffer<int>(3);

buffer.Enqueue(1);
buffer.Enqueue(2);
buffer.Enqueue(3);

Console.WriteLine(buffer.Dequeue()); // 输出 1
buffer.Enqueue(4); // 1 被覆盖

Console.WriteLine(buffer.Dequeue()); // 输出 2
Console.WriteLine(buffer.Dequeue()); // 输出 3
Console.WriteLine(buffer.Dequeue()); // 输出 4

说明：

• 通过一个固定大小的数组 buffer 存储数据，队列大小为 capacity。
• head 和 tail 指针管理数据的入队和出队。head 指针指向队列的头部（最旧的元素），tail 指针指向队列的尾部（最新的元素）。
• 当队列满时，新元素会覆盖最旧的数据，head 指针会移动到下一个位置，从而实现环形缓冲队列的覆盖行为。

这种方式比 Queue<T> 更高效，避免了额外的内存分配，适合需要频繁进行入队和出队操作的场景。

小结

• 使用 Queue<T>：可以通过在队列满时删除最旧元素来模拟环形缓冲队列，适用于简单的场景。
• 使用固定大小数组：手动管理头尾指针和队列大小，更高效，避免内存分配，适用于性能要求较高的场景。

队列和环状队列的对比

1. 环形缓冲队列是FIFO的一种实现

• FIFO原则：数据按照到达顺序处理，先进入队列的数据先被取出。
• 环形缓冲队列：通过固定大小的数组和循环指针实现FIFO，满足先进先出的特性。

2. 环形缓冲队列的特点

• 固定大小：预分配固定容量的内存，空间利用率高。
• 循环利用：通过头尾指针循环移动，重复利用数组空间。
• 高效性能：插入和删除操作的时间复杂度都是O(1)。
• 内存紧凑：数据连续存储，缓存友好。

3. 环形缓冲队列 vs 其他FIFO实现

4. 环形缓冲队列的局限性

• 固定大小：需要预先确定容量，不适合数据量变化大的场景。
• 不支持随机访问：只能按顺序访问数据。
• 溢出处理：队列满时需要明确策略（覆盖旧数据或报错）。

5. 小结

• 环形缓冲队列是FIFO的一种高效实现，特别适合固定大小、高吞吐量的场景。
• 它通过循环利用预分配的内存，避免了动态内存分配的开销，同时保持了FIFO的特性。
• 如果需要动态扩容或更灵活的内存管理，可以选择其他FIFO实现（如链表或动态数组）。

线程安全问题

1 多线程访问队列的潜在问题
1.1 竞态条件（Race Condition）
问题描述：多个线程同时修改队列的状态（如 head 和 tail 指针），导致数据不一致。

示例：
线程A和线程B同时执行入队操作。
两者读取相同的 head 指针值，导致数据覆盖或丢失。

1.2 数据不一致
问题描述：一个线程正在修改队列，另一个线程同时读取队列，导致读取到不完整或错误的数据。

示例：

线程A正在入队，更新了 head 指针但还未写入数据。

线程B读取 head 指针，误认为新数据已写入。

1.3 死锁（Deadlock）
问题描述：多个线程互相等待对方释放锁，导致程序无法继续执行。

示例：

线程A持有锁1并等待锁2。

线程B持有锁2并等待锁1。

Queue 如果一个线程只负责写，一个线程只负责读会有问题吗？

如果一个线程 只负责写（Enqueue）而另一个线程 只负责读（Dequeue），在 不使用锁 或其他线程同步机制的情况下，Queue<T> 仍然 可能会遇到问题，即使你不打算在同一时间内进行读写操作。

问题原因：

• 队列的内部状态：Queue<T> 并没有内建的线程安全机制来保证即使在读写操作不重叠的情况下，两个线程对队列的访问是安全的。
  • 例如，读线程可能会在 写线程 操作队列时，导致内部数据不一致或访问冲突。即使一个线程只负责写，另一个线程只负责读，也可能会出现 竞态条件（race condition）或 内存可见性问题。

一些潜在的风险：

1. 队列大小（Count）的读取：如果 Queue<T> 正在被修改（例如，写线程在 Enqueue），另一个线程试图读取队列大小或进行 Dequeue 操作，可能会得到不一致的结果。因为写线程可能在修改队列时，读线程同时查看到一个不完全或不一致的队列状态。

2. 数据一致性：尽管读写操作看似是顺序执行的，实际上在多个线程访问共享数据时，现代 CPU 和优化可能导致线程看到过时或不一致的数据（内存可见性问题）。因此，即使操作本身是序列化的，底层的硬件优化仍可能引发问题。

如何解决？

1. 使用锁 (lock)

通过使用 lock 确保 写操作 和 读操作 不会同时进行，这样可以防止数据竞争和不一致性：

public class ThreadSafeQueue<T>
{
    private readonly Queue<T> queue = new Queue<T>();
    private readonly object lockObject = new object();

    public void Enqueue(T item)
    {
        lock (lockObject)
        {
            queue.Enqueue(item);
        }
    }

    public T Dequeue()
    {
        lock (lockObject)
        {
            if (queue.Count == 0)
                throw new InvalidOperationException("Queue is empty.");
            return queue.Dequeue();
        }
    }

    public int Count
    {
        get
        {
            lock (lockObject)
            {
                return queue.Count;
            }
        }
    }
}

在这个示例中，通过 lock 来确保写操作和读操作不会发生竞态条件。

2. 使用 ConcurrentQueue<T>

如果你不希望手动加锁，可以使用 ConcurrentQueue<T>，它是线程安全的，可以在多个线程中同时进行读写操作，保证数据的一致性和正确性：

using System.Collections.Concurrent;

var concurrentQueue = new ConcurrentQueue<int>();

// 写线程：入队
concurrentQueue.Enqueue(1);
concurrentQueue.Enqueue(2);

// 读线程：出队
if (concurrentQueue.TryDequeue(out int result))
{
    Console.WriteLine(result); // 安全地获取队列元素
}

ConcurrentQueue<T> 会自动管理线程同步，因此你不需要担心加锁的问题，它会确保多线程环境下的正确性。

总结：

• 即使一个线程只负责写，另一个线程只负责读，Queue<T> 仍然 不保证线程安全，会有潜在的竞态条件和数据不一致问题。
• 如果需要确保线程安全，可以使用 lock 来同步读写操作，或者使用 ConcurrentQueue<T> 来避免手动管理同步。推荐使用 ConcurrentQueue<T>，因为它是专为多线程设计并且已经实现了高效的线程安全。