Zrozumienie implementacji stosu w Pythonie

W świecie programowania struktury danych stanowią fundament. Umożliwiają one efektywne porządkowanie informacji, co przekłada się na wydajność działania programów. Stos, będący jedną z podstawowych struktur, jest doskonałym przykładem prostoty i użyteczności.

Zapraszam do zgłębienia tajników stosu i jego implementacji w języku Python.

Czym jest stos?

Stos, w swojej koncepcji, przypomina układ książek czy krzeseł ułożonych jedno na drugim. Jego działanie opiera się na zasadzie „ostatnie weszło, pierwsze wyszło” (LIFO – Last In, First Out). Jest to model niezwykle prosty, a jednocześnie szeroko stosowany. Zobrazujmy to na przykładzie z życia codziennego.

Wyobraźmy sobie stos książek, w którym każda kolejna książka kładziona jest na wierzchu.

Aby dostać się do trzeciej książki od góry, musimy najpierw usunąć dwie książki, które zostały dodane później. Oznacza to, że książka, która trafiła na stos jako ostatnia, opuści go jako pierwsza. W informatyce, stos struktury danych działa na dokładnie tej samej zasadzie – LIFO.

Podstawowe operacje na stosie

Operacje na stosie sprowadzają się głównie do dwóch fundamentalnych działań:

1. push(dane)

Ta operacja polega na umieszczeniu nowych danych na szczycie stosu.

2. pop()

Operacja ta usuwa element znajdujący się na wierzchu stosu, czyli ten, który został dodany jako ostatni.

Poniższe ilustracje prezentują graficznie procesy push i pop.

Dla lepszej obsługi stosu, przydatne są również dodatkowe funkcje pomocnicze.

Przyjrzyjmy się im.

peek()

Ta funkcja zwraca wartość elementu znajdującego się na wierzchu stosu, nie usuwając go.

is_empty()

Funkcja ta pozwala sprawdzić, czy stos jest aktualnie pusty.

Po omówieniu teoretycznych aspektów, przejdźmy do praktycznej implementacji stosu.

Zakładając, że masz już zainstalowanego Pythona, możemy przejść dalej. Jeśli nie, możesz skorzystać z kompilatora online.

Implementacja stosu w Pythonie

Implementacja stosu nie należy do najtrudniejszych zadań. Python oferuje kilka sposobów na stworzenie tej struktury.

Omówmy je po kolei.

# 1. Lista jako podstawa stosu

Wykorzystamy listę do zbudowania stosu w ramach klasy. Spójrzmy na kolejne etapy implementacji.

Krok 1: Tworzymy klasę o nazwie Stack.

class Stack:
    pass

Krok 2: Dane będziemy przechowywać w liście. Dodajemy pustą listę jako atrybut `elements` w klasie Stack.

class Stack:
    def __init__(self):
        self.elements = []

Krok 3: Metoda push umożliwi dodawanie elementów na stos. Przyjmuje ona dane jako argument i dołącza je do listy elementów.

class Stack:
    def __init__(self):
        self.elements = []

    def push(self, data):
        self.elements.append(data)
        return data

Krok 4: Analogicznie, metoda pop usunie element ze szczytu stosu, wykorzystując metodę pop listy.

class Stack:
    ## ...
    def pop(self):
        return self.elements.pop()

Zakończyliśmy implementację podstawowych operacji na stosie. Teraz dodamy metody pomocnicze, które pozwolą na uzyskanie dodatkowych informacji o stosie.

Krok 5: Aby uzyskać element ze szczytu stosu, skorzystamy z ujemnego indeksu listy. `elements[-1]` zwróci ostatni element, który w naszym przypadku jest szczytem stosu.

class Stack:
    ## ...

    def peek(self):
        return self.elements[-1]

Krok 6: Stos jest pusty, gdy długość listy `elements` wynosi 0. Napiszemy metodę `is_empty`, która to sprawdzi.

class Stack:
    ## ...
    def is_empty(self):
        return len(self.elements) == 0

W ten sposób zakończyliśmy implementację stosu za pomocą listy.

Chwileczkę, ale jak w ogóle użyć tej klasy?

Spokojnie, zobaczmy, jak to zrobić. Musimy utworzyć obiekt klasy Stack. To nic trudnego, zaraz to zrobimy.

class Stack:
    ## ...

if __name__ == '__main__':
    stack = Stack()

