Podobnie jak stos, kolejka jest liniową strukturą danych, która przechowuje elementy w kolejności „pierwsze weszło, pierwsze wyszło” ( FIFO ) sposób. W przypadku kolejki ostatnio dodany element jest usuwany jako pierwszy. Dobrym przykładem kolejki jest dowolna kolejka konsumentów do zasobu, w której konsument, który przyszedł pierwszy, jest obsługiwany jako pierwszy.

Operacje związane z kolejką to:

• Kolejka: Dodaje element do kolejki. Jeśli kolejka jest pełna, mówimy o stanie przepełnienia – złożoność czasowa: O(1)
• Odpowiednio: Usuwa element z kolejki. Elementy są wysuwane w tej samej kolejności, w jakiej są wypychane. Jeśli kolejka jest pusta, mówimy o stanie niedomiaru – złożoność czasowa: O(1)
• Przód: Pobierz element czołowy z kolejki – Złożoność czasowa: O(1)
• Tył: Pobierz ostatni element z kolejki – Złożoność czasowa: O(1)

Zaimplementuj kolejkę w Pythonie

Istnieją różne sposoby implementacji kolejki Pyton. W tym artykule omówiono implementację kolejki przy użyciu struktur danych i modułów z biblioteki Python. Kolejkę Pythona można zaimplementować na następujące sposoby:

dyskietka

• lista
• kolekcje.deque
• ogon.ogon

Implementacja za pomocą listy

Lista to wbudowana w Python strukturę danych, której można używać jako kolejki. Zamiast enqueue() i odpowiednio () , dodać() I Muzyka pop() funkcja jest używana. Jednak listy są w tym celu dość powolne, ponieważ wstawienie lub usunięcie elementu na początku wymaga przesunięcia wszystkich pozostałych elementów o jeden, co wymaga czasu O(n).
Kod symuluje kolejkę przy użyciu listy w języku Python. Dodaje elementy 'A' , 'B' , I 'C' do kolejki, a następnie usuwa je z kolejki, w wyniku czego na końcu kolejka jest pusta. Dane wyjściowe pokazują kolejkę początkową, elementy usunięte z kolejki ( 'A' , 'B' , 'C' ) i stan pustej kolejki.

Python3

>

>

Wyjście:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements []>

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list>

Implementacja przy użyciu Collections.deque

Kolejkę w Pythonie można zaimplementować przy użyciu klasy deque z modułu kolekcji. Deque jest preferowany w stosunku do list w przypadkach, gdy potrzebujemy szybszych operacji dołączania i pop z obu końców kontenera, ponieważ deque zapewnia złożoność czasową O(1) dla operacji dołączania i pop w porównaniu z listą, która zapewnia złożoność czasową O(n) . Zamiast kolejkowania i deque używane są funkcje append() i popleft().
W kodzie zastosowano adeque>zcollections>moduł reprezentujący kolejkę. Dołącza 'A' , 'B' , I 'C' do kolejki i usuwa je z kolejki q.popleft()> , co spowoduje pustą kolejkę. Bez komentarza q.popleft()> po opróżnieniu kolejki wywoła anIndexError>. Kod demonstruje operacje na kolejce i obsługuje scenariusz pustej kolejki.

Python3

lista tablic Java

numer Armstronga

>

>

Wyjście:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([])>

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque>

Implementacja z wykorzystaniem kolejki.Kolejka

Kolejka to wbudowany moduł Pythona, który służy do implementacji kolejki. kolejka.Queue(maxsize) inicjuje zmienną do maksymalnego rozmiaru maxsize. Maksymalny rozmiar wynoszący zero „0” oznacza nieskończoną kolejkę. Ta kolejka jest zgodna z regułą FIFO.
W module tym dostępne są różne funkcje:

• największy rozmiar – Liczba pozycji dozwolonych w kolejce.
• pusty() – Zwraca True, jeśli kolejka jest pusta, w przeciwnym razie False.
• pełny() – Zwróć True, jeśli w kolejce znajdują się pozycje o maksymalnym rozmiarze. Jeśli kolejka została zainicjowana wartością maxsize=0 (wartość domyślna), funkcja full() nigdy nie zwraca wartości True.
• Dostawać() – Usuń i zwróć element z kolejki. Jeśli kolejka jest pusta, poczekaj, aż pozycja będzie dostępna.
• get_nowait() – Zwróć przedmiot, jeśli jest natychmiast dostępny, w przeciwnym razie wyświetl QueueEmpty.
• umieścić (przedmiot) – Umieść przedmiot w kolejce. Jeśli kolejka jest pełna, poczekaj, aż zwolni się wolne miejsce, zanim dodasz przedmiot.
• put_nowait(przedmiot) – Umieść przedmiot w kolejce bez blokowania. Jeśli żadne wolne miejsce nie jest od razu dostępne, podnieś QueueFull.
• qrozmiar() – Zwraca liczbę pozycji w kolejce.

Przykład: Ten kod wykorzystujeQueue>klasa zqueue>moduł. Zaczyna się od pustej kolejki i wypełnia ją komunikatem „ A', 'B' , I 'C' . Po usunięciu z kolejki kolejka staje się pusta i dodawana jest cyfra 1. Mimo że wcześniej była pusta, pozostaje pełna, ponieważ maksymalny rozmiar jest ustawiony na 3. Kod demonstruje operacje na kolejce, w tym sprawdzanie zapełnienia i pustki.

Python3

kolejka i kolejka priorytetowa w Javie

>

>

Wyjście:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False>