有没有更好的方法来为队列实现 Remove 方法? [英] Is there a better way to implement a Remove method for a Queue?

问题描述

首先，请承认我确实想要 Queue<T> 的功能——FIFO，一般只需要 Enqueue/Dequeue 等等——所以我更喜欢你真正想要的是一个 List<T>"以外的答案(我知道 RemoveAt).

First of all, just grant that I do in fact want the functionality of a Queue<T> -- FIFO, generally only need Enqueue/Dequeue, etc. -- and so I'd prefer an answer other than "What you really want is a List<T>" (I know about RemoveAt).

例如，假设我有一个 Queue;dataToProcess 需要按到达顺序处理的数据点.然后定期有一些这样的代码是有意义的:

For example, say I have a Queue<DataPoint> dataToProcess of data points that need to be processed in the order in which they arrived. Then periodically it would make sense to have some code like this:

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

然后假设，无论出于何种原因，发现已添加到队列中的特定数据点不应该被处理.如果有类似于以下的方法，那将是理想的:

But then suppose, for whatever reason, it's discovered that a particular data point which has been added to the queue should not be processed. Then it would be ideal if there were a method analogous to:

dataToProcess.Remove(badPoint);

我知道确实没有可行的方法来拥有不涉及某种形式的枚举的 Remove 方法；但是，由于 Queue<T> 并不能真正让您走进并随机删除一些项目，因此我能想到的唯一解决方案是:

I understand that there's really no feasible way to have a Remove method that does not involve some form of enumeration; however, since a Queue<T> doesn't really let you just walk in and remove some item randomly, the only solution I could figure out was this:

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>.

Is this ridiculous? It certainly looks bad, but I can't really see a better way, other than writing a custom class. And even then, the best way I could think to implement a Remove method would be to use a LinkedList<T> internally.

推荐答案

我认为切换到内部具有 LinkedList 的新自定义类只需要几分钟，并且比现在的性能要高得多.

I think switching over to a new custom class that had a LinkedList internally would only take you a few minutes and would be much more performant than what you have now.

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; } }
}

这篇关于有没有更好的方法来为队列实现 Remove 方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！