Python Kolejka: FIFO, LIFO Przykład
Logana Younga
Co to jest Python Kolejka?
Kolejka to kontener przechowujący dane. Dane wprowadzone jako pierwsze zostaną usunięte w pierwszej kolejności, dlatego kolejka nazywana jest także „pierwsze weszło, pierwsze wyszło” (FIFO). Kolejka ma dwa końce z przodu i z tyłu. Elementy są wprowadzane od tyłu i wyjmowane od przodu.
W jaki sposób Python Praca w kolejce?
Kolejkę można łatwo porównać z przykładem z życia codziennego: kolejką osób czekających w kolejce przy kasie biletowej, osoba stojąca pierwsza otrzyma bilet jako pierwsza, po niej następna osoba i tak dalej. Ta sama logika dotyczy również struktury danych kolejki.
Oto schematyczne przedstawienie kolejki:
Kurs Tył reprezentuje punkt, w którym elementy są wstawiane do kolejki. W tym przykładzie wartością jest 7.
Kurs Przód reprezentuje punkt, w którym elementy z kolejki zostaną usunięte. Jeśli usuniesz element z kolejki, pierwszym elementem, który otrzymasz, będzie 1, jak pokazano na rysunku.
Pozycja 1 jako pierwsza została wstawiona do kolejki, a przy jej usuwaniu jako pierwsza wyszła. Stąd kolejka nazywa się FIRST IN FIRST OUT (FIFO)
W kolejce elementy są usuwane po kolei i nie można ich usunąć pomiędzy nimi. Po prostu nie możesz losowo usunąć pozycji 5 z kolejki. Aby to zrobić, będziesz musiał usunąć wszystkie pozycje przed 5. Pozycje w kolejce zostaną usunięte w kolejności, w jakiej zostały wstawione.
Rodzaje kolejek Python
Istnieją głównie dwa rodzaje kolejek Python:
- Kolejka First in First out: W tym celu element, który pojawi się jako pierwszy, będzie pierwszym, który wyjdzie. Aby pracować z FIFO, musisz wywołać Kolejka() klasa z modułu kolejki.
- Ostatni w kolejce, pierwszy na wyjściu: Tutaj element wprowadzony jako ostatni będzie pierwszym, który wyjdzie. Aby pracować z LIFO, musisz wywołać LifoQueue() class z modułu kolejki.
Python Instalacja kolejki
Praca z kolejką w Pythonie jest bardzo łatwa. Oto kroki, które należy wykonać, aby skorzystać z kolejki w kodzie.
Krok 1) Wystarczy zaimportować moduł kolejki, jak pokazano poniżej:
import queue
Moduł jest domyślnie dostępny z Pythonem i nie potrzebujesz żadnej dodatkowej instalacji, aby rozpocząć pracę z kolejką. Istnieją 2 typy kolejek FIFO (pierwszy na wejściu, pierwszy na wyjściu) i LIFO (ostatni na wejściu, pierwszy na wyjściu).
Krok 2) Aby pracować z kolejką FIFO, wywołaj klasę Queue, korzystając z zaimportowanego modułu kolejki, jak pokazano poniżej:
import queue q1 = queue.Queue()
Krok 3) Aby pracować z kolejką LIFO, wywołaj klasę LifoQueue(), jak pokazano poniżej:
import queue q1 = queue.LifoQueue()
Metody dostępne wewnątrz klas Queue i LifoQueue
Poniżej przedstawiono ważne metody dostępne w klasie Queue i LifoQueue:
- umieścić (przedmiot): Spowoduje to umieszczenie elementu w kolejce.
- Dostawać(): Spowoduje to zwrócenie elementu z kolejki.
- pusty(): Zwróci wartość true, jeśli kolejka jest pusta, i false, jeśli elementy są obecne.
- qrozmiar(): zwraca rozmiar kolejki.
- pełny(): zwraca wartość true, jeśli kolejka jest pełna, w przeciwnym wypadku zwraca wartość false.
Przykład kolejki „pierwszy na wejściu, pierwszy na wyjściu”.
W przypadku zasady „pierwsze weszło, pierwsze wyszło” element, który wystartuje jako pierwszy, jako pierwszy wyjdzie.
Dodaj i umieść w kolejce
Popracujmy nad przykładem dodania elementu do kolejki. Aby rozpocząć pracę z kolejką, należy najpierw zaimportować kolejkę modułu, jak pokazano w poniższym przykładzie.
Aby dodać element, możesz skorzystać z metody put(), jak pokazano w przykładzie:
import queue q1 = queue.Queue() q1.put(10) #this will additem 10 to the queue.
Domyślnie rozmiar kolejki jest nieskończony i możesz dodać do niej dowolną liczbę pozycji. Jeśli chcesz zdefiniować rozmiar kolejki, możesz to zrobić w następujący sposób
import queue q1 = queue.Queue(5) #The max size is 5. q1.put(1) q1.put(2) q1.put(3) q1.put(4) q1.put(5) print(q1.full()) # will return true.
Wyjście:
True
Teraz rozmiar kolejki wynosi 5 i nie zajmie ona więcej niż 5 pozycji, a metoda q1.full() zwróci wartość true. Dodanie kolejnych elementów nie spowoduje dalszego wykonania kodu.
Usuń element z kolejki
Aby usunąć element z kolejki, możesz użyć metody zwanej get(). Ta metoda pozwala na wywołanie elementów z kolejki.
Poniższy przykład pokazuje, jak usunąć element z kolejki.
import queue
q1 = queue.Queue()
q1.put(10)
item1 = q1.get()
print('The item removed from the queue is ', item1)
Wyjście:
The item removed from the queue is 10
Przykład kolejki „Ostatni na wejściu, pierwszy na wyjściu”.
W przypadku ostatniego w kolejce pierwszego wyjścia, element wprowadzony jako ostatni będzie pierwszym, który wyjdzie.
Aby pracować z LIFO, czyli być ostatnim w pierwszej kolejce wyjściowej, musimy zaimportować moduł kolejki i skorzystać z metody LifoQueue().
Dodaj i umieść w kolejce
Tutaj zrozumiemy, jak dodać element do kolejki LIFO.
import queue q1 = queue.LifoQueue() q1.put(10)
Musisz użyć metody put() na LifoQueue, jak pokazano w powyższym przykładzie.
Usuń element z kolejki
Aby usunąć element z kolejki LIFOqueue, możesz skorzystać z metody get().
import queue
q1 = queue.LifoQueue()
q1.put(10)
item1 = q1.get()
print('The item removed from the LIFO queue is ', item1)
Wyjście:
The item removed from the LIFO queue is 10
Dodaj więcej niż 1 element do kolejki
W powyższych przykładach widzieliśmy, jak dodać pojedynczy element i usunąć element dla FIFO i LIFOqueue. Teraz zobaczymy, jak dodać więcej niż jeden element, a także go usunąć.
Dodaj i umieść element w kolejce FIFO
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Usuń element z kolejki FIFO
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.
Wyjście:
The value is 0 The value is 1 The value is 2 The value is 3 The value is 4 The value is 5 The value is 6 The value is 7 The value is 8 The value is 9 The value is 10 The value is 11 The value is 12 The value is 13 The value is 14 The value is 15 The value is 16 The value is 17 The value is 18 The value is 19
Dodaj i umieść element w kolejce LIFOqueue
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Usuń element z kolejki LIFOqueue
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.
Wyjście:
The value is 19 The value is 18 The value is 17 The value is 16 The value is 15 The value is 14 The value is 13 The value is 12 The value is 11 The value is 10 The value is 9 The value is 8 The value is 7 The value is 6 The value is 5 The value is 4 The value is 3 The value is 2 The value is 1 The value is 0
Kolejka sortowania
Poniższy przykład ilustruje sortowanie kolejki. Do sortowania wykorzystano algorytm sortowania bąbelkowego.
import queue
q1 = queue.Queue()
#Addingitems to the queue
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)
#using bubble sort on the queue
n = q1.qsize()
for i in range(n):
x = q1.get() # the element is removed
for j in range(n-1):
y = q1.get() # the element is removed
if x > y :
q1.put(y) #the smaller one is put at the start of the queue
else:
q1.put(x) # the smaller one is put at the start of the queue
x = y # the greater one is replaced with x and compared again with nextelement
q1.put(x)
while (q1.empty() == False):
print(q1.queue[0], end = " ")
q1.get()
Wyjście:
3 4 5 10 11 21
Revkolejka do kasowania
Aby odwrócić kolejkę, możesz skorzystać z innej kolejki i rekurencji.
Poniższy przykład pokazuje, jak odwrócić kolejkę.
Przykład:
import queue
q1 = queue.Queue()
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)
def reverseQueue (q1src, q2dest) :
buffer = q1src.get()
if (q1src.empty() == False) :
reverseQueue(q1src, q2dest) #using recursion
q2dest.put(buffer)
return q2dest
q2dest = queue.Queue()
qReversed = reverseQueue(q1,q2dest)
while (qReversed.empty() == False):
print(qReversed.queue[0], end = " ")
qReversed.get()
Wyjście:
10 3 21 4 5 11
Podsumowanie
- Kolejka to kontener przechowujący dane. Istnieją dwa typy kolejek: FIFO i LIFO.
- W przypadku FIFO (pierwszy w kolejce, pierwszy na wyjściu) element, który pojawi się jako pierwszy, będzie pierwszym, który wyjdzie.
- W przypadku kolejki LIFO (ostatni w kolejce, pierwszy wyszedł) element wprowadzony jako ostatni będzie pierwszym, który wyjdzie.
- Pozycję w kolejce dodaje się metodą put(item).
- Aby usunąć element, używana jest metoda get().
