Есть ли лучший способ реализовать метод 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);
}