c# 向.NET Queue 类添加Remove(int index) 方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/531191/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
c# Adding a Remove(int index) method to the .NET Queue class
提问by Alex
I would like to use the generic queue class as described in the .NET framework (3.5) but I will need a Remove(int index) method to remove items from the queue. Can I achieve this functionality with an extension method? Anyone care to point me in the right direction?
我想使用 .NET 框架 (3.5) 中描述的通用队列类，但我需要一个 Remove(int index) 方法来从队列中删除项目。我可以使用扩展方法实现此功能吗？有没有人愿意为我指出正确的方向？
采纳答案by casperOne
What you want is a List<T>where you always call RemoveAt(0)when you want to get the item from the Queue. Everything else is the same, really (calling Addwould add an item to the end of the Queue).
你需要的是一个List<T>在那里你总是调用RemoveAt(0)，当你想从获得该项目Queue。其他一切都是一样的，真的（调用Add会在 的末尾添加一个项目Queue）。
回答by David Anderson
Someone will probably develop a better solution, but from what I see you will need to return a new Queue object in your Remove method. You'll want to check if the index is out of bounds and I may have got the ordering of the items being added wrong, but here's a quick and dirty example that could be made into an extension quite easily.
有人可能会开发出更好的解决方案，但据我所知，您需要在 Remove 方法中返回一个新的 Queue 对象。您需要检查索引是否超出范围，并且我可能将添加的项目的顺序弄错了，但这里有一个快速而肮脏的示例，可以很容易地将其制作成扩展。
public class MyQueue<T> : Queue<T> {
public MyQueue()
: base() {
// Default constructor
}
public MyQueue(Int32 capacity)
: base(capacity) {
// Default constructor
}
/// <summary>
/// Removes the item at the specified index and returns a new Queue
/// </summary>
public MyQueue<T> RemoveAt(Int32 index) {
MyQueue<T> retVal = new MyQueue<T>(Count - 1);
for (Int32 i = 0; i < this.Count - 1; i++) {
if (i != index) {
retVal.Enqueue(this.ElementAt(i));
}
}
return retVal;
}
}
回答by Anton Gogolev
In fact, this defeats the whole purpose of Queue and the class you'll eventually come up with the will violate the FIFO semantics altogether.
事实上，这违背了 Queue 的全部目的，您最终会提出的类将完全违反 FIFO 语义。
回答by RvdK
David Anderson's solutionis probably the best but has some overhead. Are you using custom objects in the queue? if so, add a boolean like cancel
大卫安德森的解决方案可能是最好的，但有一些开销。您是否在队列中使用自定义对象？如果是这样，请添加一个布尔值，例如取消
Check with your workers that process the queue if that boolean is set and then skip it.
如果设置了该布尔值，请与处理队列的工作人员核对，然后跳过它。
回答by wwe
The queue class is so difficult to understand. Use a generic list instead.
队列类太难理解了。改用通用列表。
回答by rollercodester
Combining both casperOne's and David Anderson's suggestions to the next level. The following class inherits from List and hides the methods that would be detrimental to the FIFO concept while adding the three Queue methods (Equeue, Dequeu, Peek).
将 casperOne 和 David Anderson 的建议结合到一个新的水平。以下类继承自 List 并隐藏了在添加三个 Queue 方法（Equeue、Dequeu、Peek）时对 FIFO 概念有害的方法。
public class ListQueue<T> : List<T>
{
new public void Add(T item) { throw new NotSupportedException(); }
new public void AddRange(IEnumerable<T> collection) { throw new NotSupportedException(); }
new public void Insert(int index, T item) { throw new NotSupportedException(); }
new public void InsertRange(int index, IEnumerable<T> collection) { throw new NotSupportedException(); }
new public void Reverse() { throw new NotSupportedException(); }
new public void Reverse(int index, int count) { throw new NotSupportedException(); }
new public void Sort() { throw new NotSupportedException(); }
new public void Sort(Comparison<T> comparison) { throw new NotSupportedException(); }
new public void Sort(IComparer<T> comparer) { throw new NotSupportedException(); }
new public void Sort(int index, int count, IComparer<T> comparer) { throw new NotSupportedException(); }
public void Enqueue(T item)
{
base.Add(item);
}
public T Dequeue()
{
var t = base[0];
base.RemoveAt(0);
return t;
}
public T Peek()
{
return base[0];
}
}
Test code:
测试代码：
class Program
{
static void Main(string[] args)
{
ListQueue<string> queue = new ListQueue<string>();
Console.WriteLine("Item count in ListQueue: {0}", queue.Count);
Console.WriteLine();
for (int i = 1; i <= 10; i++)
{
var text = String.Format("Test{0}", i);
queue.Enqueue(text);
Console.WriteLine("Just enqueued: {0}", text);
}
Console.WriteLine();
Console.WriteLine("Item count in ListQueue: {0}", queue.Count);
Console.WriteLine();
var peekText = queue.Peek();
Console.WriteLine("Just peeked at: {0}", peekText);
Console.WriteLine();
var textToRemove = "Test5";
queue.Remove(textToRemove);
Console.WriteLine("Just removed: {0}", textToRemove);
Console.WriteLine();
var queueCount = queue.Count;
for (int i = 0; i < queueCount; i++)
{
var text = queue.Dequeue();
Console.WriteLine("Just dequeued: {0}", text);
}
Console.WriteLine();
Console.WriteLine("Item count in ListQueue: {0}", queue.Count);
Console.WriteLine();
Console.WriteLine("Now try to ADD an item...should cause an exception.");
queue.Add("shouldFail");
}
}
回答by sfuqua
If the Queue is being used to preserve the order of the items in the collection, and if you will not have duplicate items, then a SortedSetmight be what you are looking for. The SortedSetacts much like a List<T>, but stays ordered. Great for things like drop down selections.
如果 Queue 用于保留集合中项目的顺序，并且您不会有重复的项目，那么SortedSet可能就是您要查找的内容。该SortedSet行为很像List<T>，但停留订购。非常适合下拉选择之类的东西。
回答by Lukazoid
I do not believe we should be using List<T>to emulate a queue, for a queue, the enqueue and dequeue operations should be very highly performant, which they would not be when using a List<T>. For the RemoveAtmethod however, it is acceptable to be non-performant, as it is not the primary purpose of a Queue<T>.
我不认为我们应该使用List<T>来模拟队列，对于队列，入队和出队操作应该具有非常高的性能，而在使用List<T>. RemoveAt但是，对于该方法，性能不佳是可以接受的，因为它不是Queue<T>.
My approach at implementing RemoveAtis O(n) but the queue still maintains a largely O(1) enqueue (sometimes the internal array needs reallocating which makes the operations O(n)) and always O(1) dequeue.
我的实现方法RemoveAt是 O(n)，但队列仍然保持大量 O(1) 入队（有时内部数组需要重新分配，这使得操作 O(n)）并且总是 O(1) 出队。
Here is my implementation of a RemoveAt(int)extension method for a Queue<T>:
这是我对 a 的RemoveAt(int)扩展方法的实现Queue<T>：
public static void RemoveAt<T>(this Queue<T> queue, int index)
{
Contract.Requires(queue != null);
Contract.Requires(index >= 0);
Contract.Requires(index < queue.Count);
var i = 0;
// Move all the items before the one to remove to the back
for (; i < index; ++i)
{
queue.MoveHeadToTail();
}
// Remove the item at the index
queue.Dequeue();
// Move all subsequent items to the tail end of the queue.
var queueCount = queue.Count;
for (; i < queueCount; ++i)
{
queue.MoveHeadToTail();
}
}
Where MoveHeadToTailis defined as follows:
其中MoveHeadToTail定义如下：
private static void MoveHeadToTail<T>(this Queue<T> queue)
{
Contract.Requires(queue != null);
var dequed = queue.Dequeue();
queue.Enqueue(dequed);
}
This implementation also modifies the actual Queue<T>rather than returning a new Queue<T>(which I think is more in-keeping with other RemoveAtimplementations).
这个实现还修改了实际的Queue<T>而不是返回一个新的Queue<T>（我认为这更符合其他RemoveAt实现）。
回答by Adriano Repetti
It's a pretty late answer but I write it for future readers
这是一个很晚的答案，但我是为未来的读者写的
List<T>is exactly what you need but it has a big disadvantage when compared to Queue<T>: it's implemented with an array then Dequeue()is pretty expansive (in terms of time) because all items must be shifted one step back with Array.Copy. Even Queue<T>uses an array but together with two indices (for head and tail).
List<T>正是你所需要的，但相比它有一个很大的缺点Queue<T>：它有一个数组实现，那么Dequeue()是相当广阔的（在时间上），因为所有项目都必须移一步一个回头Array.Copy。甚至Queue<T>使用一个数组，但与两个索引（用于头和尾）一起使用。
In your case you also need Remove/RemoveAtand its performance won't be good (for the same reason: if you're not removing from list tail then another array must be allocated and items copied).
在您的情况下，您还需要Remove/RemoveAt并且它的性能不会很好（出于同样的原因：如果您没有从列表尾部删除，则必须分配另一个数组并复制项目）。
A better data structure to have quick Dequeue/Removetime is a linked list (you'll sacrifice - a little bit - performance for Enqueuebut assuming your queue has an equal number of Enqueue/Dequeueoperations you'll have a great gain in performance, especially when its size will grow).
一个更好的数据结构，以便快速Dequeue/Remove时间是一个链表（你会牺牲-一点点-性能Enqueue，但假设你的队列中有相同数目的Enqueue/Dequeue操作你必须在性能有很大的收益，尤其是当它的大小会长大）。
Let's see a simple skeleton for its implementation (I'll skip implementation for IEnumerable<T>, IList<T>and other helper methods).
让我们来看看一个简单的框架及其实施（我将跳过实施IEnumerable<T>，IList<T>及其他辅助方法）。
class LinkedQueue<T>
{
public int Count
{
get { return _items.Count; }
}
public void Enqueue(T item)
{
_items.AddLast(item);
}
public T Dequeue()
{
if (_items.First == null)
throw new InvalidOperationException("...");
var item = _items.First.Value;
_items.RemoveFirst();
return item;
}
public void Remove(T item)
{
_items.Remove(item);
}
public void RemoveAt(int index)
{
Remove(_items.Skip(index).First());
}
private LinkedList<T> _items = new LinkedList<T>();
}
For a quick comparison:
快速比较：
Queue List LinkedList Enqueue O(1)/O(n)* O(1)/O(n)* O(1) Dequeue O(1) O(n) O(1) Remove n/a O(n) O(n)
*O(1) is typicalcase but sometimesit'll be O(n) (when internal array need to be resized).
*O(1) 是典型情况，但有时它会是 O(n)（当需要调整内部数组的大小时）。
Of course you'll pay something for what you gain: memory usage is bigger (especially for small Toverhead will be great). Right implementation (List<T>vs LinkedList<T>) must be chosen carefully according to your usage scenario, you may also convert that code to use a single linked list to reduce 50% of memory overhead.
当然，您会为所获得的付出一些代价：内存使用量更大（特别是对于小T开销会很棒）。必须根据您的使用场景仔细选择正确的实现（List<T>vs LinkedList<T>），您也可以将该代码转换为使用单个链表以减少 50% 的内存开销。
回答by Alex
Here's how you remove a specificitem from the queue with one line of Linq (it's recreating the queue, BUT for the lack of a better method...)
这是使用一行 Linq 从队列中删除特定项目的方法（它正在重新创建队列，但由于缺乏更好的方法......）
//replace "<string>" with your actual underlying type
myqueue = new Queue<string>(myqueue.Where(s => s != itemToBeRemoved));
I know it's not removing by index, but still, someone might find this useful (this question ranks in Google for "remove specific item from a c# queue" so I decided to add this answer, sorry)
我知道它不是按索引删除，但仍然有人可能会发现这很有用（这个问题在谷歌中排名为“从 ac# 队列中删除特定项目”，所以我决定添加这个答案，抱歉）
