双端队列的增删操作实现（C#语言从零开始掌握Deque）

什么是双端队列？

双端队列（Deque）是一种特殊的线性数据结构，它允许在队列的前端（头部）和后端（尾部）都进行插入和删除操作。这与普通队列（只允许尾部入队、头部出队）或栈（只在一端操作）不同。

常见的操作包括：

• AddFront(item)：在队列前端添加元素
• AddRear(item)：在队列后端添加元素
• RemoveFront()：从队列前端移除元素
• RemoveRear()：从队列后端移除元素

为什么使用 C# 实现双端队列？

虽然 .NET 框架提供了 LinkedList<T> 或 List<T> 等集合类型，但它们并不是专为双端操作优化的。通过自己实现 Deque，你不仅能深入理解数据结构原理，还能根据需求定制性能更优的解决方案。这也是学习 C#数据结构 的重要一步。

使用数组实现双端队列

我们可以使用循环数组来高效地实现双端队列。下面是一个完整的 C# 示例：

using System;public class Deque<T>{    private T[] _items;    private int _front;    private int _rear;    private int _size;    private const int DefaultCapacity = 4;    public Deque()    {        _items = new T[DefaultCapacity];        _front = 0;        _rear = -1;        _size = 0;    }    public int Count => _size;    public bool IsEmpty => _size == 0;    // 在前端添加元素    public void AddFront(T item)    {        if (_size == _items.Length)            Resize();        _front = (_front - 1 + _items.Length) % _items.Length;        _items[_front] = item;        _size++;    }    // 在后端添加元素    public void AddRear(T item)    {        if (_size == _items.Length)            Resize();        _rear = (_rear + 1) % _items.Length;        _items[_rear] = item;        _size++;    }    // 从前端移除元素    public T RemoveFront()    {        if (IsEmpty)            throw new InvalidOperationException("Deque is empty.");        T item = _items[_front];        _items[_front] = default(T);        _front = (_front + 1) % _items.Length;        _size--;        return item;    }    // 从后端移除元素    public T RemoveRear()    {        if (IsEmpty)            throw new InvalidOperationException("Deque is empty.");        T item = _items[_rear];        _items[_rear] = default(T);        _rear = (_rear - 1 + _items.Length) % _items.Length;        _size--;        return item;    }    // 动态扩容    private void Resize()    {        T[] newItems = new T[_items.Length * 2];        for (int i = 0; i < _size; i++)        {            newItems[i] = _items[(_front + i) % _items.Length];        }        _items = newItems;        _front = 0;        _rear = _size - 1;    }}

代码详解

上面的代码实现了完整的 C#双端队列 功能：

• _front 和 _rear 分别记录队列的头尾位置。
• 使用模运算 % 实现循环数组，避免频繁移动元素。
• Resize() 方法在容量不足时自动扩容，保证性能。
• 所有操作的时间复杂度均为 O(1)（均摊）。

如何使用这个双端队列？

下面是一个简单的使用示例：

class Program{    static void Main()    {        var deque = new Deque<string>();        deque.AddRear("A");        deque.AddRear("B");        deque.AddFront("X");        Console.WriteLine(deque.RemoveFront()); // 输出: X        Console.WriteLine(deque.RemoveRear());  // 输出: B        Console.WriteLine(deque.Count);         // 输出: 1    }}

总结

通过本教程，你已经学会了如何用 C# 语言实现一个功能完整的双端队列。这种数据结构在算法竞赛、缓存系统、滑动窗口等问题中非常有用。掌握 Deque实现 不仅能提升你的编程能力，还能帮助你更好地理解底层数据结构的设计思想。

记住，学习 双端队列操作 是进阶 C# 编程的重要一步。多动手实践，你会越来越熟练！