C# - Java的双端队列

Question

在Java中，有一个名为 Deque的类，我想在.NET (C#)中找到类似的东西。

我需要这个的原因是因为我需要查看集合中的最后一项，然后从集合中出队第一项。

谢谢， AJ Ravindiran。

- TheAJ

Answer 1

请看 .NET 的 System.Collections.Generic.LinkedList 集合，它可以用作双端队列。 这是一个双向链接列表。

插入/删除

• AddFirst：添加到开头
• AddLast：添加到末尾
• RemoveFirst：从开头移除。不返回值。
• RemoveLast：从末尾移除。不返回值。

Peeking：

• First/Last 属性。

  这些属性返回一个 LinkedListNode<T>，而不是实际的值。要获取值，您需要在末尾添加 .Value。

- Grzegorz Smulko

Answer 2

PowerCollections拥有一个Deque类（并且具有可靠的血统）。

- itowlson

---

这个有什么优势，高于LinkedList<T>？ - Dave Lawrence

Answer 3

列表应该为您做到这一点：

var l = new List<int>();
var last = l[l.Count - 1];
l.RemoveAt(0);

- Mark

---

作为一种暂时的解决方法，这样做可以。问题是RemoveAt(0)需要O(n)的时间。 - bohdan_trotsenko

Answer 4

这是我实现的一个Deque<T>（使用环形缓冲区）和一个并发无锁ConcurrentDeque<T>：

• Github：https://github.com/dcastro/DequeNET
• NuGet：https://www.nuget.org/packages/DequeNET/

这两个类都支持在deque的两端进行Push、Pop和Peek操作，所有操作时间复杂度均为O(1)。

- dcastro

Answer 5

类似这样的问题在另一个SO问题中已经被提及过。

流行的答案似乎是使用链表，而Eric Lippert则建议使用他自己的Deque实现。

所以我想短暂的回答是，.NET中没有这样严格的数据结构内置。

希望对你有所帮助。

- mrvisser

---

需要注意的是，Eric的Deque实现是一个不可变集合。如果不可变性对您不重要，则可能会有更高效的可变deque实现。 - Stephen Drew