C#双端队列详解（从零开始实现高效Deque数据结构）

什么是双端队列？

双端队列（Deque）是一种线性数据结构，支持以下四种基本操作：

• AddFront(item)：在队列前端添加元素
• AddBack(item)：在队列后端添加元素
• RemoveFront()：移除并返回队列前端元素
• RemoveBack()：移除并返回队列后端元素

这种灵活性使得Deque在滑动窗口、回文检测、任务调度等场景中非常有用。虽然.NET Framework没有内置的Deque类，但我们可以通过C#轻松实现一个。

C#双端队列实现思路

为了高效地在两端操作，我们使用双向链表（Doubly Linked List）作为底层结构。每个节点包含数据、指向前一个节点的引用和指向后一个节点的引用。

1. 定义节点类

private class Node{    public T Data { get; set; }    public Node? Previous { get; set; }    public Node? Next { get; set; }    public Node(T data)    {        Data = data;    }}

2. 实现双端队列类

接下来，我们创建一个泛型类 Deque<T>，包含头尾指针和计数器：

public class Deque<T>{    private Node? head;    private Node? tail;    private int count;    public int Count => count;    public bool IsEmpty => count == 0;    // 在前端添加元素    public void AddFront(T item)    {        var newNode = new Node(item);        if (IsEmpty)        {            head = tail = newNode;        }        else        {            newNode.Next = head;            head!.Previous = newNode;            head = newNode;        }        count++;    }    // 在后端添加元素    public void AddBack(T item)    {        var newNode = new Node(item);        if (IsEmpty)        {            head = tail = newNode;        }        else        {            newNode.Previous = tail;            tail!.Next = newNode;            tail = newNode;        }        count++;    }    // 从前端移除元素    public T RemoveFront()    {        if (IsEmpty)            throw new InvalidOperationException("Deque is empty.");        T result = head!.Data;        if (head == tail)        {            head = tail = null;        }        else        {            head = head.Next;            head!.Previous = null;        }        count--;        return result;    }    // 从后端移除元素    public T RemoveBack()    {        if (IsEmpty)            throw new InvalidOperationException("Deque is empty.");        T result = tail!.Data;        if (head == tail)        {            head = tail = null;        }        else        {            tail = tail.Previous;            tail!.Next = null;        }        count--;        return result;    }}

如何使用这个双端队列？

下面是一个简单的使用示例，展示了C#双端队列的基本操作：

class Program{    static void Main()    {        var deque = new Deque<int>();        deque.AddBack(1);        deque.AddBack(2);        deque.AddFront(0); // 现在 deque 是 [0, 1, 2]        Console.WriteLine(deque.RemoveFront()); // 输出: 0        Console.WriteLine(deque.RemoveBack());  // 输出: 2        Console.WriteLine($"剩余元素数量: {deque.Count}"); // 输出: 1    }}

为什么需要自己实现Deque？

虽然.NET提供了List<T>、LinkedList<T>等集合类型，但它们并不直接支持高效的双端操作。例如，List<T>在头部插入/删除的时间复杂度是O(n)，而我们的Deque实现所有操作都是O(1)。因此，在需要频繁在两端操作的场景下，自定义的C#双端队列能显著提升性能。

总结

通过本教程，你已经学会了如何用C#从零实现一个功能完整的双端队列（Deque）。这种C#数据结构不仅灵活高效，还能帮助你解决许多实际编程问题。无论你是初学者还是有经验的开发者，掌握双端队列入门知识都将为你的编程技能增添重要一环。

希望这篇关于C#双端队列的教程对你有所帮助！你可以将代码复制到你的项目中，根据需要扩展功能（如Peek操作、清空方法等）。