Informatyka dla klas II

Kolejka

Kolejka (ang. queue) jest sekwencyjną strukturą danych o takiej własności, iż element zapisany jako pierwszy jest również odczytywany jako pierwszy. Taka struktura w literaturze informatycznej nosi nazwę FIFO (ang. First In First Out – pierwszy wchodzi, pierwszy wychodzi). Kolejkę możemy sobie wyobrazić jako tubę – elementy wstawiamy do tuby z jednej strony, po czym przesuwają się one wewnątrz i wychodzą z drugiej strony w tej samej kolejności, w jakiej zostały do tuby włożone.

 

obrazek

 

Dla kolejki są zdefiniowane operacje:

  • Sprawdzenie, czy kolejka jest pusta – operacja empty zwraca true, jeśli kolejka nie zawiera żadnego elementu, w przeciwnym razie zwraca false.
  • Odczyt elementu z początku kolejki – operacja front zwraca wskazanie do elementu, który jest pierwszy w kolejce.
  • Zapis elementu na koniec kolejki – operacja push dopisuje nowy element na koniec elementów przechowywanych w kolejce.
  • Usunięcie elementu z kolejki – operacja pop usuwa z kolejki pierwszy element.

Jeśli porównasz te operacje z operacjami dostępnymi dla stosu, to okaże się, że obie te struktury są bardzo do siebie podobne. Różnią się jedynie kolejnością dostępu do elementów.

Kolejka jako tablica

Naturalną strukturą danych dla kolejek jest lista, jednakże w prostszych przypadkach kolejkę da się zrealizować w tablicy. W takim przypadku musimy założyć z góry maksymalny rozmiar kolejki (ilość przechowywanych w niej elementów). Będziemy potrzebowali trzech zmiennych:

 

Q  –  tablica, w której będzie tworzona kolejka. Tablica ma n  elementów, indeksy rozpoczynają się od 0.
qptr  – indeks elementu, który jest początkiem kolejki
qcnt  – liczba elementów, którą przechowuje kolejka

 

Kolejkę tworzą kolejne elementy o indeksach rozpoczynających się od qptr. Na początku qptr  wskazuje pierwszy element tablicy o indeksie 0:

 

obrazek

 

Koniec kolejki wyznacza indeks równy qptr  + qcnt. Jeśli indeks ten wykracza poza ostatni element tablicy, to należy go zmniejszyć o n. Dopisanie elementu zwiększa licznik qcnt  o 1:

 

obrazek

 

Odczyt elementu z kolejki polega na przetworzeniu elementu o indeksie qptr. Usunięcie elementu z kolejki polega na zwiększeniu o 1 indeksu qptr. Jeśli po zwiększeniu qptr  wskazuje poza ostatni element tablicy, to qptr  należy wyzerować – kolejka znów rozpocznie się od początku tablicy. Licznik qptr  zawsze zmniejszamy o 1.

 

obrazek

 

Zwróć uwagę, że w tej implementacji kolejka nie zajmuje stałego położenia w tablicy. Co więcej, jej elementy mogą być rozdzielone:

 

obrazek

 

Kolejka w tablicy – algorytm sprawdzania, czy kolejka jest pusta

Wejście
qcnt    liczba elementów przechowywana w kolejce
Wyjście:

True, jeśli kolejka jest pusta, inaczej false

Lista kroków:
K01 Jeśli qcnt  = 0, to zakończ z wynikiem true
K02: Zakończ z wynikiem false

 

Kolejka w tablicy – algorytm odczytu kolejki

Wejście
Q   tablica, w której przechowywana jest kolejka
qcnt    liczba elementów przechowywana w kolejce
qptr   indeks początku kolejki
Wyjście:

Wartość elementu na początku kolejki lub wartość specjalna, jeśli kolejka jest pusta.

Lista kroków:
K01 Jeśli qcnt  = 0, to zakończ z wynikiem wartość specjalna ; kolejka pusta?
K02: Zakończ z wynikiem Q[qptr]  

 

Kolejka w tablicy – algorytm zapisu do kolejki

Wejście
n   liczba elementów w tablicy
Q   tablica, w której przechowywana jest kolejka
qcnt    liczba elementów przechowywana w kolejce
qptr   indeks początku kolejki
v   dopisywany element
Wyjście:

Jeśli w tablicy jest miejsce, to do kolejki zostaje dopisana nowa wartość. Inaczej kolejka nie jest zmieniana.

