Stos (stack)

Słownik kwalifikacji INF.04 - Projektowanie, programowanie i testowanie aplikacji

Co to jest stos?

Stos (stack) to liniowa struktura danych, w której element dodany jako ostatni jest zdejmowany jako pierwszy. Działa według zasady LIFO (Last In, First Out) — „ostatni wszedł, pierwszy wyszedł”.

Podstawowe operacje

  • push — dodanie elementu na wierzch stosu,
  • pop — pobranie i usunięcie elementu z wierzchu stosu,
  • peek / top — podejrzenie elementu z wierzchu bez usuwania,
  • isEmpty — sprawdzenie, czy stos jest pusty.

Przykład działania

Jeśli dodamy kolejno elementy:

  1. A
  2. B
  3. C

To jako pierwszy zostanie pobrany element C, ponieważ został dodany ostatni.

push(A)
push(B)
push(C)
pop() -> C
pop() -> B
pop() -> A

Zastosowania stosu

Stos jest często używany w programowaniu, między innymi do:

  • obsługi wywołań funkcji w pamięci programu,
  • cofania operacji, np. Undo,
  • sprawdzania poprawności nawiasów,
  • przetwarzania wyrażeń matematycznych,
  • algorytmów przeszukiwania, np. DFS.

Najważniejsze do zapamiętania

Jeżeli pytanie mówi o dostępie do ostatnio dodanego elementu w pierwszej kolejności, chodzi o stos. Kluczowe hasło egzaminacyjne to LIFO.