Aus einer Menge von 1 Elementen einen Eintrag aus der Warteschlange entfernen

Question

Bei einer einfach verknüpften Listenimplementierung eines Warteschlangentyps mit vorderen und hinteren Zeigern müssen Sie den hinteren Zeiger einstellen, wenn Sie einen Eintrag aus einer Menge von 1 Elementen entfernen zu null?

lese ich C++ Plus-Datenstrukturen von Nell Dale, und in Kapitel 5.2, schreibt er in seiner Dequeue Methode:

if (front == NULL) 
    rear == NULL; 

Ich frage mich, warum dies notwendig ist. Der einzige Grund, warum ich denken kann, ist die Art, wie er Enqueue in Bezug auf einen leeren Satz implementiert:

if (rear == NULL) 
    front = newNode; 
else 
    rear->next = newNode; 
rear = newNode; 

Aber könnte diese Bedingung nicht zu if (front == NULL)

Answer 1

Für den korrekten Code geändert werden, müssen Sie die pflegen Datenstruktur Invarianten mit jeder Operation. Die Art und Weise der ursprüngliche Code geschrieben wird, sehen die Invarianten wie folgt aus:

• A1: front zeigt auf das erste Element, wenn es vorhanden ist; NULL sonst
• A2: rear zeigt auf das letzte Element, wenn es existiert; NULL sonst

Sie behaupten, dass die Invarianten alternativ diese sein könnten:

• B1: front zeigt auf das erste Element, wenn es vorhanden ist; NULL sonst
• B2: rear zeigt auf das letzte Element, wenn es vorhanden ist

Nun sind diese ähnlich sind, aber nicht identisch. Die B-Invarianten benötigen keinen bestimmten Wert von rear, wenn die Liste leer ist. Jetzt können Sie verwenden die B-Invarianten, um die Liste zu implementieren, sicher, da es Diskriminierung zwischen leeren und nicht leeren Staaten zulässt, und das ist genug, um korrekte Implementierungen bereitzustellen.

Das sagt aber nichts darüber aus, ob A oder B in der Praxis besser sind. Wenn Sie die B-Invarianten verwenden, kann eine Funktion, mit der Sie nach dem letzten Element suchen, nicht einfach den Wert rear zurückgeben, da der Wert alles sein kann, wenn die Warteschlange leer ist. Sie müssen zuerst den Wert front testen.

// for the A2 invariant 
return rear ; 

// for the B2 invariant 
return (front == NULL) ? NULL : rear ; 

Dies läuft darauf hinaus, ob testen-and-assign zu wollen, wenn Sie aus der Warteschlange entfernt oder ob testen zu wollen, wenn Sie auf dem letzten Element spähen. Dies ist eine Optimierungsfrage, keine Korrektheit. Wenn Sie nie auf das letzte Element schauen müssen, können Sie dafür optimieren.

All dies sagte, dies ist ein Hauptfall für die Gefahren der vorzeitigen Optimierung. Eine zusätzliche Zeigerzuweisung zu NULL wird fast nie ein Leistungsproblem sein. Viel wahrscheinlicher ist jedoch die Einführung eines Fehlers während der Wartung, wenn sich jemand auf die A-Invarianten verlässt, wenn der vorhandene Code die B-Variablen verwendet. Die A-Invarianten sind kognitiv einfacher, weil front und rear analog aufgebaut sind, ohne dass sie ein spezielles Verhalten haben. Die B-Invarianten könnten besser funktionieren, aber auf Kosten der Komplexität. Je nach Ihren Umständen ist die Wahl besser.Die Moral dieser Geschichte: Immer dokumentieren Sie Ihre Invarianten.