Kolejka (queue)

Słownik kwalifikacji INF.04 - Projektowanie, programowanie i testowanie aplikacji

Co to jest kolejka?

Kolejka (queue) to liniowa struktura danych, w której element dodany jako pierwszy jest obsługiwany jako pierwszy. Działa według zasady FIFO (First In, First Out) — „pierwszy wszedł, pierwszy wyszedł”.

Podstawowe operacje

  • enqueue — dodanie elementu na koniec kolejki,
  • dequeue — pobranie i usunięcie elementu z początku kolejki,
  • peek / front — podejrzenie pierwszego elementu bez usuwania,
  • isEmpty — sprawdzenie, czy kolejka jest pusta.

Przykład działania

Jeśli dodamy kolejno elementy:

  1. A
  2. B
  3. C

To jako pierwszy zostanie pobrany element A, ponieważ został dodany najwcześniej.

enqueue(A)
enqueue(B)
enqueue(C)
dequeue() -> A
dequeue() -> B
dequeue() -> C

Zastosowania kolejki

Kolejki są używane tam, gdzie ważna jest kolejność zgłoszeń lub zadań, np.:

  • obsługa zadań do wykonania,
  • kolejki wydruku,
  • systemy kolejkowania klientów,
  • buforowanie danych,
  • algorytmy przeszukiwania grafu, np. BFS.

Różnica między kolejką a stosem

Kolejka działa według zasady FIFO, a stos według zasady LIFO. Jeśli trzeba pobrać element dodany najwcześniej, używa się kolejki. Jeśli trzeba pobrać element dodany ostatnio, używa się stosu.