.NET 双端队列

• 下载源代码和示例 - 28.4 KB

引言

最近，我正在做一个项目，需要使用一个缓冲队列通过网络发送数据（是的，这就是我的 Winsock 控件）。我需要获取队列中的下一项，修改它，然后把它放回队列的顶部。

正如大家所知，你不能用 `Queue` 对象做到这一点，尽管你可以用 `Stack` 来做 - 但那样，你就不能保持 `Queue` 的先进先出（FIFO）方法了。所以，我只好使用 `Collection`，并手动实现。

在优化我的控件时，我决定将 `Stack` 和 `Queue` 结合起来，以便于操作（当然，回看代码时也易于阅读）。我似乎找不到任何关于如何做这件事的信息（快速谷歌搜索）。

我决定将这两个名字结合起来，称之为 "Quack"，但就在那时，我的搜索起了作用，我发现它原来叫做 Deque（发音为 "deck"）。我决定查找任何 .NET 的实现，但看到的都是 C++ 的引用。我当时已经做好了自己的实现，所以决定在这里分享。

这是一个相当简单的 Deque 实现，而且自己做起来也很简单 - 然而，本文的重点是让你找到可以用来使用的信息 - 无论你是否想自己实现。

我实现了 `ICollection`、`IEnumerable` 和 `ICloneable` 接口 - 就像 `Stack` 和 `Queue` 对象一样。所有内容都存储在一个私有的、内部的、泛型的 `LinkedList(Of Object)` 中。

** 更新 ** 我已将此更新为更完整的 Deque 版本，并使用了 `LinkedList` 以获得更好的性能。现在可用的操作是从 Wikipedia 上的 Deque 条目 这里[^] 中获取的，包括：`PushBack`、`PushFront`、`PopBack`、`PopFront`、`PeekBack` 和 `PeekFront`。

我们开始介绍实现和使用方法，好吗？

栈 (Stacks)

栈使用后进先出 (LIFO) 的过程。在栈中，你使用 `Push` 方法将一个项目放入栈中，并使用 `Pop` 方法将一个项目从栈中取出。

让我们看一个例子。

假设我按顺序将数字 1、2、3 和 4 放入一个栈中 - 它可以这样可视化

4
3
2
1

然后我使用 `Pop` 取出一个。这将导致 4 被取出，栈看起来像这样

3
2
1

队列

队列使用先进先出 (FIFO) 的过程。在这里，你分别使用 `Enqueue` 和 `Dequeue` 方法将一个项目放入队列，并从队列中取出一个项目。

让我们用完全相同的过程，按相同的顺序向队列添加 1、2、3 和 4。下面是队列的外观

1
2
3
4

然后，在使用 `Dequeue` 取出一个项目后，我取回了 1，留下一个看起来像这样的队列

2
3
4

构建类

由于我使用 `LinkedList` 来存储项目，我们可以将“前端”和“后端”分别称为“第一个”和“最后一个”。`Push`、`Pop` 和 `Peek` 这三个方法都有两个实现，一个用于前端，一个用于后端。

Public Sub PushBack(ByVal obj As Object)
    llList.AddLast(obj)
End Sub

Public Function PopBack(Of dataType)() As dataType
    Dim objRet As dataType = PeekBack(Of dataType)()
    llList.RemoveLast()
    Return objRet
End Function

Public Function PeekBack(Of dataType)() As dataType
    If llList.Count = 0 Then Return Nothing
    Return DirectCast(llList.Last().Value, dataType)
End Function

请注意，向 `LinkedList` 的末尾添加和删除是多么容易。从前端添加和删除也同样容易，可以使用 `LinkedList` 的 `AddFirst`、`RemoveFirst` 和 `First` 方法。

创建这个类的最大困难是让它正确地实现这三个接口：`ICollection`、`IEnumerable` 和 `ICloneable`。不过幸运的是，`List` 能够提供这些功能。更多细节请参见源代码。

Using the Code

实际上，使用这个类和使用 `Stack` 和 `Queue` 类一样简单；如果你知道如何使用它们，那么你就可以使用这个类。

但对于那些不知道如何使用它们的人，这里有一个如何使用这个类的快速示例。任何一行执行后，`Deque` 的状态都显示在注释中，列表的顶部在左侧。

Dim q As New Deque
Dim objRet As Object
q.PushBack(1) ' 1
q.PushBack(2) ' 1, 2
q.PushBack(3) ' 1, 2, 3
q.PushBack(4) ' 1, 2, 3, 4
objRet = q.PopFront() ' 2, 3, 4
q.PushFront(-1) ' -1, 2, 3, 4
q.PushFront(9) ' 9, -1, 2, 3, 4
objRet = q.PopFront() ' -1, 2, 3, 4
objRet = q.PopBack() ' -1, 2, 3
objRet = q.PopFront() ' 2, 3
objRet = q.PopBack() ' 2
objRet = q.PopFront() '

关注点

示例项目通过 "动画" 的方式演示了各种示例。这非常简单地通过使用 `Sleep` 方法来暂停显示，而且构建起来也很有趣。它直观地展示了栈/队列/双端队列是如何工作的。

摘要

我只是在做另一个项目时做的这个，希望其他人能从我的代码探索中受益。

祝你在自己的编码项目中玩得开心！