Kolejka

Małgorzata Piekarska

Wstęp

Jeżeli nowy składnik dodajemy zawsze na końcu listy, zaś po przetworzeniu usuwamy z listy jej pierwszy składnik, to taką strukturę nazywamy kolejką. Kolejkę łatwo wyobrazić sobie, gdyż jest podobna do tej w sklepie, w której obowiązuje zasada, że jako pierwszy opuszcza kolejkę ten, kto przebywa w niej najdłużej. Zasadę tą często formułuje się krótko: pierwszy przyszedł, pierwszy wychodzi (First In First Out - FIFO)

Rozróżniamy następujące elementarne operacje na kolejce:

• Sprawdzenie, czy kolejka jest pusta (funkcja, która zwraca true, jeśli kolejka jest pusta, w przeciwnym razie zwraca false),
• Odczyt elementu z początku kolejki (funkcja, która zwraca wskaźnik do pierwszego elementu w kolejce),
• Wstawienie nowego elementu na koniec kolejki (funkcja, która dodaje nowy element na koniec kolejki),
• Usunięcie elementu z kolejki (funkcja, która usuwa z kolejki pierwszy element).