Ho avuto una domanda su come rimuovere un elemento dal centro della coda, senza disturbare l'ordine di altri elementi.
per es.
Coda prima dell'operazione: - < | a b c d e | <
coda dopo operazione: - < | a b d e | <
Nota: - Conosco il modo generico di rimuovere a, b e inserire di nuovo in coda, seguito da d ed e. Ma ho bisogno di un modo più rapido ed efficiente.
Le code sono generalmente considerate come un tipo di dati astratto che solo ha enqueue e dequeue operazioni. Quindi nel caso generale, non possiamo usare altre funzioni.
Diamo un'occhiata al caso di una coda FIFO che supporta solo queste due operazioni e inoltre ha una proprietà size . Ottenere e rimuovere l'elemento centrale è banale rimuovendo anche tutti gli elementi precedenti:
val q: Queue[Item] = ...;
val half_size: Int = q.size / 2;
var result: Item = null;
while (q.size > half_size) {
result = q.dequeue();
}
Tuttavia, la riproduzione degli articoli rimossi nell'ordine corretto richiede la rimozione di tutti gli elementi, poiché non è possibile reinserire gli elementi alla fine! abbiamo per fare qualcosa del genere:
val q: Queue[Item] = ...;
val temp: Queue[Item] = new Queue();
val half_size: Int = q.size / 2;
var result: Item = null;
while (q.size > 0) {
val item = q.dequeue();
if (q.size == half_size) {
result = item;
} else {
temp.enqueue(item);
}
}
while (temp.size > 0) {
q.enqueue(temp.dequeue());
}
Ovviamente, questo funziona solo se la coda di input non viene modificata mentre viene eseguito questo algoritmo.
Per le code LIFO (ad esempio, pile), dobbiamo solo rimuovere metà degli elementi in quanto possiamo riprodurre gli articoli nell'ordine corretto. Per uno stack, di solito chiamiamo enqueue push e dequeue pop .
val q: Stack[Item] = ...;
val temp: Stack[Item] = new Stack();
val half_size: Int = q.size / 2;
var result: Item = null;
while (q.size > half_size) {
result = q.pop();
temp.push(result);
}
while (temp.size > 0) {
q.push(temp.pop());
}
Alcune implementazioni di code sono in realtà elenchi concatenati completi (ad es. in Java, java.util.LinkedList soddisfa l'interfaccia java.util.Queue ). Se abbiamo accesso a tali dettagli di implementazione di una coda, possiamo suddividere l'elemento più facilmente. Quindi, se abbiamo un LinkedList piuttosto che un Queue , possiamo semplicemente list.remove(indexOfTheMiddleElement) . A seconda della lingua che stai utilizzando, potresti essere in grado di prendere alcune scorciatoie.
Leggi altre domande sui tag data-structures algorithms queue