Kolejka

Każdy z nas miał do czynienia z kolejkąkolejkakolejką w sklepie. Zasada jej działania jest dosyć prosta: osoba, która znajduje się przed nami, pojawiła się wcześniej, a więc zostanie wcześniej obsłużona. Tak samo działa struktura danych zwana kolejką.

Kolejka jest przeciwieństwem stosu, jeśli chodzi o sposób dodawania i usuwania elementów. Nazywamy ją strukturą typu FIFO (z ang. First In First Out, czyli „pierwszy na wejściu, pierwszy na wyjściu”). Nowy element jest dodawany na końcu kolejki. Natomiast jako pierwszy usuwany jest element z początku kolejki.

Kolejka może być wykorzystana np. w teorii grafów w algorytmie przeszukiwania grafu wszerz. 

R1MFOU9MQ1DDA

Schemat kolejki.
Na ilustracja znajdują się prostokąty, od pierwszego wychodzi strzałka dodaj do prostokąta podpisanego jako KONIEC.
Dwa kolejne prostokąty są puste.
Następny prostokąt podpisany jest jako: POCZĄTEK.
Wychodzi od niego strzałka z podpisem usuń skierowana na osobny prostokąt umieszczony pod kolejką.

Tak jak w przypadku stosu, nie możemy użyć indeksowania, aby odwołać się do dowolnych elementów składających się na kolejkę. Jesteśmy w stanie tylko odczytać wartości znajdujące się na jej początku.

Implementacja kolejki z zastosowaniem tablicy

Kolejka także jest strukturą dynamiczną, lecz możemy ją zaimplementować, używając statycznej tablicy. Jedynym ograniczeniem jest maksymalna liczba przechowywanych w kolejce elementów.

Aby kolejka działała poprawnie, konieczne jest użycie dwóch zmiennych. Jedna z nich będzie wskazywała początek kolejki, natomiast druga jej koniec.

RN65A16RLB8FU

Ilustracja przedstawia tablicę podpisaną jako zawartość.
Po polu podpisanym jako koniec kolejki znajdują się liczby: 4, 5, 8.
W kolejnym polu znajduje się strzałka z podpisem: początek kolejki.
Każde z pól posiada swój indeks od 0 do 7 podpisany poniżej tablicy.

Poniżej znajdują się zapisane za pomocą pseudokodu funkcje wykorzystywane podczas dodawania i usuwania elementów kolejki. Zakładamy, że kolejka jest reprezentowana przez tablicę kolejka o rozmiarze $n$ elementów. Indeksy początku oraz końca kolejki są przechowywane w postaci zmiennych indeks_poczatek oraz indeks_koniec. Początkowa wartość indeks_poczatek wynosi $n-1$. Zmienną indeks_koniec inicjalizujemy z kolei wartością o jeden mniejszą, czyli $n-2$. Tablicę indeksujemy od wartości $0$.

Funkcja dodaj_do_kolejki(a):
	jeżeli indeks_koniec = indeks_poczatek wykonaj:
		wypisz("Kolejka jest pełna")
	w przeciwnym razie wykonaj:
		kolejka[indeks_koniec] ← a
		indeks_koniec ← indeks_koniec - 1
        
		jeżeli indeks_koniec < 0:
			indeks_koniec ← n - 1

Funkcja usun_z_kolejki():
	jeżeli indeks_koniec = (indeks_poczatek - 1)
		LUB indeks_poczatek = 0 ORAZ indeks_koniec = n - 1:
		wypisz("Kolejka jest pusta")
	w przeciwnym razie:
		indeks_poczatek ← indeks_poczatek - 1
        
		jeżeli indeks_poczatek < 0:
			indeks_poczatek ← n - 1

Przedstawiony za pomocą pseudokodu program może wydawać się skomplikowany, ponieważ zawiera dużo instrukcji warunkowych. Odpowiadają one za przesuwanie indeksów wskazujących krańce kolejki z początku na koniec tablicy. Dzięki temu nigdy nie wychodzimy poza zakres tablicy w wyniku modyfikacji indeksów.

Dodatkowo indeks_poczatek zawsze wskazuje indeks komórki tablicy za pierwszym elementem. Jest to pewne ułatwienie, które pomaga stwierdzić, kiedy kolejka jest pełna, a kiedy pusta. Jego wadą jest to, że kolejka może przechowywać nie $n$, lecz $n-1$ elementów. Aby dokładniej zrozumieć, dlaczego tak się dzieje, pomocne mogą okazać się aplety dostępne w sekcji „Aplet”, których zadaniem jest wizualizowanie działania kolejki.