INF.04Algorytmika i Struktury Danych
Stos (LIFO) i Kolejka (FIFO)
Liniowe struktury danych: Stos działa według zasady LIFO (ostatni wchodzi, pierwszy wychodzi), a Kolejka według FIFO (pierwszy wchodzi, pierwszy wychodzi).
1. Stos (Stack – LIFO: Last In, First Out)
- Zasada: Ostatni dodany element jest usuwany jako pierwszy (jak stos talerzy).
- Operacje:
push(x): Dodaje element na wierzchołek stosu (O(1)).pop(): Zdejmuje i zwraca element z wierzchołka (O(1)).peek() / top(): Podgląda wierzchołek bez usuwania.
- Zastosowania: Stos wywołań funkcji (Call Stack), operacje Cofnij (
Ctrl+Z), ewaluacja wyrażeń ONP, przeszukiwanie DFS.
2. Kolejka (Queue – FIFO: First In, First Out)
- Zasada: Pierwszy dodany element jest usuwany jako pierwszy (jak kolejka w sklepie).
- Operacje:
enqueue(x) / push(x): Dodanie elementu na koniec kolejki (O(1)).dequeue() / pop(): Usunięcie elementu z początku kolejki (O(1)).
- Zastosowania: Bufor wydruku (spooler), obsługa żądań HTTP w serwerach, kolejka zadań, przeszukiwanie BFS.
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Stos (LIFO) i Kolejka (FIFO) lub rozpocznij trening.