Co to jest stos LIFO?
Stos to liniowa struktura danych, w której elementy są przetwarzane według zasady LIFO (Last In, First Out), czyli: ostatni dodany element jest zdejmowany jako pierwszy.
Najprostsze skojarzenie to stos talerzy: talerz położony na górze zostanie zdjęty jako pierwszy.
Podstawowe operacje na stosie
- push — dodanie elementu na szczyt stosu,
- pop — zdjęcie elementu ze szczytu stosu,
- peek / top — odczyt elementu ze szczytu bez usuwania,
- isEmpty — sprawdzenie, czy stos jest pusty.
Kiedy stos jest lepszy niż lista?
Stos warto zastosować wtedy, gdy dane mają być obsługiwane w odwrotnej kolejności niż zostały dodane. Nie interesuje nas wtedy swobodny dostęp do dowolnego elementu, tylko szybkie dodawanie i usuwanie z jednego końca struktury.
Typowe zastosowania stosu:
- cofanie operacji, np.
Undo, - obsługa wywołań funkcji w programie,
- sprawdzanie poprawności nawiasów,
- odwracanie kolejności danych,
- algorytmy przeszukiwania, np. DFS.
Przykład w C
Stack<string> stos = new Stack<string>();
stos.Push("A");
stos.Push("B");
stos.Push("C");
Console.WriteLine(stos.Pop()); // C
Console.WriteLine(stos.Pop()); // B
Element C został dodany jako ostatni, ale usunięty jako pierwszy. To właśnie zasada LIFO.
Najważniejsze do zapamiętania
Stos wybieramy wtedy, gdy kolejność przetwarzania danych ma być odwrócona względem kolejności ich dodawania.