我想使用 .NET 框架 (3.5) 中描述的通用队列类，但我需要一个 Remove(int index) 方法来从队列中删除项目。我可以使用扩展方法实现此功能吗？有人愿意指出我正确的方向吗？
Jacob
问问题
48580 次
12 回答
25
你想要的是一个List<T>当RemoveAt(0)你想从Queue. 其他一切都是一样的，真的（调用Add会将一个项目添加到 的末尾Queue）。
于 2009-02-10T06:21:41.427 回答
15
将 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];
}
}
测试代码：
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");
}
}
于 2012-01-28T21:21:58.980 回答
15
这是使用一行 Linq 从队列中删除特定项目的方法（它正在重新创建队列，但由于缺乏更好的方法......）
//replace "<string>" with your actual underlying type
myqueue = new Queue<string>(myqueue.Where(s => s != itemToBeRemoved));
我知道它不是按 index删除的，但仍然有人可能会觉得这很有用（这个问题在 Google 中排名为“从 ac# 队列中删除特定项目”，所以我决定添加这个答案，抱歉）
于 2014-08-19T12:47:48.103 回答
8
这是一个很晚的答案，但我是为未来的读者写的
List<T>正是您所需要的，但Queue<T>与. 甚至使用一个数组，但有两个索引（用于头部和尾部）。Dequeue()Array.CopyQueue<T>
在您的情况下，您还需要Remove/RemoveAt并且它的性能不会很好（出于同样的原因：如果您不从列表尾部删除，则必须分配另一个数组并复制项目）。
具有快速Dequeue/Remove时间的更好的数据结构是链表（您将牺牲 - 一点点 - 性能，Enqueue但假设您的队列具有相同数量的Enqueue/Dequeue操作，您将获得很大的性能提升，特别是当它的大小时会成长）。
让我们看一个简单的实现框架（我将跳过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>();
}
快速比较：
队列列表 LinkedList 入队 O(1)/O(n)* O(1)/O(n)* O(1) 出队 O(1) O(n) O(1) 删除 n/a O(n) O(n)
* O(1) 是典型情况，但有时会是 O(n)（当内部数组需要调整大小时）。
当然，您会为所获得的东西付出一些代价：内存使用量更大（尤其是对于较小的T开销会很棒）。必须根据您的使用场景仔细选择正确的实现（List<T>vs LinkedList<T>），您也可以将该代码转换为使用单链表以减少 50% 的内存开销。
于 2014-07-03T12:12:19.143 回答
7
有人可能会开发出更好的解决方案，但据我所知，您需要在 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;
}
}
于 2009-02-10T06:06:53.193 回答
6
尽管没有内置方式，但您不应该使用 List 结构或其他结构，IFF RemoveAt 不是常用操作。
如果您通常入队和出队但只是偶尔删除，那么您应该能够在删除时重新构建队列。
public static void Remove<T>(this Queue<T> 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<T>(this Queue<T> queue, int itemIndex)
{
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]);
}
}
以下方法可能更有效，使用更少的内存，从而减少 GC：
public static void RemoveAt<T>(this Queue<T> queue, int itemIndex)
{
var cycleAmount = queue.Count;
for (int i = 0; i < cycleAmount; i++)
{
T item = queue.Dequeue();
if (i == itemIndex)
continue;
queue.Enqueue(item);
}
}
于 2017-02-20T02:02:55.993 回答
2
事实上，这违背了 Queue 的全部目的，并且您最终会提出的类将完全违反 FIFO 语义。
于 2009-02-10T07:22:13.233 回答
2
如果 Queue 用于保留集合中项目的顺序，并且您不会有重复的项目，那么SortedSet可能就是您要寻找的。这些SortedSet行为很像 a List<T>，但保持有序。非常适合下拉选择之类的东西。
于 2012-03-26T18:27:28.447 回答
2
我不认为我们应该List<T>用来模拟队列，对于队列，入队和出队操作应该非常高效，而在使用List<T>. 然而，对于该RemoveAt方法，可以接受的是非性能，因为它不是 a 的主要目的Queue<T>。
我的实现方法RemoveAt是 O(n)，但队列仍然保持很大程度上 O(1) 入队（有时内部数组需要重新分配，这使得操作 O(n)）并且总是 O(1) 出队。
这是我对 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();
}
}
其中MoveHeadToTail定义如下：
private static void MoveHeadToTail<T>(this Queue<T> queue)
{
Contract.Requires(queue != null);
var dequed = queue.Dequeue();
queue.Enqueue(dequed);
}
此实现还修改了实际Queue<T>而不是返回一个新的Queue<T>（我认为这与其他RemoveAt实现更一致）。
于 2013-12-13T12:50:45.237 回答
1
大卫安德森的解决方案可能是最好的，但有一些开销。您是否在队列中使用自定义对象？如果是这样，请添加一个布尔值，如取消
如果设置了该布尔值，请与处理队列的工作人员核实，然后跳过它。
于 2009-02-10T08:37:58.790 回答
0
请注意，如果您不实际删除项目而只是将其“标记”为“已删除”，则使用列表可以使“删除”过程更有效。是的，你必须添加一些代码来处理你是如何做到的，但回报是效率。
举个例子 - 假设你有一个List<string>. 然后，例如，您可以将该特定项目设置为 null 并完成它。
于 2015-07-11T01:05:43.183 回答
-3
队列类很难理解。请改用通用列表。
于 2011-11-09T02:42:37.257 回答