Mamy już obiekt stosu, gotowy do użycia. Sprawdźmy, jak działają operacje na nim, wykonując następujące kroki:

• Sprawdzamy, czy stos jest pusty, używając metody `is_empty`. Powinna zwrócić wartość True.
• Wstawiamy elementy 1, 2, 3, 4, 5 na stos, używając metody `push`.
• Metoda `is_empty` powinna teraz zwrócić wartość False.
• Wyświetlamy element ze szczytu stosu, korzystając z metody `peek`.
• Usuwamy element ze stosu, wykorzystując metodę `pop`.
• Sprawdzamy element ze szczytu za pomocą `peek`. Powinien zwrócić 4.
• Usuwamy wszystkie pozostałe elementy ze stosu.
• Ostatnie wywołanie metody `is_empty` powinno zwrócić wartość True.

Jeśli nasza implementacja przejdzie pomyślnie wszystkie powyższe testy, to nasz stos działa poprawnie. Spróbuj napisać kod, który zrealizuje te kroki.

Masz już gotowy kod? Jeśli nie, bez obaw, sprawdź poniższe rozwiązanie.

class Stack:
    def __init__(self):
        self.elements = []

    def push(self, data):
        self.elements.append(data)
        return data

    def pop(self):
        return self.elements.pop()

    def peek(self):
        return self.elements[-1]

    def is_empty(self):
        return len(self.elements) == 0

if __name__ == '__main__':
    stack = Stack()

    ## checking is_empty method -> true
    print(stack.is_empty())

    ## pushing the elements
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    ## again checking is_empty method -> false
    print(stack.is_empty())

    ## printing the topmost element of the stack -> 5
    print(stack.peek())

    ## popping the topmost element -> 5
    stack.pop()

    ## checking the topmost element using peek method -> 4
    print(stack.peek())

    ## popping all the elements
    stack.pop()
    stack.pop()
    stack.pop()
    stack.pop()

    ## checking the is_empty method for the last time -> true
    print(stack.is_empty())

Udało się! Stworzyliśmy od podstaw implementację stosu, używając listy. Uruchomienie powyższego kodu powinno dać następujący wynik:

True
False
5
4
True

Można użyć listy bezpośrednio jako stosu, jednak nasza implementacja pozwala lepiej zrozumieć, jak działa stos, co jest przydatne w innych językach programowania.

Możesz także sprawdzić te artykuły o listach.

Teraz przejdźmy do wbudowanego modułu `deque` z modułu `collections`, który również może posłużyć jako stos.

#2. deque z modułu collections

Kolejka dwustronna `deque` pozwala na dodawanie i usuwanie elementów z obu końców, co czyni ją elastyczną strukturą, którą możemy dostosować do działania jak stos. Poprzez odpowiednie użycie jej metod możemy uzyskać zachowanie LIFO.

Implementacja `deque` opiera się na liście podwójnie wiązanej, co zapewnia stałą wydajność przy dodawaniu i usuwaniu elementów. Dostęp do elementów w środku takiej listy jest jednak czasochłonny (O(n)), co nie jest problemem w przypadku stosu, gdzie dostęp ograniczony jest do wierzchołka.

Zanim przejdziemy do implementacji stosu przy użyciu `deque`, zobaczmy, jakie metody będą nam potrzebne:

• `append(data)` – służy do wstawiania danych na wierzch stosu
• `pop()` – usuwa element z wierzchu stosu

Nie ma bezpośrednich odpowiedników dla metod `peek` i `is_empty`. Zamiast `peek` możemy wyświetlić cały stos, a do sprawdzenia, czy stos jest pusty, możemy użyć funkcji `len`.

Zobaczmy implementację stosu przy użyciu `deque` z modułu `collections`.

from collections import deque

## creating deque object
stack = deque()

## checking whether stack is empty or not -> true
print(len(stack) == 0)

## pushing the elements
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

## again checking whether stack is empty or not -> false
print(len(stack) == 0)

## printing the stack
print(stack)

## popping the topmost element -> 5
stack.pop()

## printing the stack
print(stack)

## popping all the elements
stack.pop()
stack.pop()
stack.pop()
stack.pop()

## checking the whether stack is empty or not for the last time -> true
print(len(stack) == 0)

To już wszystko. Nauczyliśmy się, jak zaimplementować stos za pomocą `deque` z modułu `collections`. Uruchomienie powyższego programu powinno dać następujący wynik:

True
False
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
True

