Kolejka na Tablicy

Cel

Kolejka, która powszechnie jest używana w programowaniu, może zapisywać dane na tablicy o stałej długości. Taka implementacja ma pewne ograniczenia, ale też zalety.

Opis

Kolejka jest to struktura danych, która pozwala na:

1. dodanie elementu
2. usunięcie elementu
3. odczytanie długości kolejki

Elementy w kolejce wychodzą w takiej samej kolejności w jakiej nadeszły, więc dodając do kolejki 1, 2, 3, 4 elementy będą później zdjęte w tej samej kolejności.

Analiza implementacji

Chcą skorzystać z tablicy jak kolejki potrzebne są dwa indeksy oraz rozmiar tablicy. Pierwszy indeks wskazuje, gdzie w tablicy znajduje się pierwszy, nieodczytany element w tablicy. Dalej będziemy go nazywać "Początek". Z kolei drugi indeks wskazuje miejsce zapisu następnego elementu i nazwiemy go "Koniec".

Kiedy "Początek" i "Koniec" są indeksami o tej samej wartości to oznacza, że kolejka jest pusta. Ze względu na to, że tablica ma określony rozmiar to może dojść do sytuacji, gdy nie będzie można zapisać kolejnego elementu. Kolejka będzie pełna, gdy wstawienie kolejnego elementu przesunęłoby indeks "Koniec" tam gdzie znajduje się "Początek". Na podstawie pozycji indeksów można też obliczyć ile w kolejce znajduje się elementów.

Wadą opierania implementacji kolejki o tablicę jest ograniczona pojemność oraz stałe zużycie pamięcie niezależnie od tego jaki będzie maksymalny rozmiar kolejki. Warto jednak zauważyć, że po zaalokowaniu pamięci kolejka zawsze gwarantuje określoną podczas tworzenia ilość pozycji. Wybór pomiędzy kolejką dynamiczną, a statyczną należy wybrać w zależności od projektu.

Przykład

Przypuśćmy, że mamy kolejkę, która może pomieścić maksymalnie trzy elementy. Wtedy dane o kolejce będą się zmieniać następująco:

W powyższym schemacie przez gwiazdkę * została oznaczona pozycja indeksu "Koniec" w przypadku, gdy po niej nie występuje puste pole to do kolejki nie może zostać dołączony nowy element.

Implementacja

Celem implementacji jest utworzenie klasy Kolejka, która pozwoli na przechowywanie liczb całkowitych. W przypadku, gdy operacja nie będzie możliwa zostanie zwrócony odpowiedni błąd. Poniższy kod jest przykładowy.

Część prywatna

W części prywatnej klasy muszą się znaleźć: tablica do zapisu danych, indeksy oraz rozmiar tablicy.

Konstruktor

Kolejka nie będzie działać poprawnie jeśli wartości na początku nie zostaną poprawnie ustawione. Konstruktor będzie przyjmować jeden argument: rozmiar kolejki. Oba indeksy najlepiej jest ustawić na ten sam indeks 0, a tablicę należy przygotować pod zapisanych. Rozmiar deklarowanej tablicy jest o 1 większy niż podany argument w konstruktorze.

1.   def __init__(self, rozmiar):
2.     self.poczatek = 0
3.     self.koniec = 0
4.     self.n = rozmiar + 1
5.     self.tablica = [None for i in range(rozmiar + 1)]

Stan Kolejki

Następnie można zaimplementować dwie funkcje, które będą sprawdzać czy kolejka jest pusta czy pełna. Zostaną one wykorzystane podczas odczytu / zapisu, aby uniknąć nieprawidłowej operacji.

1.   def CzyPelna(self):
2.     return self.Zwieksz(self.koniec) == self.poczatek

1.   def CzyPusta(self):
2.     return self.koniec == self.poczatek

Długość Kolejki

