Co to jest stos?
Stos to liniowa struktura danych działająca według zasady LIFO (Last In, First Out), czyli „ostatni wszedł, pierwszy wyszedł”. Oznacza to, że element dodany jako ostatni zostanie usunięty jako pierwszy.
Stos można porównać do stosu talerzy: nowy talerz kładziemy na górze, a zdejmujemy również z góry.
Podstawowe operacje stosu
Najczęściej stos obsługuje następujące metody:
push(element)— dodaje element na szczyt stosu,pop()— usuwa i zwykle zwraca element ze szczytu stosu,peek()— zwraca element ze szczytu bez usuwania,isEmpty()— sprawdza, czy stos jest pusty.
Kluczowe jest to, że pop() usuwa ostatnio dodany element, a nie pierwszy dodany.
Przykład działania
push(10) // stos: 10
push(20) // stos: 10, 20
push(30) // stos: 10, 20, 30
pop() // usuwa 30
peek() // zwraca 20, ale go nie usuwa
Element 30 został dodany jako ostatni, więc zostaje usunięty jako pierwszy.
Zastosowania stosu
Stos jest wykorzystywany m.in. do:
- obsługi wywołań funkcji w programie,
- cofania operacji, np.
Undo, - sprawdzania poprawności nawiasów,
- odwracania kolejności danych,
- obliczania wyrażeń w notacji ONP.
Stos a kolejka
Stos działa według zasady LIFO, natomiast kolejka według zasady FIFO (First In, First Out). W kolejce pierwszy dodany element jest usuwany jako pierwszy, np. jak osoby stojące w kolejce do kasy.