Elementy pomocnicze:
i  –  indeks
Lista kroków:
K01 Jeśli qcnt  = n, to zakończ ; sprawdzamy, czy w tablicy jest miejsce na nowy element
K02: i  ← qptr  + qcnt ; wyznaczamy położenie końca kolejki
K03: Jeśli i  ≥ n, to i  ← i  - n ; korygujemy i w razie potrzeby
K04: Q[i] ← v ; umieszczamy element na końcu kolejki
K05: qcnt  ← qcnt  + 1 ; zwiększamy liczbę elementów
K06: Zakończ  

 

Kolejka w tablicy – algorytm usuwania z kolejki

Wejście
n   liczba elementów w tablicy
Q   tablica, w której przechowywana jest kolejka
qcnt    liczba elementów przechowywana w kolejce
qptr   indeks początku kolejki
Wyjście:

Kolejka pomniejszona o pierwszy element.

Lista kroków:
K01 Jeśli qcnt  = 0, to zakończ ; sprawdzamy, czy kolejka zawiera jakieś elementy
K02: qcnt  ← qcnt  - 1 ; zmniejszamy licznik elementów
K03: qptr  ← qptr  + 1 ; przesuwamy początek kolejki
K04: Jeśli qptr  = n, to qptr  ← 0 ; korygujemy indeks początku kolejki
K05: Zakończ  

 

Kolejka jako lista

Do realizacji kolejki posłużymy się lekko zmodyfikowaną listą jednokierunkową. Będziemy potrzebowali dwóch wskaźników:

 

head  –  wskaźnik pierwszego elementu na liście
tail  – wskaźnik ostatniego elementu na liście

 

Nowe elementy dodajemy na koniec listy – dzięki wskaźnikowi tail  szybko będziemy mogli znaleźć ostatni element i dołączyć za nim element wstawiany. Pobieranie elementów będzie się odbywało z początku listy. Budowa elementów listy jest typowa: każdy zawiera pole next, które wskazuje kolejny element na liście, oraz pole data, które zawiera przechowywane dane:

Typ elementu listy

struct slistEl
{
  slistEl * next;
  typ_danych data;
};

 

Kolejka na liście – algorytm sprawdzania, czy kolejka jest pusta

Wejście
head    wskaźnik początku kolejki
Wyjście:

True, jeśli kolejka jest pusta, inaczej false

Lista kroków:
K01 Jeśli head  = nil, to zakończ z wynikiem true
K02: Zakończ z wynikiem false

 

Kolejka na liście – algorytm odczytu kolejki

Wejście
head    wskaźnik pierwszego elementu listy
Wyjście:

Wartość elementu na początku kolejki lub wartość specjalna, jeśli kolejka jest pusta.

Lista kroków:
K01 Jeśli head  = 0, to zakończ z wynikiem wartość specjalna ; kolejka pusta?
K02: Zakończ z wynikiem (headdata)  

 

Kolejka na liście – algorytm zapisu do kolejki

Wejście
head    wskaźnik pierwszego elementu listy
tail   wskaźnik ostatniego elementu listy
v   dopisywany element
Wyjście:

Kolejka z dopisanym na końcu elementem o wartości v.

Elementy pomocnicze:
p  –  wskaźnik elementu listy
Lista kroków:
K01 Utwórz nowy element listy  
K02: p  ← adres nowego elementu  
K03: (pnext) ← nil ; inicjujemy pola nowego elementu
K04: (pdata) ← v  
K05: Jeśli tail  ≠ nil, to idź do K08 ; sprawdzamy, czy lista jest pusta
K06: head  ← p ; jeśli tak, to wprowadzamy do niej element jako pierwszy i ostatni
K07 Idź do K09  
K08: (tailnext) ← p ; inaczej element dołączamy na koniec listy
K09: tail  ← p ; ustawiamy element jako ostatni na liście
K10: Zakończ  

 

Kolejka na liście – algorytm usuwania z kolejki

Wejście
head    wskaźnik pierwszego elementu listy
tail   wskaźnik ostatniego elementu listy
Wyjście:

Kolejka pomniejszona o pierwszy element.

Elementy pomocnicze:
p  –  wskaźnik elementu listy
Lista kroków:
K01 Jeśli head  = nil, to zakończ ; jeśli lista jest pusta, kończymy
K02: p  ← head ;zapamiętujemy adres pierwszego elementu
K03: head  ← (headnext) ;odłączamy od listy pierwszy element
K04: Jeśli head  = nil, to tail  ← nil ; jeśli lista stała się pusta, to nie posiada ostatniego elementu
K05: Usuń z pamięci element wskazywany przez p  
K06: Zakończ  

 

Przechodzenie drzewa wszerz

