Am 14. September 2017 haben wir eine überarbeitete Fassung unserer Datenschutzrichtlinie veröffentlicht. Wenn Sie video2brain.com weiterhin nutzen, erklären Sie sich mit diesem überarbeiteten Dokument einverstanden. Bitte lesen Sie es deshalb sorgfältig durch.

Grundlagen der Programmierung: Datenstrukturen

Stapel und LIFO

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Stapel sind sehr beschränkt funktionierende Datenstrukturen. Sie agieren nach dem Last In First Out(LIFO)-Prinzip.

Transkript

Im Folgenden werden wir über Datenstrukturen sprechen, die Stacks beziehungsweise Queues genannt werden. Also Stapel beziehungsweise Warteschlangen. Stacks und Queues sind Sammlungen, wie es auch Arrays und Listen sind. Sie sind eine weitere Art, um unterschiedliche Inhalte aufzubewahren. Wenn wir von Stacks und Queues sprechen, verbinden wir damit keine verschrobenen, esoterischen Bedeutungen. Sie bedeuten exakt das, was sie sind: Stapel und Warteschlangen. So, als würden wir mit Großmutter darüber reden. Denken Sie einmal an einen Stapel Papier. Ein Stapel Bücher, ein Stapel schmutziger Teller in einem Restaurant. Die Idee des Stacks ist, dass Sie, wenn Sie etwas zum Stapel hinzufügen, Sie es dann obendrauflegen. Und wenn weiter schmutzige Teller in die Küche gebracht werden, werden sie oben auf den Stapel draufgelegt. Und wenn wir etwas vom Stack wegnehmen, nehmen wir es ebenfalls von oben weg. Der letzte Teller, der hinzugefügt wurde, wird der erste sein, der wieder weggenommen wird. Der letzte rein, der erste raus. Last in, first out. Was genau ist das Konzept hinter einem Stack beim Programmieren? Wir haben eine Datenstruktur von unterschiedlichen Elementen, bei denen das letzte hinzugefügte Element auch das erste ist, was rausgenommen wird. Last in, first out. LIFO-Datenstruktur. Anders als beim Array befassen wir uns nicht mit einem numerischen Index für diese Elemente. Wir wollen nicht an einen numerischen Index denken. Wir kümmern uns um – eigentlich gar nichts. Außer um zwei grundlegende Operationen auszuführen. Damit wir ein neues Element zum Stapel hinzufügen können, und dass wir das oberste Element wieder vom Stapel entfernen können. Das ist alles. Und die dafür verwendeten Begriffe sind in fast allen Programmiersprachen gleich. Wir verwenden push und pop. Das sind Begriffe, die wir schon vom dynamischen Array her kennen. Push heißt also, dass wir ein Element ans Ende der Datenstruktur pushen. Ein neues Element oben auf den Stapel drauf, und wenn wir ein Element vom Stapel nehmen wollen, dann verwenden wir pop. Pop wird uns das oberste Element des Stapels herausnehmen. Es ist wichtig im Hinterkopf zu behalten, dass wir ein Element vom Stapel entfernen, wenn wir pop verwenden. Bei pop schauen wir nicht nur einfach ans Ende, pop gibt uns den Wert eines Elements zurück oder entfernt dieses Element vom obersten Teil des Stapels. Wenn Sie sich jetzt fragen, was soll ich tun, wenn ich aber nur hineinschauen möchte? Die meiste Zeit, wenn Stacks implementiert werden, wird auch diese Möglichkeit des Zugriffs mitbedacht. Wir werfen nur einen Blick auf das oberste Element, und tatsächlich bleibt das Element aber noch im Stack enthalten. Dieses verhalten wird als peek bezeichnet. Das sind dann auch schon die drei grundlegenden Verhaltensmuster in einem Stack. Pop, push und eventuell auch noch peek. Aber es ist immer last in, first out. Hier ist die wichtigste daraus resultierende Idee, dass nämlich die Arbeit mit Stacks noch einfacher sein sollte, als die Arbeit mit Arrays oder verlinkten Listen. Denn es gibt weniger, was man mit einem Stack machen kann. Es ist eine ganz bewusst sehr eingeschränkte und von der Intention her beschränkte und beschränkende Datenstruktur. Wir werden nie Elemente in der Mitte oder ganz am Anfang einfügen. Wir müssen uns nicht um nach vorne oder nach hinten verweisende Links kümmern und keine Einträge neu organisieren. Wir kümmern uns auch nicht um irgendeinen Index. Alles, was wir tun, ist push, pop und vielleicht auch noch peek. Und wenn Sie versuchen, irgendetwas anderes mit einem Stack zu machen, dann haben Sie einfach nur die falsche Datenstruktur gewählt. Wie ist es jetzt mit der Unterstützung von Stacks? Stacks werden in so gut wie jeder Sprache in irgendeiner Form unterstützt. In Java zum Beispiel ist es eine ganz reguläre Klasse, eine Stack-Klasse, die Sie erzeugen können. Es gibt dabei nur ganz wenige Methoden. Wir haben peek, pop und push. Und es gibt eine Suche. Es gibt auch noch eine Kontrolle, ob dieser Stack leer ist oder nicht. Ähnliche Optionen gibt's auch im .NET. Wir haben eine Stack-Klasse, Die hat ein paar eingebaute Möglichkeiten. Ebenfalls arbeiten wir hier mit peek, pop und push. Und wenn wir in den Python-Bereich schauen, gibt's da zwar keine explizite Stack-Klasse, aber es gibt eine eigene Abteilung mit regulären Python- Dokumentationen in der Liste, wie Stacks verwendet werden. Wir könnten aber genausogut ein Array verwenden. Das Array, wie wir bereits gesehen haben, hat push- und pop-Methoden, die wir genau dafür verwenden können. Und in C++ ist der Stack ein Bestandteil der Standardvorlagenbibliothek. Wieder geht's hier um push- und pop-Methoden. Wenn eine Sprache keinen extra definierten Stack-Typen hat, wie zum Beispiel Objective C, kann immer noch ein dynamisches Array verwendet werden, um dort am Ende Elemente hinzuzufügen oder wieder zu entfernen. Dafür haben sehr viele Sprachen diese push- und pop-Methoden bei ihren dynamischen Arrays mit dabei. Damit sie eben wie Stapel verwendet werden können, falls notwendig.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
Derzeit sind keine Feedbacks vorhanden...
 

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!