c＃将Remove（int index）方法添加到.NET Queue类
我想使用.NET框架（3.5）中描述的通用队列类，但我需要一个Remove（int index）方法来从队列中删除项目。 我可以使用扩展方法实现此function吗？ 有人想指出我正确的方向吗？
你想要的是List ，当你想从Queue获取项目时，你总是调用RemoveAt(0) 。 其他一切都是一样的，真的（调用Add会在Queue的末尾添加一个项目）。
将casperOne和David Anderson的建议结合到一个新的水平。 以下类inheritance自List并隐藏了在添加三个Queue方法（Equeue，Dequeu，Peek）时对FIFO概念有害的方法。
public class ListQueue : List { new public void Add(T item) { throw new NotSupportedException(); } new public void AddRange(IEnumerable collection) { throw new NotSupportedException(); } new public void Insert(int index, T item) { throw new NotSupportedException(); } new public void InsertRange(int index, IEnumerable 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 comparison) { throw new NotSupportedException(); } new public void Sort(IComparer comparer) { throw new NotSupportedException(); } new public void Sort(int index, int count, IComparer 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]; } }
测试代码：
class Program { static void Main(string[] args) { ListQueue queue = new ListQueue (); 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"); } }
以下是使用一行Linq从队列中删除特定项目的方法（它正在重新创建队列，但缺少更好的方法……）
//replace "" with your actual underlying type myqueue = new Queue (myqueue.Where(s => s != itemToBeRemoved));
我知道它不是通过索引删除，但仍然有人可能会觉得这很有用（这个问题在Google中排名“从ac＃queue中删除特定项目”所以我决定添加这个答案，抱歉）
有人可能会开发出更好的解决方案，但从我看到你需要在Remove方法中返回一个新的Queue对象。 你需要检查索引是否超出范围，我可能已经错误地添加了项目的顺序，但是这是一个快速而肮脏的例子，可以很容易地成为扩展。
public class MyQueue : Queue { public MyQueue() : base() { // Default constructor } public MyQueue(Int32 capacity) : base(capacity) { // Default constructor } /// /// Removes the item at the specified index and returns a new Queue /// public MyQueue RemoveAt(Int32 index) { MyQueue retVal = new MyQueue (Count - 1); for (Int32 i = 0; i < this.Count - 1; i++) { if (i != index) { retVal.Enqueue(this.ElementAt(i)); } } return retVal; } }
这是一个非常晚的答案，但我写给未来的读者
List正是你所需要的，但与Queue相比它有一个很大的缺点：它是用数组实现的，然后Dequeue()非常广泛（就时间而言）因为所有项目都必须向前移一步使用Array.Copy 。 甚至Queue使用一个数组，但同时使用两个索引（头部和尾部）。
在您的情况下，您还需要Remove / RemoveAt并且其性能不会很好（出于同样的原因：如果您没有从列表尾部删除，则必须分配另一个数组并复制项目）。
一个更快的Dequeue / Remove时间的更好的数据结构是一个链表（你会牺牲 – 一点点 – Enqueue性能，但假设你的队列具有相同数量的Enqueue / Dequeue操作，你将获得很大的性能提升，特别是当它的尺寸会增长时）。
让我们看一下它的实现的简单框架（我将跳过IEnumerable ， IList和其他辅助方法的实现）。
class LinkedQueue { 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 _items = new LinkedList (); }
为了快速比较：
队列列表LinkedList
入队O（1）/ O（n）* O（1）/ O（n）* O（1）
出列O（1）O（n）O（1）
删除不适用O（n）O（n）
* O（1）是典型情况，但有时它将是O（n）（当内部数组需要resize时）。
当然，你会为你获得的东西支付一些东西：内存使用量更大（特别是对于小T开销会很好）。 必须根据您的使用场景仔细选择正确的实现（ List vs LinkedList ），您也可以将该代码转换为使用单个链表来减少50％的内存开销。
实际上，这会破坏Queue的整个目的，而你最终会提出的类将完全违反FIFO语义。
如果正在使用队列来保留集合中项目的顺序，并且如果您没有重复项目，那么SortedSet可能就是您要查找的内容。 SortedSet行为很像List ，但保持有序。 非常适合下拉选项等。
虽然没有内置方式，但是你不应该使用List结构或其他结构，IFF RemoveAt不是经常运行的。
如果您通常入队并出列但只是偶尔删除，那么您应该能够在删除时负担队列重建。
public static void Remove(this Queue queue, T itemToRemove) where T : class { var list = queue.ToList(); //Needs to be copy, so we can clear the queue queue.Clear(); foreach (var item in list) { if (item == itemToRemove) continue; queue.Enqueue(item); } } public static void RemoveAt (this Queue queue, int itemIndex) where T : class { var list = queue.ToList(); //Needs to be copy, so we can clear the queue queue.Clear(); for (int i = 0; i < list.Count; i++) { if (i == itemIndex) continue; queue.Enqueue(list[i]); } }
大卫安德森的解决方案可能是最好的，但有一些开销。 您是否在队列中使用自定义对象？ 如果是这样，添加一个类似取消的布尔值
如果设置了布尔值，请检查处理队列的工作人员，然后跳过它。
我不相信我们应该使用List来模拟队列，对于队列，enqueue和dequeue操作应该是非常高性能的，当使用List时它们不会是这样。 但是对于RemoveAt方法，可以接受非性能，因为它不是Queue的主要目的。
我实现RemoveAt是O（n），但队列仍然保持很大的O（1）入队（有时内部数组需要重新分配，这使得操作O（n））并且总是O（1）出列。
这是我为Queue实现的RemoveAt(int)扩展方法：
public static void RemoveAt(this Queue 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(); } }
MoveHeadToTail的定义如下：
private static void MoveHeadToTail(this Queue queue) { Contract.Requires(queue != null); var dequed = queue.Dequeue(); queue.Enqueue(dequed); }
此实现还修改了实际的Queue而不是返回一个新的Queue （我认为它与其他RemoveAt实现更加一致）。
请注意，对于列表，如果您实际上没有删除该项目，只是将其“标记”为“已删除”，则可以使“删除”过程更有效。 是的，你必须添加一些代码来处理你是如何做到的，但是回报就是效率。
就像一个例子 – 假设你有一个List 。 然后，您可以将该特定项设置为null并使用它完成。
队列类很难理解。 请改用通用列表。