Dla zainteresowanych: stos jako klasa - PY_I_R_W13B_M05 Dynamiczne struktury danych. Implementacja

Rc3eHnGputwzz

Stos

Przypomnijmy, że stos to liniowa struktura typu LIFO (ang. Last‑In, First‑Out – ostatni na wejściu, pierwszy na wyjściu), która obsługuje dwie podstawowe operacje, tj. odkładanie i zdejmowanie danych. Dodatkowe działania, które wykonuje się na stosie, to odczytywanie wierzchołka stosu, czyli ostatniego odłożonego elementu, bez usuwania go, oraz ewentualnie sprawdzanie rozmiaru stosu, czyli liczby odłożonych elementów.

Ważne!

W programie korzystamy z biblioteki sys.

Biorąc powyższe warunki pod uwagę, do implementacji stosu wystarczy nam jednokierunkowa lista niecykliczna. Elementami tej listy będą węzły zawierające dane, np. liczby, oraz – w przypadku listy jednokierunkowej – referencja na element następny. Do zdefiniowania węzła użyjemy klasy zawierającej konstruktor inicjalizujący dwa pola klasy:

class Wezel:
    def __init__(self, liczba):
        self.liczba = liczba
        self.nastepny = None

Stworzenie nowego węzła i przypisanie wartości do jego składowych umożliwia instrukcja:

nowy = Wezel(liczba)

Stos zaimplementujemy również jako klasę, której atrybutem inicjalizowanym w konstruktorze referencją pustą będzie referencja na wierzchołek stosu o nazwie wierzcholek.

class Stos:
    def __init__(self):
        self.wierzcholek = None

    # Poniżej dodamy kolejne metody

Do klasy Stos() dodamy teraz metody wykonujące charakterystyczne dla stosu operacje.

Zaczniemy od metody czyPusty(), która będzie zwracała wartość true (prawda), jeżeli stos będzie pusty, czyli w sytuacji, kiedy pole wierzcholek będzie referencją pustą. W przeciwnym razie metoda zwróci wartość false (fałsz).

def czy_pusty(self):
    if self.wierzcholek is None:
        print("Stos pusty!")
        return True
    return False

W celu zachowania poprawności działania struktury LIFO, funkcja odloz() będzie dodawała elementy na początku listy i odpowiednio funkcja zdejmij() będzie usuwała elementy również z początku listy.

Zacznijmy od metody odloz():

def odloz(self, liczba):
    print("Odkladam", liczba)
    nowy = Wezel(liczba)
    nowy.nastepny = self.wierzcholek
    self.wierzcholek = nowy

W funkcji odloz() tworzymy nowy węzeł i zapisujemy w nim wartość zmiennej liczba przekazaną jako argument. Następnie pole nastepny nowego elementu ustawiamy na dotychczasowy wierzcholek, w ten sposób dodajemy element na początku listy. Na koniec aktualizujemy pole wierzcholek, tak aby wskazywało na nowo dodany element.

W metodzie pomijamy sprawdzenie ewentualnego błędu przepełnienia stosu, który ze względu na użycie listy jest mało prawdopodobny.

Usuwanie pierwszego elementu jest możliwe dzięki referencji wierzcholek:

def zdejmij(self):
    if self.czy_pusty():
        return -sys.maxsize - 1

    pomocniczy = self.wierzcholek
    liczba = pomocniczy.liczba
    self.wierzcholek = self.wierzcholek.nastepny

    print("Zdejmuje", liczba)
    return liczba

Jeżeli stos jest pusty, tzn. zachodzi błąd niedopełnienia stosu, zwracamy minimalną wartość dla typu całkowitego, którą w języku wylicza się jako ujemną wartość maksymalną (-sys.maxsize) pomniejszoną o 1.

W przeciwnym razie dotychczasowy pierwszy element oraz zapisaną w nim wartość zapamiętujemy w zmiennych pomocniczych. Następnie ustawiamy wierzchołek na drugi element listy, dotychczasowy pierwszy usuwamy, a zapamiętaną wartość zwracamy.

Metoda pobierz_wierzcholek() ma tylko jedno zadanie: jeżeli stos nie jest pusty, zwraca wartość zapisaną w pierwszym, czyli ostatnim dodanym, elemencie listy:

def pobierz_wierzcholek(self):
    if self.czy_pusty():
        return -sys.maxsize - 1
    return self.wierzcholek.liczba

Metoda wypisz() posłuży do wypisania wartości odłożonych na stosie, czyli zapisanych w kolejnych węzłach listy:

def wypisz(self):
    if self.czy_pusty():
        return

    print("Stos zawiera:", end="")
    pomocniczy = self.wierzcholek
    while pomocniczy:
        print(pomocniczy.liczba, "", end="")
        pomocniczy = pomocniczy.nastepny;
    print()

Do wypisania wartości używamy pętli przechodzącej po wszystkich elementach stosu zapisywanych w zmiennej pomocniczy, którą ustawiamy na wierzchołek, a następnie wewnątrz pętli przesuwamy na kolejne węzły wskazywane przez pole nastepny. Pętla będzie działać dopóki nie dojdziemy do ostatniego węzła, którego referencja nastepny będzie pusta.

Do sprawdzenia działania stosu możemy użyć poniższego kodu:

stos = Stos()
stos.odloz(1)
stos.odloz(2)
stos.odloz(3)
stos.wypisz()
stos.zdejmij()
stos.zdejmij()
stos.zdejmij()
stos.zdejmij()

