1:48:35
Datenstrukturen und Algorithmen 3
Jens Krüger
Overview
Diese Vorlesung konzentriert sich auf die Implementierung und Anwendung von Stacks und Queues, zwei grundlegenden Datenstrukturen. Zunächst wird die Implementierung eines Stacks mithilfe eines Arrays vorgestellt, wobei Herausforderungen wie feste Kapazitäten und Speicherverwaltung diskutiert werden. Anschließend wird die Implementierung einer Queue mit einer verketteten Liste und einem Array behandelt, wobei die Unterschiede in Zeit- und Speicherkomplexität sowie die Bedeutung von dynamischen Größenanpassungen hervorgehoben werden. Abschließend werden praktische Anwendungsfälle für Stacks und Queues in der Programmierung erläutert.
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- Das ABZ bietet Unterstützung bei organisatorischen und lernbezogenen Fragen während des Studiums.
- Es gibt Beratung bei Studienentscheidungen und Krisen sowie psychologische Unterstützung.
- Das ABZ unterstützt Studierende mit chronischen Erkrankungen oder Behinderungen (Inklusion).
- Konflikte mit Dozierenden oder Diskriminierung können über die Ombudsperson geklärt werden.
- Der Career Service hilft bei Bewerbungen und Lebensläufen am Ende des Studiums.
Das ABZ ist eine wichtige Anlaufstelle für Studierende, die Unterstützung in verschiedenen Phasen und bei unterschiedlichen Problemen während ihres Studiums benötigen.
Studierende können das ABZ aufsuchen, wenn sie eine Prüfung nicht bestanden haben und Unterstützung beim Lernen benötigen.
- Stacks und Queues sind grundlegende Datenstrukturen, die auf Arrays oder verketteten Listen basieren.
- Eine Array-basierte Stack-Implementierung erfordert eine anfänglich festgelegte maximale Kapazität.
- Elemente werden sequenziell in das Array eingefügt (Push) und von hinten entnommen (Pop).
- Ein Zähler (N) verfolgt die Anzahl der Elemente und bestimmt die nächste freie Position.
- Probleme sind Overflow (zu viele Elemente) und Underflow (Entnahme aus leerem Stack).
Das Verständnis der Array-basierten Stack-Implementierung legt die Grundlage für das Verständnis von Array-basierten dynamischen Datenstrukturen und deren Einschränkungen.
Ein Stack mit einer Kapazität von 1000 Elementen wird erstellt, und Elemente werden nacheinander von vorne nach hinten in das zugrundeliegende Array eingefügt.
- Das Problem des 'Leutering' (unnötige Speicherbelegung) entsteht, wenn Elemente nach dem Pop nicht explizit aus dem Array entfernt werden.
- Um Leutering zu vermeiden, muss das entfernte Element im Array explizit gelöscht (z.B. auf None gesetzt) werden, bevor es zurückgegeben wird.
- Das Problem des Overflows wird durch dynamisches Vergrößern des Arrays gelöst, typischerweise durch Verdopplung der Kapazität.
- Das Vergrößern des Arrays erfordert das Kopieren aller vorhandenen Elemente in ein neues, größeres Array.
- Eine naive Vergrößerung um nur eins führt zu quadratischer Laufzeit; eine Verdopplung führt zu amortisierter linearer Laufzeit.
Die korrekte Speicherverwaltung und dynamische Größenanpassung sind entscheidend für die Effizienz und Skalierbarkeit von Datenstrukturen, insbesondere bei großen Datenmengen.
Wenn ein Array voll ist, wird eine neue Kapazität geschaffen, die doppelt so groß ist, und alle alten Elemente werden in das neue Array kopiert.
- Arrays haben eine feste Größe, daher muss bei Bedarf ein neues, größeres Array erstellt und die Elemente kopiert werden.
- Eine Strategie zur Vergrößerung ist die Verdopplung der Kapazität, wenn das Array voll ist.
- Eine naive Vergrößerung um nur ein Element führt zu ineffizienten quadratischen Laufzeiten.
- Das Verkleinern des Arrays ist ebenfalls möglich, sollte aber nicht symmetrisch zur Vergrößerung erfolgen, um Angriffe (Denial of Service) zu vermeiden.
- Eine Strategie ist, das Array zu verdoppeln, wenn es voll ist, und erst zu halbieren, wenn es nur noch zu einem Viertel gefüllt ist.
Die Wahl der richtigen Strategie für dynamische Größenanpassungen beeinflusst maßgeblich die Performance und Sicherheit der Datenstruktur.
Wenn ein Array mit 10 Elementen voll ist, wird es auf 20 Elemente vergrößert, anstatt nur auf 11.
- Die amortisierte Laufzeit betrachtet die durchschnittliche Leistung über eine Sequenz von Operationen, nicht die Leistung jeder einzelnen Operation.
- Eine Verdopplungsstrategie bei der Größenanpassung führt zu einer amortisierten linearen Laufzeit für Einfügeoperationen.
- Der Speicherverbrauch eines Array-basierten Stacks liegt im schlimmsten Fall beim Vierfachen der benötigten Elemente (wegen der Wachstumsstrategie).
- Verkettete Listen bieten eine konstante Zeit für jede Operation, verbrauchen aber mehr Speicher pro Element (Overhead für Referenzen).
- Die Wahl zwischen Array und verketteter Liste hängt von den spezifischen Anforderungen an Zeit, Speicher und Implementierungskomplexität ab.
Das Verständnis der amortisierten Laufzeit und des Speicherverbrauchs hilft bei der Auswahl der optimalen Datenstruktur für eine gegebene Anwendung.
Obwohl das Kopieren von 1 Milliarde Elementen beim Verdoppeln eines Arrays teuer ist, ist diese Operation so selten, dass die durchschnittliche Einfügeoperation schnell bleibt.
- Eine Queue folgt dem First-In, First-Out (FIFO)-Prinzip.
- Für eine Queue mit einer verketteten Liste ist es am effizientesten, Elemente am Ende einzufügen (Enqueue) und am Anfang zu entfernen (Dequeue).
- Das Einfügen am Ende erfordert eine Referenz auf das letzte Element (Tail-Pointer), um nicht die gesamte Liste durchlaufen zu müssen.
- Das Entfernen am Anfang ist einfach, indem der Head-Pointer auf das nächste Element verschoben wird.
- Sonderfälle wie das Einfügen in eine leere Queue oder das Entfernen des letzten Elements erfordern eine sorgfältige Behandlung der Head- und Tail-Pointer.
Die effiziente Implementierung einer Queue ist entscheidend für Anwendungen, die eine faire Verarbeitung von Aufgaben oder Ereignissen erfordern.
Elemente werden am Ende einer verketteten Liste hinzugefügt und vom Anfang entfernt, um das FIFO-Prinzip zu gewährleisten.
- Eine Queue kann auch effizient mit einem Array implementiert werden, indem ein Ringpuffer-Konzept verwendet wird.
- Zwei Pointer, Head (Anfang) und Tail (Ende), werden verwendet, um die Positionen für Entnahme und Einfügung zu verfolgen.
- Modulo-Arithmetik wird eingesetzt, um die Pointer im Array 'umlaufen' zu lassen, wenn sie das Ende erreichen.
- Das Einfügen erfolgt am Tail, das Entfernen am Head.
- Die dynamische Größenanpassung (Verdoppeln/Halbieren) funktioniert analog zur Array-basierten Stack-Implementierung.
Die Array-basierte Queue-Implementierung (Ringpuffer) kombiniert die Effizienz von Arrays mit der FIFO-Logik von Queues und bietet eine gute Performance.
Wenn der Tail-Pointer das Ende des Arrays erreicht, springt er dank Modulo-Arithmetik zurück zum Anfang, um dort neue Elemente einzufügen.
- Stacks sind nützlich für Funktionen wie Rückgängigmachen (Undo/Redo), Browser-Verlauf (Zurück-Button) und Funktionsaufrufe (Call Stack).
- Stacks werden auch in Compilern, virtuellen Maschinen und zur Auswertung von Ausdrücken verwendet.
- Queues sind ideal für die Verwaltung von Aufgaben in der Reihenfolge ihres Eintreffens, z.B. Druckaufträge oder Aufgaben in einem Betriebssystem.
- Die Wahl zwischen Stack und Queue hängt davon ab, ob das zuletzt hinzugefügte Element zuerst verarbeitet werden soll (Stack) oder das älteste (Queue).
- Das Verständnis dieser Datenstrukturen ist grundlegend für viele fortgeschrittene Computerwissenschaftskonzepte.
Stacks und Queues sind fundamentale Bausteine in der Informatik, die in einer Vielzahl von realen Anwendungen und Systemen zum Einsatz kommen.
Wenn Sie in einem Texteditor 'Rückgängig' drücken, wird das zuletzt ausgeführte Kommando vom Stack genommen und rückgängig gemacht.
Key takeaways
- Die Implementierung von Datenstrukturen wie Stacks und Queues kann entweder auf Arrays oder verketteten Listen basieren, wobei jede Methode eigene Vor- und Nachteile in Bezug auf Zeit- und Speicherkomplexität hat.
- Dynamische Größenanpassung durch Verdopplung der Kapazität ist entscheidend für die Effizienz von Array-basierten Datenstrukturen und führt zu amortisierter linearer Laufzeit.
- Das Vermeiden von Speicherlecks ('Leutering') durch explizites Entfernen von Elementen aus dem Speicher ist wichtig für die Ressourcennutzung.
- Eine Queue folgt dem FIFO-Prinzip (First-In, First-Out), während ein Stack dem LIFO-Prinzip (Last-In, First-Out) folgt.
- Ringpuffer sind eine effiziente Methode zur Implementierung von Queues mit Arrays, die Modulo-Arithmetik zur Zirkularisierung nutzen.
- Die Wahl der richtigen Datenstruktur hängt von den spezifischen Anforderungen der Anwendung ab, insbesondere von der Reihenfolge der Verarbeitung und den Performance-Zielen.
- Grundlegende Datenstrukturen wie Stacks und Queues sind die Basis für viele komplexere Algorithmen und Systemkomponenten in der Informatik.
Key terms
StackQueueArrayVerkettete ListePushPopEnqueueDequeueFIFO (First-In, First-Out)LIFO (Last-In, First-Out)OverflowUnderflowDynamische GrößenanpassungAmortisierte LaufzeitRingpufferModulo-ArithmetikCall Stack
Test your understanding
- Was sind die Hauptunterschiede zwischen der Implementierung eines Stacks mit einem Array und mit einer verketteten Liste in Bezug auf Zeit- und Speicherkomplexität?
- Wie hilft die Verdopplungsstrategie bei der Größenanpassung eines Arrays, eine amortisierte lineare Laufzeit zu erreichen, und warum ist eine naive Vergrößerung um eins ineffizient?
- Erklären Sie das 'Leutering'-Problem bei Array-basierten Datenstrukturen und wie es behoben werden kann.
- Was ist der Unterschied zwischen dem FIFO-Prinzip einer Queue und dem LIFO-Prinzip eines Stacks, und welche Art von Problemen eignet sich jeweils am besten?
- Wie funktioniert ein Ringpuffer bei der Implementierung einer Queue mit einem Array, und welche Rolle spielt die Modulo-Arithmetik dabei?