Dopóki indeks "Koniec" kolejki jest większy niż indeks "Początek" to długość kolejki to różnica tych dwóch indeksów. Należy jednak pamiętać, że indeksy zmieniają się cyklicznie, więc w pewnym momencie zajdzie odwrotna relacja i "Koniec" znajdzie się przed "Początkiem". Wtedy należy ich sumę odjąć od rozmiaru tablicy.

1.   def Ile(self):
2.     if (self.koniec >= self.poczatek):
3.       return self.koniec - self.poczatek
4.     else:
5.       return self.n - self.poczatek + self.koniec

Operacje na kolejce

Funkcja Dodaj() przyjmuje jeden argument - liczbę, która ma zostać umieszczona w kolejce. Przed dopisaniem elementu do tablicy należy upewnić się, że kolejka nie jest pełna. Inaczej po dodaniu większej ilości elementów niż tablica ma rozmiar dojdzie do nadpisywania danych. Pod dopisaniu elementu wystarczy przesunąć indeks "Koniec" o jedno miejsce w prawo.

1.   def Dodaj(self, a):
2.     if (self.CzyPelna()):
3.       raise Exception("Kolejka pelna")
4.     else:
5.       self.tablica[self.koniec] = a
6.       self.koniec = self.Zwieksz(self.koniec)

Analogicznie podczas usuwania funkcja Usun() musi sprawdzić czy kolejka nie jest pusta. Jeśli tak to musi zgłosić wyjątek. W przeciwnym razie pobiera odpowiedni element, zwiększa indeks "Początek" i zwraca odczytaną wartość.

1.   def Usun(self):
2.     if (self.CzyPusta()):
3.       raise Exception("Kolejka pusta")
4.     else:
5.       wynik = self.tablica[self.poczatek]
6.       self.poczatek = self.Zwieksz(self.poczatek)
7.       return wynik

Do zwiększania indeksu o 1 została napisana specjalna funkcja Zwieksz(), która ma za zadanie pilnować, aby indeks był poprawnym indeksem pewnego elementu z tablicy.

1.   def Zwieksz(self, a):
2.     return (a + 1) % self.n

Testowanie funkcji

Do przetestowania napisanej klasy wystarczy poniższy kod:

1. kolejka = Kolejka(5);
3. for i in range(6):
4.   try:
5.     kolejka.Dodaj(i)
6.     print("Dodano", i)
7.   except Exception as ex:
8.     print("Nie dodano " + str(i) + ": " + ex.args[0])
10. print("Elementów", kolejka.Ile())
12. a = kolejka.Usun()
13. print("Wyjęto", a)
14. kolejka.Dodaj(a)
15. print("Dodano", a)
16. print("Elementów", kolejka.Ile())
18. for i in range(6):
19.   try:
20.     a = kolejka.Usun()
21.     print("Wyjęto", a)
22.   except Exception as ex:
23.     print("Nie wyjęto:", ex.args[0])

Po uruchomieniu zwróci ona następujący wynik:

1. Dodano 0
2. Dodano 1
3. Dodano 2
4. Dodano 3
5. Dodano 4
6. Nie dodano 5: Kolejka pelna
7. Elementów 5
8. Wyjęto 0
9. Dodano 0
10. Elementów 5
11. Wyjęto 1
12. Wyjęto 2
13. Wyjęto 3
14. Wyjęto 4
15. Wyjęto 0
16. Nie wyjęto: Kolejka pusta

Klasa działa poprawnie. Początkowo program próbuje zapisać 6 elementów, ale przy szóstym zgłaszany zostaje wyjątek. Następnie jeden element zostaje zdjęty i ponownie włożony. Przed i po tej części długość tablicy nie powinna się zmienić. Sprawdzane jest tutaj obliczanie długości kolejki dla indeksów o różnych relacjach. Następnie zwrócone są kolejno elementy 1, 2, 3, 4, 0, a przy próbie odczytu kolejnego zostaje zgłoszony wyjątek.

• Kod źródłowy Implementacja