Есть ли лучший способ реализовать метод Remove для очереди?

Прежде всего, просто дайте, что я действительно хочу функциональность Queue<T> - FIFO, как правило, нужно только 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> внутренне.

Ответы

Ответ 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; } }
}

Ответ 2

Альтернативой может быть просто оставить элементы в очереди и игнорировать их, когда вы читаете их. Что-то вроде:

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

Ответ 3

Я новичок, но мне удалось решить ту же (или очень похожую) проблему в последнее время. Надеюсь, это поможет.

Вот наша очередь:

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

Что делать, если мы помещаем копию всех выделенных элементов в хешсет (например:

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

поэтому при вставке элементов мы также добавляем те же данные в хэшсет.

и, когда оказывается, нам не нужен элемент, мы удаляем его из этого hashset

pointsToProcess.Remove(element);

поэтому, когда мы должны "использовать" следующий элемент очереди,

мы проверяем, действительно ли нам нужно иметь дело с ним (если он является членом hashset), в противном случае его нужно игнорировать, и мы можем избавиться от него,

while (dataToProcess.Count > 0) {


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


// processing data


}

else
{

// error message and

dataToProcess.Dequeue();

}


}

Ответ 4

см. С# Добавление метода Remove (int index) к классу .NET Queue

Очередь - это наиболее эффективная структура для организации очередей, реализация очереди в структуре данных списка неэффективна.

Хотя нет встроенного способа, вы не должны использовать список структуры или другой структуры, IFF Remove - это не частая операция.

Если вы обычно задерживаетесь и убираете, но только изредка удаление, то вы должны иметь возможность перестраивать очередь, когда удаление.

см. ссылку для двух простых методов расширения

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

Ответ 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);
}