Informatik Datenstrukturen – Stacks und Queues
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was bedeutet LIFO und bei welcher Datenstruktur gilt es? · Was bedeutet FIFO und bei …
Karten
15 KartenWas bedeutet LIFO und bei welcher Datenstruktur gilt es?
Rückseite
LIFO steht für Last In, First Out – das zuletzt eingefügte Element wird zuerst entnommen; gilt für Stacks.
Was bedeutet FIFO und bei welcher Datenstruktur gilt es?
Rückseite
FIFO steht für First In, First Out – das zuerst eingefügte Element wird zuerst entnommen; gilt für Queues.
Welche drei Kernoperationen hat ein Stack?
Rückseite
push (einfügen), pop (entfernen und zurückgeben), top/peek (oberstes Element ansehen ohne Entfernen).
Welche Kernoperationen hat eine Queue?
Rückseite
enqueue (hinten einfügen), dequeue (vorne entfernen und zurückgeben), front/peek (vorderstes Element ansehen).
Wie ist die Laufzeit von push und pop bei einem Stack (Array-Implementierung)?
Rückseite
Beide Operationen laufen in O(1) amortisiert, da nur der Top-Index geändert wird.
Wie ist die Laufzeit von enqueue und dequeue bei einer Queue (Ringpuffer-Array)?
Rückseite
Beide Operationen laufen in O(1), da nur Kopf- und End-Indizes modulo Array-Größe verschoben werden.
Was ist ein Stack-Overflow und wann tritt er auf?
Rückseite
Ein Stack-Overflow tritt auf, wenn push auf einem vollen Stack (begrenzte Array-Größe) oder bei zu tiefer Rekursion aufgerufen wird.
Was ist ein Queue-Underflow?
Rückseite
Ein Underflow tritt auf, wenn dequeue oder front auf einer leeren Queue aufgerufen wird – keine Elemente vorhanden.
Wofür nutzt der Compiler einen Stack bei Funktionsaufrufen?
Rückseite
Der Call Stack speichert Rücksprungadressen, lokale Variablen und Parameter jedes Funktionsaufrufs – LIFO entspricht der Aufruf-Rückkehr-Reihenfolge.
Nenne ein typisches Anwendungsbeispiel für Queues in Betriebssystemen.
Rückseite
Prozess-Scheduling: Ready-Queue hält lauffähige Prozesse in FIFO-Reihenfolge (z. B. Round-Robin) oder priorisiert.
Wie funktioniert die Breadth-First-Search (BFS) mit einer Queue?
Rückseite
Startknoten enqueuen, dann Schleife: Knoten dequeuen, besuchen, alle unbesuchten Nachbarn enqueuen – garantiert kürzeste Pfade in ungewichteten Graphen.
Wie prüft man mit einem Stack, ob Klammern in einem Ausdruck balanciert sind?
Rückseite
Öffnende Klammern pushen, bei schließender Klammer poppen und Typ vergleichen – am Ende muss Stack leer sein.
Was ist eine Deque (Double-Ended Queue)?
Rückseite
Eine Queue, die Einfügen und Entfernen an beiden Enden in O(1) erlaubt – vereint Stack- und Queue-Eigenschaften.
Wann wählt man einen Stack statt einer Queue (Entscheidungskriterium)?
Rückseite
Stack bei LIFO-Bedarf: Rekursionssimulation, Backtracking, Auswertungen (z. B. Postfix), Undo-Funktionen.
Wann wählt man eine Queue statt eines Stacks (Entscheidungskriterium)?
Rückseite
Queue bei FIFO-Bedarf: Pufferung, Scheduling, BFS, Producer-Consumer-Muster, Anfrageverarbeitung in Reihenfolge des Eintreffens.