ALG4

134 Rozdział 5. Struktury danyct

Jak to zwykle bywa, możliwych implementacji kolejek jest co najmniej kilka. Realizacja efektywna „czasowo” za pomocą list jednokierunkowych jest zbliżona do tej wzmiankowanej przy okazji omawiania stosu. Nie będzie ona stanowiła przedmiotu naszej dyskusji, ograniczymy się jedynie do prostej implementacji tablicowej (zbliżonej zresztą ideowo do tablicowej realizacji stosu).

Tablicowa implementacja kolejki FIFO jest wyjaśniona na rysunku 5 -17.

Zawartość kolejki stanowią elementy pomiędzy głową i ogonem - te dwie zmienne będą oczywiście zmiennymi prywatnymi klasy FIFO. Dojście nowego elementu do I kolejki wiąże się z inkrernentacją zmiennej ogon i dopisaniem elementu u dołu „szarej strefy”. Oczywiście w pewnym momencie może się okazać, że ogon osią-1 gnął koniec tablicy - wówczas pojęcie dołu odwróci się i to dosłownie!

W takim przypadku cała szara strefa zawinie się wokół elementu zerowego tablicy. Obsługa „klienta” będącego aktualnie na początku kolejki wiąże się z zapamiętaniem elementu czołowego i z inkrernentacją zmiennej głowa. Trzeba się umówić I ponadto jak interpretować stwierdzenie, że kolejka jest pusta?

Rys. 5-17.

Tablicowa realizacja kolejki FIFO.

MaxE

Zamiast komplikować sobie życie specjalnymi testami zawartości tablicy, można po prostu założyć, że gdy glowa=ogon, to kolejka jest pusta. Tym samym trzeba zarezerwować jeden dodatkowy element tablicy, który nigdy nie będzie wykorzystany z uwagi na sposób działania metody wsław. Po tych rozbudowanych wyjaśnieniach programowa realizacja kolejki nic powinna już stanowić żadnej niespodzianki dla Czytelnika:

knlejka.lt

tomplate <class TypPodst> clasa FIFO

TypPodst *t;

int głowa,ogon,MaxElt;