Struktury danych/Kolejki

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

Kolejki

Kolejka jest przeciwieństwem stosu omawianego wcześniej. Łatwo sobie wyobrazić sytuację, w której dostęp do danych jak w stosie nie będzie nam potrzebny ani efektywny, a będziemy potrzebować struktury, która w swej naturze będzie miała pewne ograniczenia związane z dostępem do danych. W kolejce to ograniczenie pozwala nam zachować dodatkowy parametr, który można wykorzystać. Jest nim właśnie kolejność dodawania do zbioru. Możemy więc wyobrazić sobie kolejkę jako tubę, przez którą przepychamy elementy w takiej kolejności w jakiej do niej je włożyliśmy.

Opis

Idea działania kolejki

Kolejka (ang. queue) w przeciwieństwie do stosu, podczas usuwania zawsze wyrzuca "najstarszy" element kolekcji, tzn. ten, który został dodany najwcześniej, dlatego bywa nazywana FIFO, czyli First-in First-out - pierwszy na wejściu, pierwszy na wyjściu. Podobnie jak w przypadku stosu, operacje dodawania oraz usuwania w kolejce również mają zwyczajowe nazwy.

Budowa kolejki

Omówmy teraz jak powinna wyglądać procedura CREATE w przypadku kolejki. W zamyśle ta struktura powinna zawierać dwa pola front oraz back, które byłby wskaźnikami do początku i końca naszej kolejki. Od razu nasuwa się analogia do tego jak zbudowana jest lista, z tym, że w tym wypadku powinna zawierać nie tylko pole head, ale i jakieś pole tail wskazujące na końcowy element. Graficznie kolejka miałaby wszystkie elementy, które są na obrazku obok.

Kolejka

• ENQUEUE(d: Data) - (zakolejkuj) dodaje rekord d na koniec kolejki
• DEQUEUE() - ("odkolejkuj") usuwa element z przodu kolejki

Dodatkowe informacje

Należy pamiętać, że kolejka jest strukturą "wziętą z życia", która jest bardzo pomocna przy rozwiązywaniu problemów synchronizacyjnych. Żeby to zrozumieć można sobie wyobrazić sklep z jedną kasą, i bardzo dużą ilością klientów, naturalną rzeczą jest to, że klienci zaczną się ustawiać w kolejkę i właśnie w ten sposób będą podchodzić do kasy. W dalszej części książki opowiemy nieco dokładniej jak system operacyjny wykorzystuje kolejki.

Implementacja

W praktyce dobrym pomysłem jak chodzi o implementację kolejki jest zwykła tablica, ale z dostępem pomyślanym w nieco inny sposób. Implementacja listowa zawsze daje dodatkowy narzut pamięciowy ze względu wykorzystywania wskaźników, więc można to traktować jako pewną optymalizację.

Jeśli założymy, że ostatni element tablicy znajduje się zaraz przed pierwszym to będziemy mieć do czynienia z czymś co nazywamy tablicą cykliczną. Możemy uzyskać taki efekt korzystając z operacji modulo na indeksach zwykłej tablicy.

Ilustracja działania kolejki na tablicy cyklicznej

Poruszanie się po tej tablicy będzie realizowane za sprawą dwóch wskaźników odpowiadających polom front i back. Przy czym, zakładamy, że wskaźnik front wskazuje na pierwsze puste miejsce. Back pokazuje pierwszy element w zbiorze.

Operacja ENQUEUE polegać będzie na zapisie nowej wartości w tablicy i inkrementacji wskaźnika back modulo wielkość tablicy. DEQUEUE z kolei będzie przesuwaniem wskaźnika (inkrementacją modulo wielkość tablicy) front i wypisywaniem wartości, na którą przed chwilą wskazywał.

To czy kolejka jest pełna będzie można bardzo łatwo wywnioskować z pozycji front i back, jeśli będą sobie równe będzie to oznaczać, że tablica, w której zapisujemy jest pełna. W zależności od implementacji, można zwrócić błąd przepełnienia (jak my w implementacji z dodatku) lub na przykład dynamicznie powiększyć tablicę.

Typy kolejek

• Kolejka podwójna
• Kolejka priorytetowa

Ćwiczenia

Podstawowe

Ćwiczenie 1: Napisz implementację kolejki za pomocą

1. tablicy cyklicznej
2. listy

Ćwiczenie 2: Napisz optymalną implementację kolejki, która dynamicznie będzie przydzielać nową pamięć w przypadku jej braku.