Do tej pory widzieliśmy dwie metody implementacji stosu. Czy istnieją jeszcze jakieś inne? Tak! Poznajmy ostatni sposób implementacji stosu w tym poradniku.

#3. LifoQueue

Nazwa `LifoQueue` sama w sobie wskazuje, że działa ona zgodnie z zasadą LIFO, czyli dokładnie tak, jak stos. Pochodzi ona z wbudowanego modułu `queue` i oferuje przydatne metody do implementacji stosu. Oto one:

• `put(data)` – dodaje dane do kolejki (stosu)
• `get()` – usuwa i zwraca element z wierzchu stosu
• `empty()` – sprawdza, czy stos jest pusty
• `qsize()` – zwraca liczbę elementów w stosie

Spójrzmy na implementację stosu przy użyciu `LifoQueue` z modułu `queue`.

from queue import LifoQueue

## creating LifoQueue object
stack = LifoQueue()

## checking whether stack is empty or not -> true
print(stack.empty())

## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)

## again checking whether stack is empty or not -> false
print(stack.empty())

## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())

## checking the stack size
print("Size", stack.qsize())

print(stack.get())
print(stack.get())

## checking the whether stack is empty or not for the last time -> true
print(stack.empty())

Powyższy program powinien zwrócić następujący wynik:

True
False
5
4
3
Size 2
2
1
True

Zastosowania stosu

Posiadając już solidną wiedzę na temat stosów, możemy przejść do ich praktycznego zastosowania. Spójrzmy na problem, który rozwiążemy z wykorzystaniem tej struktury.

Mając dane wyrażenie, napisz program, który sprawdzi, czy nawiasy okrągłe, klamrowe i kwadratowe są poprawnie zrównoważone.

Oto przykłady:

Wejście: „[{}]([])”

Wyjście: Zbalansowane

Wejście: „{[}]([])”

Wyjście: Niezbalansowane

Stos jest idealnym narzędziem do rozwiązania tego problemu. Oto kroki, które wykonamy:

• Tworzymy stos, na którym będziemy przechowywać znaki.
• Jeśli długość wyrażenia jest nieparzysta, to na pewno jest niezbalansowane.
• Iterujemy przez dane wyrażenie:
  • Jeśli napotkamy nawias otwierający (, { lub [, wkładamy go na stos.
  • Jeśli napotkamy nawias zamykający ), } lub ], zdejmujemy nawias ze szczytu stosu.
  • Sprawdzamy, czy zdjęty nawias pasuje do nawiasu zamykającego. Jeśli nie, wyrażenie jest niezbalansowane.
• Po przejściu całego wyrażenia, jeśli stos jest pusty, to wyrażenie jest zbalansowane. W przeciwnym razie nie jest.

Do sprawdzania, czy nawiasy do siebie pasują, możemy wykorzystać zbiory.

## stack
class Stack:
    def __init__(self):
        self.elements = []

    def push(self, data):
        self.elements.append(data)
        return data

    def pop(self):
        return self.elements.pop()

    def peek(self):
        return self.elements[-1]

    def is_empty(self):
        return len(self.elements) == 0

def balance_check(expression):
    ## checking the length of the expression
    if len(expression) % 2 != 0:
        ## not balanced if the length is odd
        return False

    ## for checking
    opening_brackets = set('([{')
    pairs = set([ ('(',')'), ('[',']'), ('{','}') ])

    ## stack initialization
    stack = Stack()

    ## iterating through the given expression
    for bracket in expression:

        ## checking whether the current bracket is opened or not
        if bracket in opening_brackets:
            ## adding to the stack
            stack.push(bracket)
        else:
            ## popping out the last bracket from the stack
            popped_bracket = stack.pop()

            ## checking whether popped and current bracket pair
            if (popped_bracket, bracket) not in pairs:
                return False

    return stack.is_empty()

if __name__ == '__main__':
    if balance_check('[{}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")

    if balance_check('{[}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")

Stos można wykorzystać w wielu innych sytuacjach. Przedstawiony przykład jest tylko jednym z nich. Zachęcam do poszukiwania dalszych zastosowań tej struktury.

Podsumowanie

To już koniec tego poradnika. Mam nadzieję, że nauka była dla Ciebie równie przyjemna, jak dla mnie tworzenie tego tekstu. Do zobaczenia przy kolejnych wyzwaniach!

Miłego kodowania! 🙂 👨‍💻