Implementacja stosu (LIFO) z operacjami push, pop i peek. Zastosowanie: ONP, cofanie operacji.
Stos to liniowa struktura danych działająca na zasadzie LIFO (Last In, First Out) – element włożony jako ostatni zostaje pobrany jako pierwszy.
Kluczowa intuicja: cała akcja dzieje się na jednym końcu – na wierzchu stosu. Nie mamy dostępu do elementów w środku ani na dnie; zarówno dokładanie, jak i zdejmowanie odbywa się wyłącznie na szczycie. To właśnie ten jeden punkt styku sprawia, że stos jest tak prosty i szybki w działaniu.
Analogia: stos talerzy w szafce – bierzemy zawsze ten z góry, a nowy talerz kładziemy na samej górze. Nie da się (rozsądnie) wyciągnąć talerza ze środka stosu bez zdjęcia wszystkiego, co leży nad nim.
Podstawowe operacje:
push(x) – kładzie element x na wierzch stosu.
pop() – zdejmuje i zwraca element z wierzchu.
top() (lub peek()) – sprawdza wartość elementu na wierzchu, nie zdejmując go.
pusty() – sprawdza czy stos nie zawiera elementów.
size() – zwraca liczbę elementów aktualnie znajdujących się na stosie.
W Pythonie: nie ma osobnego typu "stos" – wystarczy zwykła lista, która zachowuje się jak stos: append() działa jak push, a pop() zdejmuje ostatni element, czyli wierzch. Operacje zapisujemy po prostu jako funkcje działające na tej liście.
Przykład z życia – historia przeglądarki na dwóch stosach. Przycisk „wstecz" i „naprzód" można zbudować z dwóch stosów: jednego dla stron, do których cofamy, i drugiego dla tych, do których idziemy naprzód. Gdy odwiedzamy nową stronę, bieżącą wrzucamy na stos „wstecz", ustawiamy nową jako bieżącą i czyścimy stos „naprzód" (nowa gałąź historii unieważnia poprzednie „naprzód"). Gdy klikamy „wstecz", bieżącą wrzucamy na stos „naprzód", zdejmujemy szczyt stosu „wstecz" i to on staje się nową bieżącą stroną. „Naprzód" działa odwrotnie – zdejmujemy ze stosu „naprzód", a bieżącą odkładamy na „wstecz". Każdy z tych ruchów to tylko kilka operacji na szczytach dwóch stosów – bez przeszukiwania całej historii.
Algorytmy wykorzystujące stos:
ONP – odwrotna notacja polska – obliczanie wyrażeń arytmetycznych: na stos odkładamy liczby, a przy działaniu zdejmujemy z niego argumenty.
Sprawdzanie poprawności nawiasów – każdy nawias otwierający odkładamy na stos, a zamykający zdejmuje pasujący mu nawias z wierzchu.
Algorytmy grafowe – przeszukiwanie w głąb (DFS).
Odwracanie struktur – np. sprawdzanie palindromów.
Stos wywołań funkcji – to nie my budujemy ten stos, tylko sam program: każde wywołanie funkcji odkłada na nim swoją ramkę, a powrót ją zdejmuje. Dlatego stos stoi za każdą rekurencją – widać to w ciągu Fibonacciego, a także w sortowaniu szybkim i sortowaniu przez scalanie, gdzie głębokość tego stosu wprost przekłada się na złożoność pamięciową.
Odkładaj i zdejmuj elementy ze szczytu stosu (LIFO). Zwróć uwagę, że zawsze działasz tylko na jednym końcu.
Dodaj kilka elementów i obserwuj, jak zmienia się struktura.
// stos opieramy na liście dynamicznej stos ← pusta lista funkcja push(x): // dodajemy x na koniec listy = wierzch stosu dodaj x na koniec stos funkcja pop(): jeżeli pusty(): zwróć błąd x ← stos[ostatni indeks] usuń ostatni element ze stos zwróć x funkcja top(): jeżeli pusty(): zwróć błąd zwróć stos[ostatni indeks] funkcja pusty(): zwróć długość(stos) = 0
# Stos to zwykła lista – operacje zapisujemy jako funkcje,
# którym przekazujemy tę listę w argumencie.
def pusty(stos):
return len(stos) == 0
def push(stos, x):
# dodajemy na koniec listy = na wierzch stosu
stos.append(x)
def pop(stos):
if pusty(stos):
return None
# usuwamy i zwracamy ostatni element = wierzch
return stos.pop()
def top(stos):
if pusty(stos):
return None
return stos[-1]
# Przykład użycia
stos = []
push(stos, 1)
push(stos, 2)
push(stos, 3)
print(stos)
# Wynik: [1, 2, 3]
print(pop(stos))
# Wynik: 3
print(top(stos))
# Wynik: 2
print(pusty(stos))
# Wynik: FalseO(1)O(1)O(1)Wszystkie podstawowe operacje na stosie działają w czasie stałym O(1), ponieważ dotykamy zawsze tylko jednego miejsca – wierzchu. Operacje push(x) i pop() niczego nie przeszukują ani nie przesuwają – po prostu dokładają element na końcu albo zdejmują ostatni i aktualizują wskaźnik szczytu. Dzięki temu wykonują tę samą, z góry określoną liczbę kroków niezależnie od tego, czy na stosie leżą 3 czy 3 miliony elementów.
Podobnie top() odczytuje wartość ze szczytu, a pusty() i size() sprawdzają jedynie zapamiętaną liczbę elementów – wszystkie w czasie O(1). Żadna z tych operacji nie zależy od rozmiaru stosu.
Pamięć rośnie liniowo z liczbą przechowywanych elementów, więc złożoność pamięciowa to O(n), gdzie n to liczba elementów aktualnie znajdujących się na stosie.
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: