有没有更好的方法来实现队列的删除方法？

Question

首先，假设我确实需要 Queue<T> 的功能——先进先出，通常只需要 Enqueue / Dequeue 等操作。因此，我希望得到的回答不是“你真正需要的是 List<T>”（我知道有 RemoveAt 方法）。

例如，假设我有一个数据点队列 Queue<DataPoint> dataToProcess，需要按照它们到达的顺序进行处理。然后，周期性地执行以下代码是有意义的：

while (dataToProcess.Count > 0) {
    DataPoint pointToProcess = dataToProcess.Dequeue();
    ProcessDataPoint(pointToProcess);
}

但是假设由于某种原因，发现将添加到队列中的特定数据点不应被处理。那么最好有一种类似于以下方法的方法：

dataToProcess.Remove(badPoint);

我知道没有可行的方法可以实现一个不涉及枚举的Remove方法；但是，由于Queue<T>并不能让你随意删除某个项目，所以我能想到的唯一解决方案是：

bool Remove(T item) {
    bool itemFound = false;

    // set up a temporary queue to take items out
    // one by one
    Queue<T> receivingQueue = new Queue<T>();

    // move all non-matching items out into the
    // temporary queue
    while (this.Count > 0) {
        T next = this.Dequeue();
        if (next.Equals(item)) {
            itemFound = true;
        } else {
            receivingQueue.Enqueue(next);
        }
    }

    // return the items back into the original
    // queue
    while (receivingQueue.Count > 0) {
        this.Enqueue(receivingQueue.Dequeue());
    }

    return itemFound;
}

这很荒谬吗？看起来确实不好，但我想除了编写自定义类之外，没有更好的方法。即使是这样，我所能想到的最好的实现“Remove”方法的方式是在内部使用 LinkedList<T>。

- Dan Tao

---

PowerCollections (@codeplex) 可能对你有用。 - bohdan_trotsenko

Answer 1

我认为转换到一个具有LinkedList内部的新自定义类只需要几分钟，而且比您现在拥有的更具性能。

public class SpecialQueue<T>
{
    LinkedList<T> list = new LinkedList<T>();

    public void Enqueue(T t)
    {
        list.AddLast(t);
    }

    public T Dequeue()
    {
        var result = list.First.Value;
        list.RemoveFirst();
        return result;
    }

    public T Peek()
    {
        return list.First.Value;
    }

    public bool Remove(T t)
    {
        return list.Remove(t);
    }

            public int Count { get { return list.Count; } }
}

- Jake Pearson

---

我想我会倾向于同意你的观点，这就是为什么我问这个问题的原因--因为我想不出使用Queue<T>来完成这个任务的好方法，但我认为也许有人能看到我所忽略的东西。 - Dan Tao

此外，您可以通过在出队时进行入队操作而不是将队列保存到临时列表中来加快现有方法的速度。 - Jake Pearson

@Jake：非常聪明——我没有想到！虽然你的LinkedList实现看起来确实更好（而且与我所做的相匹配……我猜这几乎就是唯一的方法了）。 - Dan Tao

Answer 2

另一种方法是将项目保留在队列中，在从中读取时忽略它们。类似于：

T DequeueFiltered(HashSet<T> ignored) {
   T item;
   while (ignored.Contains(item = Dequeue())) {
      ignored.Remove(item);
   }
   return item;
}

- Guffa

---

我认为这是一个非常聪明的建议。我能看到的一个问题是，由于该项仍然在队列中，因此必须有一个经过筛选的GetEnumerator形式，在枚举过程中跳过被忽略的项。 - Dan Tao

Answer 3

我是一个初学者，但我最近成功解决了相同（或非常相似）的问题。希望能对您有所帮助。

这是我们的队列：

Queue<T> dataToProcess = new Queue<T>();

假设我们将所有已排队的项目复制到一个哈希集中，会发生什么情况（例如：

HashSet<T> pointsToProcess = new HashSet<T>(); 

所以当我们将元素加入队列时，我们也将相同的数据添加到哈希集合中。

当确定不需要某个元素时，我们从哈希集合中移除它。

pointsToProcess.Remove(element);

因此，当我们需要“使用”队列的下一个元素时，

我们检查是否真的需要处理它（如果它是哈希集合的成员），否则就必须忽略它并且可以将其删除，

while (dataToProcess.Count > 0) {


if  pointsToProcess.Contains(dataToProcess.Peek())
{


// processing data


}

else
{

// error message and

dataToProcess.Dequeue();

}


}

- vampierre

Answer 4

请看 c# 给 .NET Queue 类添加 Remove(int index) 方法

队列是最有效的排队结构，用列表数据结构实现队列不是很高效。

虽然没有内置的方法，但如果删除不是频繁操作，则不应使用 List 结构或其他结构。

如果您通常进行入队和出队，但只偶尔进行删除，则在删除时应该能够承受队列重建。

请查看链接以获取两个简单的扩展方法

public static void Remove<T>(this Queue<T> queue, T itemToRemove) where T : class

public static void RemoveAt<T>(this Queue<T> queue, int itemIndex) where T : class

- Kind Contributor

Answer 5

var first = Q.Dequeue();
if (first.Id.Equals(deleteId)) return;
Q.Enqueue(first);

while (Q.Peek() != first)
{
   var r = Q.Dequeue();
   if(!r.Id.Equals(deleteId)) Q.Enqueue(r);
} 

- jenspo