Kürzlich, in einem Interview wurde ich den Nachteil der Verwendung der zirkulären Warteschlange gefragt. Ich konnte mir keine vorstellen. Bei der Suche im Internet ist die einzige Antwort, die ich gefunden habe, dass es schwierig zu implementieren ist als die lineare Warteschlange :). Gibt es einen anderen Nachteil?Nachteil der zirkulären Warteschlange?
Es scheint mir, dass jeder Code, der die Warteschlange durchläuft, den ersten Knoten verfolgen muss, um das Ende der Überquerung zu erkennen. In einer Umgebung mit mehreren Threads kann jedoch ein anderer Thread den ersten Knoten entfernen, wodurch der traversierende Thread in eine Endlosschleife versetzt wird. Der durchlaufende Thread müsste also den ersten Knoten für die Dauer seines Zyklus durch die Warteschlange gesperrt halten.
Dann wiederum gibt es normalerweise Gefahren für die Verwendung jeder Art von Liste während der Aufzählung. Zum Beispiel könnte das Ende einer regulären verknüpften Liste gelöscht und in den Kopf verschoben werden (nicht ungewöhnlich, wenn es um Warteschlangen geht), was einen Iterator unterbrechen könnte. – nneonneo
Wird dies nicht im Fall von gemeinsam genutztem Speicher zwischen mehreren Prozessen passieren? Ich frage wie du explizit * threads * nennst – asheeshr
@AshRj Ja könnte es bei mehreren Prozessen durchaus vorkommen. –
Ich würde sagen, der größte Nachteil einer kreisförmigen Warteschlange ist, dass Sie nur queue.length-Elemente speichern können. Wenn Sie es als Puffer verwenden, begrenzen Sie Ihre Historientiefe.
Ein weiterer kleinerer Nachteil ist, dass es schwierig ist, eine leere Warteschlange von einer vollständigen Warteschlange zu unterscheiden, ohne zusätzliche Informationen beizubehalten.
Nicht so schwer. Siehe Kommentare zu Frage. Es gibt mindestens 2 Möglichkeiten, es zu tun ... –
Die Antwort, nach der der Interviewer gesucht hat, hängt wahrscheinlich von einem zusätzlichen Kontext ab, der in der obigen Frage nicht enthalten ist.
Zum Beispiel werden häufig kreisförmige Warteschlangen für stark konkurrierende Erzeuger/Verbraucher-Systeme in Betracht gezogen. Wenn die Warteschlange voll ist, können Operationen an der Vorder- und Rückseite der Warteschlange um die gleichen Cache-Zeilen konkurrieren, und das kann in solchen Kontexten ein Problem sein.
Oder vielleicht wollte der Interviewer Sie sprechen, wie viel einfacher es in einer müllsammelbaren Sprache ist, eine blockierungsfreie Verbindungswarteschlange im Vergleich zu einer zirkularen Array-basierten Warteschlange zu erstellen.
Oder vielleicht geht es nur darum, wie Sie die Vektorbehälter, die von Ihrer Sprache zur Verfügung gestellt werden, viel besser nutzen können, wenn Sie eine lineare Warteschlange mit periodischer Verschiebung statt einer kreisförmigen Warteschlange verwenden.
Je nach Implementierung müssen Sie einen Knoten möglicherweise in einer kreisförmigen Warteschlange leer lassen, während eine lineare Warteschlange vollständig gefüllt sein kann. Nicht viel Nachteil, es sei denn jeder Knoten ist gigantisch! – asheeshr
Warum muss ein Knoten leer bleiben? –
Es hängt davon ab, wie Sie die ringförmige Warteschlange implementieren. Wenn Sie Daten in jedem Knoten speichern, gibt es keine einfache Möglichkeit, zwischen einer leeren und einer vollständigen Liste zu unterscheiden. – asheeshr