C# 中的 Deque 类

• 下载源代码文件 - 11.9 Kb

引言

这是一个常见的故事：您正在做一个项目，需要一个非常简单的类，一个您认为已经是您正在使用的库的一部分的类。您搜索了库，发现该类不存在。然后您面临一个选择，您可以“自己动手”创建一个类，或者使用第三方实现（如果您能找到的话）。在大多数情况下，我们选择前者也就不足为奇了。创建自己的基础类，并且知道它将来会派上用场，这可能令人满意。

这里讨论的类是 Deque（发音为“deck”）类。Deque 是一种数据结构，允许您在队列的两端添加和删除元素。我当时正在研究我的状态机工具包，需要一个 Deque 集合类。我检查了 System.Collections 命名空间，看看它是否有一个。不幸的是，它没有。我在 CodeProject 上对 Deque 类进行了粗略搜索，发现了这篇关于“Dequeue”类的文章。我没有看代码，但无论如何都决定它不是我想要的，而且不可否认，我已经下定决心要编写自己的 Deque 类。

Deque 数据结构

队列数据结构表示向队列末尾（或背面）添加元素并从队列开头（或正面）移除元素的功能。想象一下电影院里排队买票的人群。第一个排队的人是第一个买到票的人。这种方法称为“先进先出”（FIFO）。

有时您需要能够向队列的两端添加和删除元素。Deque 数据结构非常适合这一点。它是一个“双端队列”，您可以在队列的开头和结尾添加和删除元素。

Deque 类

首先，我希望我的 Deque 类看起来像 System.Collections 命名空间中的一个类。如果我在搜索 System.Collections 命名空间时找到了 Deque 类，它就会是这样的。我仔细研究了 Queue 类，并以它为模型来构建我的类。为此，Deque 类实现了相同的接口：ICollection、IEnumerable 和 ICloneable。

除了这些接口中的方法和属性之外，Deque 类还具有 Queue 类中的一些方法。

• Clear - 清除集合中的所有元素。
• Contains - 确定一个对象是否存在于集合中。
• ToArray - 将集合中的所有元素复制到一个数组中。
• Synchronized - 为集合提供一个同步的包装器。

Queue 类还提供了一个 Peek 方法。此方法允许您查看 Queue 开头的元素而不将其移除。以此为例，Deque 类提供了 PeekFront 和 PeekBack 方法，分别用于查看 Deque 开头和结尾的元素。

PushFront 和 PushBack 方法允许您分别向 Deque 的开头和结尾添加元素，而它们的对应方法 PopFront 和 PopBack 则允许您分别从 Deque 的开头和结尾移除元素。

实现

Deque 类使用双向链表来实现其元素集合。链表中的链接由私有的 Node 类表示。由于元素可以添加到 Deque 的开头和结尾，因此需要有开头和结尾节点来跟踪 Deque 的开头和结尾。

有一个自定义的私有类 DequeEnumerator，用于实现 GetEnumerator 方法返回的 IEnumerator 接口，以便从前到后遍历 Deque。我以前编写过自定义枚举器，这并不难，只是您必须确保您的实现符合 IEnumerator 规范。

同步

由于我需要 Deque 是线程安全的，因此我实现了一个静态的 Synchronized 方法（以 System.Collections 命名空间中的集合为模型）。它返回一个围绕 Deque 对象的线程安全包装器。为了实现这一点，我首先将 Deque 类中的每个方法和属性设为 virtual。然后，我从 Deque 类派生了一个名为 SynchronizedDeque 的私有类，其中重写了 Deque 的每个方法和属性。

当创建一个 SynchronizedDeque 时，它会接收一个 Deque 对象。它通过在其重写的方法和属性中锁定对 Deque 对象的访问，并将调用委托给 Deque 对象来实现线程安全。Synchronized 方法创建一个 SynchronizedDeque 对象，并返回一个 Deque 引用给它，因此它看起来和行为都像一个常规的 Deque 对象。

Deque<T> 类

我决定是时候创建一个支持泛型的 Deque 类的新版本了。将原始 Deque 类转换为泛型版本相当直接。我复制了原始代码，并将 Deque 中所有对元素的引用从 object 类型更改为 T 类型。我让 Deque<T> 类实现 IEnumerator<T> 接口。有趣的是 IEnumerator<T> 实现 IDisposable，所以我不得不修改我的私有枚举器类以提供 IDisposable 功能。这一切都相当容易做到。

如果您需要，原始 Deque 仍然存在，未更改。

源代码

Deque 类位于 Sanford.Collections 命名空间中（以前是 LSCollections 命名空间；我认为它需要重命名）。而 Deque<T> 类位于 Sanford.Collections.Generics 命名空间中。压缩的源代码包含几个文件：原始的 Deque.cs 文件、实现新 Deque<T> 类的文件，以及 Tester.cs 和 GenericTester.cs 文件。Tester.cs 文件表示一个控制台应用程序类，它测试 Deque 和 Deque<T> 类的功能。

结论

好吧，这篇文章换了个节奏。我上一次在 CodeProject 的贡献是一系列文章，展示了我花了几个月时间开发和研究的工具包。相比之下，Deque 类以及这篇文章在很大程度上都很容易编写。但有时最简单的东西可能最有用。至少我希望我在这里取得了成功。感谢您的时间，一如既往，欢迎评论和建议。

历史

• 2005 年 9 月 25 日 - 第一个版本完成。
• 2006 年 10 月 15 日 - 修改了文章，并添加了 Deque<T> 类。