Diskussion zum Artikel "Von den Grundlagen bis zur Mittelstufe: Warteschlangen, Listen und Bäume (II)"

Neuer Artikel Von den Grundlagen bis zur Mittelstufe: Warteschlangen, Listen und Bäume (II) :

Dies ist ein Artikel, den Sie, lieber Leser, sorgfältig durcharbeiten sollten. Das liegt an der Art des hier vorgestellten Materials. Obwohl wir uns bemüht haben, den Stoff so einfach und informativ wie möglich darzustellen, können die hier bereitgestellten Informationen für diejenigen, die gerade erst mit dem Programmieren beginnen, durchaus recht komplex erscheinen. Dennoch ist dies kein Grund, den Mut zu verlieren oder das hier Erläuterte zu ignorieren, da dieser Artikel eine Verbindung zwischen zwei völlig unterschiedlichen, wenn auch eng miteinander verbundenen Themen herstellen wird.

Nun, wenn Sie gerade erst mit dem Programmieren anfangen, sind Sie wahrscheinlich noch etwas unsicher, wo und wie Sie das im vorherigen Artikel Behandelte anwenden können. Dennoch kann die Fähigkeit, das dort Besprochene und Erklärte anzuwenden, in vielen Situationen eine entscheidende Rolle für Ihre Karriere als Programmierer spielen. Aber Ihnen ist wahrscheinlich schon aufgefallen, dass sowohl die FIFO-Warteschlange als auch die Ringwarteschlange eines gemeinsam haben: Die Elemente darin werden immer in der Reihenfolge verarbeitet, in der sie der Warteschlange hinzugefügt wurden. Mit anderen Worten: Das älteste Element wird immer zuerst gelesen, und daher wird das neueste Element in der Warteschlange immer zuletzt gelesen. Oft müssen wir diese Reihenfolge jedoch umkehren. Wir möchten also, dass das neueste Element zuerst gelesen wird und das älteste Element in der Warteschlange zuletzt.

Man könnte sogar meinen, dass es hierfür ausreichen würde, einfach die Reihenfolge zu ändern, in der die Elemente einer FIFO-Warteschlange oder einer Ringwarteschlange ausgelesen werden. Tatsächlich ist es in manchen praktischen Situationen genau so. Es gibt jedoch eine Art von Warteschlange, die speziell dafür entwickelt wurde, dies zu ermöglichen, ohne dass bestehender Code geändert werden muss. Diese Art von Warteschlange, die speziell dafür konzipiert ist, die Reihenfolge der Elemente umzukehren, wird als Stapel bezeichnet.

Ein Stapel ist nichts anderes als das, was der Name schon sagt. Mit anderen Worten: Wenn wir neue Elemente hinzufügen, können wir ältere Elemente nicht entfernen, ohne zuvor die zuletzt hinzugefügten zu entfernen. Es gibt sogar ein Spielzeug, das perfekt veranschaulicht, was ein Stapel ist und wo man ihn einsetzen kann. Dieses Spielzeug ist auf der folgenden Abbildung zu sehen.

Für alle, die dieses Spielzeug nicht kennen: Es ist unter dem Namen „Türme von Hanoi“ bekannt. Glauben Sie mir, dieses Spielzeug wurde bereits in der Vergangenheit zur Analyse und zum Vergleich von Prozessoren eingesetzt. Das liegt daran, dass es Möglichkeiten gibt, damit eine genaue Schätzung der Verarbeitungsgeschwindigkeit zu erhalten. Da jedoch viele Prozessoren zunehmend darauf optimiert wurden, den Algorithmus selbst zu beschleunigen, anstatt die tatsächliche Rechengeschwindigkeit der CPU zu steigern, wurde dieses Vergleichsmodell letztendlich aufgegeben. Wenn Sie selbst versuchen möchten, die Türme von Hanoi zu lösen, können Sie sich auf der Website von Somatemática umsehen.


Autor: CODE X