Stos (struktura danych) — definicja, zasada LIFO, operacje push/pop

Stos — praktyczna struktura danych (LIFO). Dowiedz się o zasadzie działania, operacjach push/pop oraz praktycznych zastosowaniach w programowaniu.

Stos jest jedną z najważniejszych struktur danych w informatyce. Aby zrozumieć jak działa stos, pomyśl o talii kart do gry, która jest zakryta. Możemy tylko łatwo uzyskać dostęp do karty, która jest na wierzchu. Kiedy chcemy spojrzeć na wierzchnią kartę, możemy zrobić dwie rzeczy: możemy ją podejrzeć, ale pozostawić na stosie, lub możemy ją odczepić. Kiedy odrywamy górny obiekt, zdejmujemy go ze stosu. Jeśli chcemy dodać kolejną kartę na wierzch stosu, to ją przesuwamy.

Stos jest nazywany kolekcją typu LIFO (last-in-first-out). Oznacza to, że ostatnia rzecz, którą dodaliśmy (wepchnęliśmy) jest pierwszą rzeczą, która zostaje wyciągnięta (wysunięta). Jeśli ostatnią kartą, którą położyliśmy na naszym stosie kart był as, to pierwszą kartą, którą ściągnęliśmy z wierzchu jest ten sam as.

Podstawowe operacje

• push(x) — dodać element x na wierzch stosu.
• pop() — usunąć i zwrócić element z wierzchu stosu. Jeśli stos jest pusty, zwykle sygnalizuje się błąd (underflow) lub zwraca wartość specjalną.
• peek() (lub top()) — zwrócić element z wierzchu bez usuwania go.
• isEmpty() — sprawdzić, czy stos jest pusty.
• size() — (opcjonalnie) zwrócić liczbę elementów na stosie.

Prosty pseudokod

Przykładowe operacje dla stosu reprezentowanego jako tablica z indeksem top:

push(x):

if top == capacity - 1 then (overflow) or resize()

top = top + 1; A[top] = x

pop():

if top == -1 then (underflow) or error

x = A[top]; top = top - 1; return x

peek():

if top == -1 then error else return A[top]

Implementacje

• Tablica (statyczna lub dynamiczna) — prosta, szybka (operacje w czasie stałym O(1)), wymaga zarządzania rozmiarem (możliwość overflow lub automatyczne powiększanie).
• Lista jednokierunkowa — każdy push tworzy nowy węzeł na początku listy, pop usuwa pierwszy węzeł. Nie ma ograniczenia rozmiaru (poza pamięcią), również operacje są O(1).

Złożoność obliczeniowa i pamięciowa

• Czas: typowo push, pop i peek działają w czasie O(1).
• Pamięć: O(n) dla n przechowywanych elementów. Implementacja tablicowa może rezerwować dodatkową pamięć (gdy używamy dynamicznych tablic i strategii powiększania), implementacja listowa wymaga pamięci dodatkowej na wskaźniki.

Błędy i ograniczenia

• Underflow — próba wykonania pop() lub peek() na pustym stosie.
• Overflow — w implementacji tablicowej przy braku mechanizmu powiększania, gdy brak miejsca na nowe elementy. Można temu zaradzić dynamicznym alokowaniem większej tablicy.
• W środowiskach wielowątkowych stos może wymagać synchronizacji (mutex, atomowe operacje) aby uniknąć warunków wyścigu.

Zastosowania

• Stos wywołań funkcji (call stack) w większości języków — przechowywanie adresów powrotu i zmiennych lokalnych.
• Algorytmy przeszukiwania grafu (DFS) — stos wykorzystywany jest zamiast rekurencji lub razem z nią.
• Parsowanie wyrażeń i sprawdzanie poprawności nawiasów.
• Funkcje cofania/undo w edytorach oraz mechanizmy "wstecz" w przeglądarkach (back button).
• Algorytmy obliczania notacji odwrotnej (RPN) oraz konwersji infiksowej do postfiksowej.

Warianty i rozszerzenia

• Stos ograniczony — ze stałą maksymalną pojemnością (np. wbudowane bufory).
• Dwustronny stos (deque) — struktura pozwalająca na operacje na obu końcach; może działać jako stos lub kolejka.
• Stos persistentny — wersjonowana struktura zachowująca dostęp do starych wersji po modyfikacjach (przydatne w programowaniu funkcyjnym).

Stos to prosta, ale niezwykle użyteczna struktura danych — dzięki swoim właściwościom LIFO znajduje zastosowanie w wielu miejscach programowania i algorytmiki. Zrozumienie jego działania oraz prostych operacji push/pop jest podstawą pracy z bardziej złożonymi strukturami i algorytmami.

Szukaj według litery