Implementacja stosu - PY_I_R_W13B_M05 Dynamiczne struktury danych. Implementacja

Rc3eHnGputwzz

W wątku Wybrane algorytmy i ich kodowanie w języku Python zostały opisane wybrane dynamiczne struktury danych takie jak stos, kolejka lista jednokierunkowa. W tym materiale poznasz sposoby ich implementacji.

Jak zaimplementować stos w Pythonie za pomocą listy

Stos (ang. stack) to jedna z najprostszych, a zarazem najważniejszych struktur danych. Opiera się na zasadzie LIFO – Last In, First Out, czyli “ostatni wchodzi, pierwszy wychodzi”.
Stosy pojawiają się w wielu miejscach:

w działaniu funkcji i rekurencji,
przy parsowaniu wyrażeń,
w algorytmach przeszukiwania (DFS),
w obsłudze cofania akcji (undo),
w symulacjach i grach.

W Pythonie stos można stworzyć bardzo łatwo, ponieważ lista (list) zawiera operacje idealnie nadające się do jego obsługi.

Podstawowe operacje stosu

Każdy stos powinien umożliwiać:

push(x) – dodanie elementu na szczyt stosu,
pop() – zdjęcie elementu ze szczytu,
peek() / top() – podejrzenie elementu na szczycie,
is_empty() – sprawdzenie czy stos jest pusty.

Pythonowe listy naturalnie obsługują te operacje dzięki metodom append() i pop().

stos = []

# push
stos.append(10)
stos.append(20)
stos.append(30)

# pop
x = stos.pop()     # zdejmie 30
print("Zdjęto:", x)

# peek (bez usuwania)
print("Na szczycie:", stack[-1])

# is_empty
print("Czy pusty?", len(stack) == 0)

Dynamiczne struktury danych

Dla zainteresowanych: stos jako klasa

PY_I_R_W13B_M05 Dynamiczne struktury danych. Implementacja

Jak zaimplementować stos w Pythonie za pomocą listy

Podstawowe operacje stosu