Schlange: Unterschied zwischen den Versionen
Die Seite wurde neu angelegt: „== Einführung == In der Informatik bezeichnet eine '''Warteschlange''' oder '''Schlange''' (englisch ''Queue'') eine grundlegende und häufig eingesetzte dynamische Datenstruktur. Sie dient der geordneten Zwischenspeicherung von Datenobjekten, bevor diese systematisch weiterverarbeitet werden. Warteschlangen verwalten beliebige Objekte nach dem strengen '''FIFO-Prinzip''' (''First-In-First-Out''). Das bedeutet: Das Element, welches zuerst in die Datens…“ |
Keine Bearbeitungszusammenfassung |
||
| Zeile 113: | Zeile 113: | ||
== Laufzeitanalyse (Komplexität) == | == Laufzeitanalyse (Komplexität) == | ||
Warteschlangen lassen sich in der Praxis äußerst effizient über Arrays mit Ringpuffer-Logik oder über einfach verkettete Listen implementieren. Eine Zeigerstruktur, die stets den Anfang (Front) und das Ende (Tail) speichert, garantiert hochperformante Speicher- und Lesezugriffe. Für die oben genannten Methoden ergibt sich gemäß der [[ | Warteschlangen lassen sich in der Praxis äußerst effizient über Arrays mit Ringpuffer-Logik oder über einfach verkettete Listen implementieren. Eine Zeigerstruktur, die stets den Anfang (Front) und das Ende (Tail) speichert, garantiert hochperformante Speicher- und Lesezugriffe. Für die oben genannten Methoden ergibt sich gemäß der [[O-Notation|O-Notation]] folgende Laufzeitkomplexität: | ||
{| class="wikitable" | {| class="wikitable" | ||