Esiste un modo migliore per implementare un metodo di rimozione per una coda?

Question

Prima di tutto, concedimi solo che in effetti desidero la funzionalità di un Queue<T> - FIFO, generalmente solo Enqueue/Dequeue, ecc. - e quindi preferirei una risposta diversa da "Quello che vuoi veramente è a List<T> "(So di RemoveAt).

Ad esempio, supponiamo di avere uno Queue<DataPoint> dataToProcess di punti dati che devono essere elaborati nell'ordine in cui sono arrivati. Poi periodicamente avrebbe senso avere qualche codice come questo:

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

Ma poi supponiamo, per qualsiasi motivo, si è scoperto che un particolare punto di dati che è stato aggiunto alla coda dovrebbe non essere elaborato. Allora sarebbe l'ideale se ci fosse un metodo analogo a:

dataToProcess.Remove(badPoint); 

Capisco che non c'è davvero alcun modo fattibile per avere un metodo Remove che non comporta una qualche forma di enumerazione; tuttavia, dal momento che un Queue<T> in realtà non consentono solo a piedi e rimuovere qualche elemento a caso, l'unica soluzione che ho potuto capire era questo:

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

È questo il ridicolo? Certamente lo sembra , ma non riesco a vedere un modo migliore, se non scrivere una classe personalizzata. E anche in quel caso, il modo migliore che potessi pensare per implementare un metodo Remove sarebbe utilizzare internamente un LinkedList<T>.

Answer 1

Penso che passare a una nuova classe personalizzata che aveva una LinkedList internamente richiederebbe solo pochi minuti e sarebbe molto più performante di quello che si ha ora.

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

Answer 2

Un'alternativa potrebbe essere quella di lasciare solo gli elementi in coda, e ignorarli quando si sta leggendo da esso. Qualcosa di simile:

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

Answer 3

Sono un principiante tuttavia sono riuscito a risolvere lo stesso problema (o molto simile) di recente. Spero che aiuti.

Qui è la nostra coda:

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

Che cosa succede se mettiamo una copia di tutti gli elementi accodate in un hashset (ad esempio:

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

così quando enqueueing gli elementi aggiungiamo anche gli stessi dati per l'hashset.

e quando si scopre che non abbiamo bisogno di un elemento, abbiamo rimuovere da quel hashset

pointsToProcess.Remove(element); 

così quando dobbiamo 'uso' l'elemento successivo della coda,

siamo esaminare se abbiamo davvero bisogno di trattare con esso (se è membro del HashSet), altrimenti deve essere ignorato e possiamo sbarazzarci di esso,

while (dataToProcess.Count > 0) { 


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


// processing data 


} 

else 
{ 

// error message and 

dataToProcess.Dequeue(); 

} 


} 

Answer 4

vedere c# Adding a Remove(int index) method to the .NET Queue class

La coda è la struttura più efficiente per l'accodamento, l'implementazione di una coda su una struttura di dati dell'elenco non è efficiente.

Anche se non c'è un modo integrato, non si dovrebbe usare una struttura List o altra struttura, IFF Rimuovi non è un'operazione frequente.

Se si esegue normalmente l'accodamento e la riaccensione, ma solo occasionalmente la rimozione di , è necessario consentire la ricostruzione della coda quando si rimuove la memoria .

si veda il link per due semplici metodi di estensione

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

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