Rc3eHnGputwzz
Fotografia przedstawia falującą wodę.

PY_I_R_W13B_M05 Dynamiczne struktury danych. Implementacja

Źródło: Michael Benz, dostępny w internecie: unsplash.com, domena publiczna.

Jak zaimplementować kolejkę w Pythonie za pomocą listy

Kolejka (queue) to struktura danych działająca na zasadzie FIFOFirst In, First Out, czyli „pierwszy wchodzi, pierwszy wychodzi”.
Kolejki znajdują zastosowanie w:

  • obsłudze zadań w systemach operacyjnych (kolejka procesów),

  • symulacjach kolejek w sklepach czy bankach,

  • algorytmach przeszukiwania wszerz (BFS),

  • zarządzaniu zadaniami w programach i wątkach.

Pythonowa lista (list) umożliwia stworzenie kolejki, ale trzeba uważać na efektywność operacji.

Podstawowe operacje kolejki

Kolejka powinna obsługiwać:

  1. enqueue(x) – dodanie elementu na koniec kolejki

  2. dequeue() – usunięcie elementu z początku kolejki

  3. peek() / front() – podejrzenie elementu na początku kolejki

  4. is_empty() – sprawdzenie czy kolejka jest pusta

Implementacja kolejki za pomocą listy

Linia 1. kolejka znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 3. kratka enqueue – dodanie na koniec. Linia 4. kolejka kropka append otwórz nawias okrągły cudzysłów A cudzysłów zamknij nawias okrągły. Linia 5. kolejka kropka append otwórz nawias okrągły cudzysłów B cudzysłów zamknij nawias okrągły. Linia 6. kolejka kropka append otwórz nawias okrągły cudzysłów C cudzysłów zamknij nawias okrągły. Linia 8. kratka zdjęcie z początku. Linia 9. pierwszy znak równości kolejka kropka pop otwórz nawias okrągły 0 zamknij nawias okrągły kratka usuwa i zwraca apostrof A apostrof. Linia 10. print otwórz nawias okrągły cudzysłów Usunięto dwukropek cudzysłów przecinek pierwszy zamknij nawias okrągły. Linia 12. kratka peek – element na początku. Linia 13. print otwórz nawias okrągły cudzysłów Pierwszy w kolejce dwukropek cudzysłów przecinek kolejka otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły. Linia 15. kratka is podkreślnik empty. Linia 16. print otwórz nawias okrągły cudzysłów Czy kolejka jest pusta znak zapytania cudzysłów przecinek len otwórz nawias okrągły kolejka zamknij nawias okrągły znak równości znak równości 0 zamknij nawias okrągły.