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

Rc3eHnGputwzz

Kolejka

Kolejka to liniowa struktura danych typu FIFO (ang. First‑In, First‑Out – pierwszy na wejściu, pierwszy na wyjściu), co oznacza, że jej elementy odczytywane są zgodnie z kolejnością dodawania, a zatem odwrotnie niż w przypadku stosu.

W implementacji kolejki również użyjemy listy jednokierunkowej i takiej samej jak w przypadku stosu definicji klasy Wezel. Natomiast klasa Kolejka będzie zawierała dwa pola:

glowa – referencję na pierwszy element kolejki;
ogon – referencję na ostatni element kolejki, który ułatwi dodawanie elementów na końcu listy.

Nazwy pozostałych metod dostosujemy do omawianej struktury.

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

class Kolejka:
    def __init__(self):
        self.glowa = None
        self.ogon = None

    # Poniżej dodamy kolejne metody

Metoda czy_pusta() działa tak samo, jak w przypadku stosu i każdej listy, tzn. jeżeli referencja na pierwszy element jest pusta, lista jest pusta.

    def czy_pusta(self):
        return self.glowa is None

Metoda dodaj() będzie dodawała nowe elementy na końcu listy przy użyciu pola ogon.

    def dodaj(self, liczba):
        print("Dodaje:", liczba)
        nowy = Wezel(liczba)

        if self.czy_pusta():
            self.glowa = self.ogon = nowy
        else:
            self.ogon.nastepny = nowy
            self.ogon = nowy

Na początku metody tworzymy nowy węzeł, przypisujemy otrzymaną liczbę do jego pola liczba, a referencję nastepny ustawiamy na wartość pustą. Następnie, jeżeli lista jest pusta, referencje na pierwszy (glowa) i ostatni (ogon) element listy ustawiamy na nowy węzeł.

W przeciwnym razie referencję nastepny dotychczasowego ostatniego elementu ustawiamy na nowy węzeł i aktualizujemy referencję ogon, aby wskazywał nowo dodany element.

Metoda usun() będzie zwracała kolejne elementy z początku listy, czyli działać będzie tak samo, jak metoda zdejmij() w przypadku stosu. Ponieważ jednak elementy będą dodawane na końcu listy, zasada działania kolejki FIFO zostanie zachowana.

def usun(self):
    if self.czy_pusta():
        return -sys.maxsize - 1

    pomocniczy = self.glowa
    liczba = pomocniczy.liczba
    self.glowa = self.glowa.nastepny
    print("Usuwam:", liczba)
    return liczba

Ćwiczenie 1

Wykorzystaj omówiony kod i przygotuj program pozwalający sprawdzić działanie kolejki. Dodaj do kolejki trzy liczby, wypisz kolejkę, a następnie wywołaj metodę usuwającą cztery razy.

R1LHghliGaqEJ

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 Kolejka 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 glowa znak równości None. Linia 11. self kropka ogon znak równości None. Linia 13. def czy podkreślnik pusta otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 14. return self kropka glowa is None. Linia 16. def dodaj otwórz nawias okrągły self przecinek liczba zamknij nawias okrągły dwukropek. Linia 17. print otwórz nawias okrągły cudzysłów Dodaje dwukropek cudzysłów przecinek liczba zamknij nawias okrągły. Linia 18. nowy znak równości Wezel otwórz nawias okrągły liczba zamknij nawias okrągły. Linia 20. if self kropka czy podkreślnik pusta otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 21. self kropka glowa znak równości self kropka ogon znak równości nowy. Linia 22. else dwukropek. Linia 23. self kropka ogon kropka nastepny znak równości nowy. Linia 24. self kropka ogon znak równości nowy. Linia 26. def usun otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 27. if self kropka czy podkreślnik pusta otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 28. return minus sys kropka maxsize minus 1. Linia 30. pomocniczy znak równości self kropka glowa. Linia 31. liczba znak równości pomocniczy kropka liczba. Linia 32. self kropka glowa znak równości self kropka glowa kropka nastepny. Linia 33. print otwórz nawias okrągły cudzysłów Usuwam dwukropek cudzysłów przecinek liczba zamknij nawias okrągły. Linia 34. return liczba. Linia 36. def wypisz otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 37. if self kropka czy podkreślnik pusta otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 38. print otwórz nawias okrągły cudzysłów Kolejka jest pusta wykrzyknik cudzysłów zamknij nawias okrągły. Linia 39. return. Linia 41. print otwórz nawias okrągły cudzysłów Kolejka zawiera dwukropek cudzysłów przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 42. pomocniczy znak równości self kropka glowa. Linia 43. while pomocniczy dwukropek. Linia 44. 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 45. pomocniczy znak równości pomocniczy kropka nastepny. Linia 46. print otwórz nawias okrągły zamknij nawias okrągły. Linia 49. kolejka znak równości Kolejka otwórz nawias okrągły zamknij nawias okrągły. Linia 50. kolejka kropka dodaj otwórz nawias okrągły 1 zamknij nawias okrągły. Linia 51. kolejka kropka dodaj otwórz nawias okrągły 2 zamknij nawias okrągły. Linia 52. kolejka kropka dodaj otwórz nawias okrągły 3 zamknij nawias okrągły. Linia 53. kolejka kropka wypisz otwórz nawias okrągły zamknij nawias okrągły. Linia 54. kolejka kropka usun otwórz nawias okrągły zamknij nawias okrągły. Linia 55. kolejka kropka usun otwórz nawias okrągły zamknij nawias okrągły. Linia 56. kolejka kropka usun otwórz nawias okrągły zamknij nawias okrągły. Linia 57. kolejka kropka usun 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 Kolejka:
    def __init__(self):
        self.glowa = None
        self.ogon = None

    def czy_pusta(self):
        return self.glowa is None

    def dodaj(self, liczba):
        print("Dodaje:", liczba)
        nowy = Wezel(liczba)

        if self.czy_pusta():
            self.glowa = self.ogon = nowy
        else:
            self.ogon.nastepny = nowy
            self.ogon = nowy

    def usun(self):
        if self.czy_pusta():
            return -sys.maxsize - 1

        pomocniczy = self.glowa
        liczba = pomocniczy.liczba
        self.glowa = self.glowa.nastepny
        print("Usuwam:", liczba)
        return liczba

    def wypisz(self):
        if self.czy_pusta():
            print("Kolejka jest pusta!")
            return

        print("Kolejka zawiera: ", end="")
        pomocniczy = self.glowa
        while pomocniczy:
            print(pomocniczy.liczba, "", end="")
            pomocniczy = pomocniczy.nastepny
        print()


kolejka = Kolejka()
kolejka.dodaj(1)
kolejka.dodaj(2)
kolejka.dodaj(3)
kolejka.wypisz()
kolejka.usun()
kolejka.usun()
kolejka.usun()
kolejka.usun()

Wynik działania programu:

Dodaje: 1
Dodaje: 2
Dodaje: 3
Kolejka zawiera: 1 2 3 
Usuwam: 1
Usuwam: 2
Usuwam: 3

Implementacja kolejki

Dla zainteresowanych: implementacja listy jedno i dwukierunkowej

Kolejka