Przechodzenie drzewa binarnego wszerz (ang. breadth-first search, BFS) polega na odwiedzaniu kolejnych węzłów leżących na kolejnych poziomach.

 

obrazek

 

Najpierw odwiedzamy korzeń drzewa – węzeł nr 0, który znajduje się na poziomie 0. Dalej przechodzimy do jego synów i odwiedzamy węzły nr 1 i 2 na poziomie 1. W kolejnym kroku przechodzimy do poziomu 2 i odwiedzamy kolejno węzły nr 3, 4, 5 i 6. Operację tę kontynuujemy, aż do przejścia przez wszystkie węzły drzewa.

Tego typu przejście wymaga zapamiętywania wskazań węzłów w kolejce. Kolejka pozwala odczytywać umieszczone w niej elementy w tej samej kolejności, w jakiej zostały do niej wstawione, czyli jest jakby buforem opóźniającym. Prześledźmy przejście BFS przedstawione w poniższej tabelce (dane dopisujemy na koniec kolejki, czyli z prawej strony, a pobieramy z początku kolejki, czyli z lewej strony):

 

Stan przejścia Kolejka Przetworzone węzły Opis
  [ A ]   Umieszczamy w kolejce węzeł startowy, czyli A. Przejście wykonywane jest w pętli dotąd, aż kolejka stanie się pusta.
obrazek [ B C ] A Pobieramy z kolejki węzeł A. Odwiedzamy go. W kolejce umieszczamy dzieci węzła A, czyli węzły B i C
obrazek [ C D E ] A B Pobieramy z kolejki węzeł B. Odwiedzamy go. W kolejce umieszczamy synów D i E.
obrazek [ D E F G ] A B C Pobieramy z kolejki węzeł C. Odwiedzamy go. W kolejce umieszczamy synów F i G.
obrazek [ E F G H I ] A B C D Pobieramy z kolejki węzeł D. Odwiedzamy go. W kolejce umieszczamy synów H i I.
obrazek [ F G H I J ] A B C D E Pobieramy z kolejki węzeł E. Odwiedzamy go. W kolejce umieszczamy syna J
obrazek [ G H I J K ] A B C D E F Pobieramy z kolejki węzeł F. Odwiedzamy go. W kolejce umieszczamy syna K
obrazek [ H I J K ] A B C D E F G Pobieramy z kolejki węzeł G. Odwiedzamy go. Węzeł jest liściem, więc nic nie umieszczamy w kolejce.
obrazek [ I J K ] A B C D E F G H Pobieramy z kolejki węzeł H. Odwiedzamy go. Węzeł jest liściem, więc nic nie umieszczamy w kolejce.
obrazek [ J K ] A B C D E F G H I Pobieramy z kolejki węzeł I. Odwiedzamy go.
obrazek [ K ] A B C D E F G H I J Pobieramy z kolejki węzeł J. Odwiedzamy go.
obrazek [ pusta ] A B C D E F G H I J K Pobieramy z kolejki węzeł K. Odwiedzamy go. Kończymy przechodzenie drzewa, ponieważ kolejka jest już pusta.

Na poniższym rysunku zaznaczyliśmy linię przejścia przez kolejne węzły drzewa.

obrazek → BFS → obrazek

Rozmiar kolejki nie przekracza 2h, gdzie h  jest wysokością drzewa.

 

Algorytm kolejkowy BFS dla drzewa binarnego

Wejście
v    wskazanie węzła startowego drzewa binarnego
h    wysokość drzewa
Wyjście:
przetworzenie wszystkich węzłów drzewa kolejnymi poziomami od strony lewej do prawej.
Elementy pomocnicze:
Q    kolejka, której elementy są wskazaniami węzłów drzewa. Długość kolejki jest równa 2h.
Lista kroków:
K01: Utwórz pustą kolejkę Q  
K02: Q.push(v) ; zapamiętujemy wskazanie węzła startowego w kolejce
K03: Dopóki Q.empty() = false: wykonuj K04...K08  
K04:     v  ← Q.front() ; pobieramy wskazanie węzła z początku kolejki
K05:     Q.pop() ; usuwamy pobrany element z kolejki
K06:     Odwiedź węzeł wskazywany przez v ; przetwarzamy węzeł
K07:     Jeśli (vleft) ≠ nil, to Q.push(vleft) ; jeśli węzeł ma lewego syna, to umieszczamy jego wskazanie w kolejce
K08:     Jeśli (vright) ≠ nil, to Q.push(vright) ; jeśli węzeł ma prawego syna, to umieszczamy jego wskazanie w kolejce
K09: Zakończ  

   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe