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).
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License