Ćwiczenie 1

Na podstawie omówionego kodu przygotuj program ilustrujący działanie stosu. Przeanalizuj podaną funkcje główną i odpowiedz, jaki będzie ostatni wypisany przez program komunikat. Uruchom program i sprawdź poprawność swojej odpowiedzi.

RM4BEI8u73tF1

Linia 1. import sys. Linia 3. class Wezel dwukropek. Linia 4. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self przecinek liczba zamknij nawias okrągły dwukropek. Linia 5. self kropka liczba znak równości liczba. Linia 6. self kropka nastepny znak równości None. Linia 8. class Stos dwukropek. Linia 9. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 10. self kropka wierzcholek znak równości None. Linia 12. def czy podkreślnik pusty otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 13. if self kropka wierzcholek is None dwukropek. Linia 14. print otwórz nawias okrągły cudzysłów Stos pusty wykrzyknik cudzysłów zamknij nawias okrągły. Linia 15. return True. Linia 16. return False. Linia 18. def odloz otwórz nawias okrągły self przecinek liczba zamknij nawias okrągły dwukropek. Linia 19. print otwórz nawias okrągły cudzysłów Odkladam cudzysłów przecinek liczba zamknij nawias okrągły. Linia 20. nowy znak równości Wezel otwórz nawias okrągły liczba zamknij nawias okrągły. Linia 21. nowy kropka nastepny znak równości self kropka wierzcholek. Linia 22. self kropka wierzcholek znak równości nowy. Linia 24. def zdejmij otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 25. if self kropka czy podkreślnik pusty otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 26. return minus sys kropka maxsize minus 1. Linia 27. pomocniczy znak równości self kropka wierzcholek. Linia 28. liczba znak równości pomocniczy kropka liczba. Linia 29. self kropka wierzcholek znak równości self kropka wierzcholek kropka nastepny. Linia 30. print otwórz nawias okrągły cudzysłów Zdejmuje cudzysłów przecinek liczba zamknij nawias okrągły. Linia 31. return liczba. Linia 33. def pobierz podkreślnik wierzcholek otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 34. if self kropka czy podkreślnik pusty otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 35. return minus sys kropka maxsize minus 1. Linia 36. return self kropka wierzcholek kropka liczba. Linia 38. def wypisz otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 39. if self kropka czy podkreślnik pusty otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 40. return. Linia 42. print otwórz nawias okrągły cudzysłów Stos zawiera dwukropek cudzysłów przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 43. pomocniczy znak równości self kropka wierzcholek. Linia 44. while pomocniczy dwukropek. Linia 45. print otwórz nawias okrągły pomocniczy kropka liczba przecinek cudzysłów cudzysłów przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 46. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 47. print otwórz nawias okrągły zamknij nawias okrągły. Linia 50. stos znak równości Stos otwórz nawias okrągły zamknij nawias okrągły. Linia 51. stos kropka odloz otwórz nawias okrągły 1 zamknij nawias okrągły. Linia 52. stos kropka odloz otwórz nawias okrągły 2 zamknij nawias okrągły. Linia 53. stos kropka odloz otwórz nawias okrągły 3 zamknij nawias okrągły. Linia 54. stos kropka wypisz otwórz nawias okrągły zamknij nawias okrągły. Linia 55. stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły. Linia 56. stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły. Linia 57. stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły. Linia 58. stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły.

import sys

class Wezel:
    def __init__(self, liczba):
        self.liczba = liczba
        self.nastepny = None

class Stos:
    def __init__(self):
        self.wierzcholek = None

    def czy_pusty(self):
        if self.wierzcholek is None:
            print("Stos pusty!")
            return True
        return False

    def odloz(self, liczba):
        print("Odkladam", liczba)
        nowy = Wezel(liczba)
        nowy.nastepny = self.wierzcholek
        self.wierzcholek = nowy

    def zdejmij(self):
        if self.czy_pusty():
            return -sys.maxsize - 1
        pomocniczy = self.wierzcholek
        liczba = pomocniczy.liczba
        self.wierzcholek = self.wierzcholek.nastepny
        print("Zdejmuje", liczba)
        return liczba

    def pobierz_wierzcholek(self):
        if self.czy_pusty():
            return -sys.maxsize - 1
        return self.wierzcholek.liczba

    def wypisz(self):
        if self.czy_pusty():
            return

        print("Stos zawiera: ", end="")
        pomocniczy = self.wierzcholek
        while pomocniczy:
            print(pomocniczy.liczba, "", end="")
            pomocniczy = pomocniczy.nastepny;
        print()


stos = Stos()
stos.odloz(1)
stos.odloz(2)
stos.odloz(3)
stos.wypisz()
stos.zdejmij()
stos.zdejmij()
stos.zdejmij()
stos.zdejmij()

Wynikiem działania programu będą komunikaty:

Odkladam 1
Odkladam 2
Odkladam 3
Stos zawiera: 3 2 1 
Zdejmuje 3
Zdejmuje 2
Zdejmuje 1
Stos pusty!

Po utworzeniu stosu odkładane są 3 wartości, natomiast później metoda zdejmij() wywoływana jest 4 razy. Dlatego ostatni komunikat brzmi: „Stos pusty!”.

Implementacja stosu

Implementacja kolejki

Stos