Struktury dynamiczne: stos, kolejka, lista oraz ONP

Stos (ang. stack) działa na zasadzie LIFO (Last In, First Out) — ostatni element włożony jest pierwszym zdejmowanym. Myśl o stosie talerzy: bierzesz zawsze z wierzchu.

class Stos: def __init__(self): self.elementy = [] def push(self, x): self.elementy.append(x) def pop(self): return self.elementy.pop() def podglad(self): return self.elementy[-1] def czy_pusty(self): return len(self.elementy) == 0

W Pythonie zwykła lista działa jak stos od razu (append() = push, pop() = pop) — obie operacje są O(1).

2. Kolejka (FIFO)

Kolejka działa na zasadzie FIFO (First In, First Out) — tak jak kolejka w sklepie: kto pierwszy stanął, pierwszy zostanie obsłużony. Do wydajnej implementacji używamy collections.deque zamiast zwykłej listy (usuwanie z początku listy jest O(n), a z deque jest O(1)).

from collections import deque kolejka = deque() kolejka.append("Anna") # dodanie na koniec kolejka.append("Bartek") pierwszy = kolejka.popleft() # zdjęcie z początku -> "Anna"

3. Lista jednokierunkowa

W przeciwieństwie do tablicy, elementy listy nie leżą obok siebie w pamięci — każdy węzeł przechowuje wartość oraz wskaźnik (referencję) do następnego węzła. Dodawanie na początku jest O(1), ale dostęp do n-tego elementu wymaga przejścia od początku — O(n).

class Wezel: def __init__(self, wartosc): self.wartosc = wartosc self.nastepny = None class ListaJednokierunkowa: def __init__(self): self.glowa = None def dodaj_na_poczatek(self, wartosc): nowy = Wezel(wartosc) nowy.nastepny = self.glowa self.glowa = nowy def wypisz(self): biezacy = self.glowa while biezacy: print(biezacy.wartosc) biezacy = biezacy.nastepny

4. Odwrotna Notacja Polska (ONP)

ONP (zapis postfiksowy) zapisuje operatory po argumentach, np. wyrażenie (3 + 4) * 2 w ONP to 3 4 + 2 *. Ten zapis pozwala obliczyć wynik bez nawiasów i bez znajomości priorytetów operatorów, wykorzystując stos: liczby odkładamy na stos, a napotykając operator — zdejmujemy dwa górne elementy, wykonujemy działanie i wynik odkładamy z powrotem.

def oblicz_onp(wyrazenie): stos = [] for token in wyrazenie.split(): if token in "+-*/": b = stos.pop() a = stos.pop() if token == "+": stos.append(a + b) elif token == "-": stos.append(a - b) elif token == "*": stos.append(a * b) elif token == "/": stos.append(a / b) else: stos.append(float(token)) return stos.pop() # oblicz_onp("3 4 + 2 *") -> 14.0

5. Ćwiczenia praktyczne

Ćwiczenie 1 — sprawdzanie nawiasów

Wykorzystując klasę Stos, napisz funkcję sprawdzającą, czy w tekście nawiasy są poprawnie domknięte i zagnieżdżone (np. "(a+[b*c])" jest poprawne, a "(a+[b)]" nie).

Ćwiczenie 2 — zamiana na ONP ręcznie

Zapisz w notacji ONP wyrażenie (5 - 2) * (3 + 1), a następnie zweryfikuj wynik funkcją oblicz_onp.

ONP: 5 2 - 3 1 + * → wynik: (5-2) × (3+1) = 3 × 4 = 12

Sprawdź wiedzę

1. Stos działa na zasadzie:

FIFO LIFO Losowego dostępu

2. Która struktura Pythona jest zalecana do efektywnej implementacji kolejki?

Zwykła lista collections.deque Krotka (tuple)

3. Wyrażenie ONP "3 4 +" oznacza:

3 + 4 3 - 4 4 - 3

1. Stos (LIFO)