Was genau unterscheidet Listen von Queues und stacks in Python?
Generell habe ich die Funktionsweise und die Anwendungsgebiete von Listen noch nicht so richtig verstanden. Ich würd mich sehr über Hilfe freuen. Danke im Voraus!
3 Antworten
Das ist eine Queue (Schlange):
Quelle: ACBahn, Warteschlange Eisdiele, CC BY 3.0
Eine Queue basiert (nach klassischer Definition) auf dem FIFO-Prinzip (First In – First Out). Das sieht man schön an obiger Warteschlange: Die erste Person, die in der Schlange steht, bekommt auch zuerst ihr Eis. Bei einer Queue existieren folgende Operationen:
- Anstellen eines neuen Elements an das Ende der Queue
- Abrufen des vordersten Elements („Kopf“) der Queue
- Entfernen des vordersten Elements der Queue
Die Elemente in der Mitte spielen keine Rolle und können nicht abgerufen werden. Der Verkäufer kann immer nur den vordersten Kunden bedienen, nicht irgendeinen anderen.
Stack (Stapel)Das sind Stacks (Stapel):
Quelle: congerdesign, plate, CC0
Ein Stack basiert auf dem LIFO-Prinzip (Last In – First Out). Das sieht man gut an einem Tellerstapel: Der Teller, den du als letztes auf den Stapel gelegt hast, ist auch derjenige, den du zuerst wieder nimmst. Bei einem Stack existieren folgende Operationen:
- Legen eines neuen Elements auf den Stapel
- Abrufen des obersten Elements des Stapels
- Entfernen des obersten Elements des Stapels
Die Elemente in der Mitte spielen keine Rolle und können nicht abgerufen werden. Du kannst immer nur den obersten Teller entnehmen, nicht irgendeinen. Dazu musst du erst alle Teller darüber entfernen.
ListeDas ist eine Liste:
Quelle: Prattflora, Ice cube tray, CC BY-SA 3.0
Eine Liste basiert weder auf dem FIFO- noch auf dem LIFO-Prinzip, sondern ist wesentlich flexibler. Das sieht man an obiger Eiswürfelbox: Es kann jederzeit jeder Eiswürfel entnommen werden bzw. ein Eiswürfel an beliebiger Stelle eingesetzt werden. Bei einer Liste existieren folgende Operationen:
- Einfügen eines Elements am Ende der Liste oder an einer beliebigen Position
- Abrufen eines Elements an einer beliebigen Position
- Entfernen eines Elements an einer beliebigen Position
Es kommt immer auf den Kontext an. Eine Queue ist sinnvoll, wenn man etwas Warteschlangen-ähnliches (FIFO) hat. Ein Stack ergibt Sinn, falls immer nur das oberste Element interessant ist (LIFO). Ansonsten empfiehlt sich eine Liste, falls größere Flexibilität erforderlich ist.
List, Queue und Stack sind dynamische Datenstrukturen.
Bei Listen kannst Du auf jedes belibige Element der LIste zugreifen. Stacks sind Stapel und zeichnen sich durch das LIFO Prinzip aus (Last In First Out). Beim Stack kannst Du immer nur auf das oberste Element zugreifen. Queues sind Schlangen und arbeiten nach dem FIFO Prinzip (First In First Out). Das Element, das Du als erstes in die Queue packst, auf das greifst Du auch als erstes zu.
List (dt. Liste) ist optimiert auf feste Längen. Queues im Gegenzug auf variable Längen. Weißt du also nicht, wie viele Elemente du speichern möchtest, dann solltest du eher eine Queue verwenden.
Stacks sind ein komplett anderer Ansatz.
Queue und List arbeiten beide FIFO (First in first out, also wie z.B. eine Supermarktschlange) während der Stack (Stapel) LIFO (Last in first out, also wie z.B. ein Bücherstapel) arbeitet.