Python Kø: FIFO, LIFO Eksempel
Logan Young
Hvad er Python Kø?
En kø er en container, der indeholder data. De data, der indtastes først, vil blive fjernet først, og derfor kaldes en kø også "First in First Out" (FIFO). Køen har to ender foran og bagved. Varerne indtastes bagfra og fjernes fra forsiden.
Hvordan Python Kø arbejde?
Køen kan let sammenlignes med eksemplet fra den virkelige verden, rækken af mennesker, der venter i en kø ved billetskranken, den person, der står først, får billetten først, efterfulgt af den næste person og så videre. Den samme logik gælder også for køens datastruktur.
Her er en diagrammatisk fremstilling af køen:
Rear repræsenterer det punkt, hvor elementerne er indsat i køen. I dette eksempel er 7 værdien for det.
Front repræsenterer det punkt, hvor emnerne fra køen vil blive fjernet. Fjerner du en vare fra køen, er det første element, du får, 1, som vist på figuren.
Vare 1 var den første, der blev indsat i køen, og mens den fjernes, er den den første, der kommer ud. Derfor kaldes køen FIRST IN FIRST OUT (FIFO)
I en kø fjernes varerne i rækkefølge og kan ikke fjernes ind imellem. Du kan bare ikke fjerne element 5 tilfældigt fra køen, for at gøre det skal du fjerne alle elementer før 5. Varerne i køen vil blive fjernet i den rækkefølge, de indsættes.
Typer af kø i Python
Der er hovedsageligt to typer kø i Python:
- Først i først ud-kø: Til dette vil det element, der går først, være det første, der kommer ud. For at arbejde med FIFO skal du kalde Kø() klasse fra kømodul.
- Sidst ind først ud-kø: Herovre vil det element, der indtastes sidst, være det første, der kommer ud. For at arbejde med LIFO skal du ringe LifoQueue() klasse fra kømodulet.
Python kø Installation
Det er meget nemt at arbejde med kø i python. Her er de trin, du skal følge for at gøre brug af kø i din kode.
Trin 1) Du skal blot importere kømodulet, som vist nedenfor:
import queue
Modulet er tilgængeligt som standard med python, og du behøver ingen yderligere installation for at begynde at arbejde med køen. Der er 2 typer kø-FIFO (først ind først ud) og LIFO (sidst ind først ud).
Trin 2) For at arbejde med FIFO-kø skal du kalde klassen Queue ved hjælp af kømodulet importeret som vist nedenfor:
import queue q1 = queue.Queue()
Trin 3) For at arbejde med LIFO-kø skal du kalde klassen LifoQueue() som vist nedenfor:
import queue q1 = queue.LifoQueue()
Metoder tilgængelige i Queue- og LifoQueue-klassen
Følgende er de vigtige metoder, der er tilgængelige i Queue- og LifoQueue-klassen:
- put(emne): Dette vil sætte varen i køen.
- få(): Dette vil returnere dig en vare fra køen.
- tom(): Det vil returnere sandt, hvis køen er tom og falsk, hvis der er varer til stede.
- qsize(): returnerer størrelsen på køen.
- fuld(): returnerer sand, hvis køen er fuld, ellers falsk.
Eksempel på First In First Out Queue
I tilfælde af først ind først ud, vil det element, der går først, være det første, der kommer ud.
Tilføj og vare i en kø
Lad os arbejde på et eksempel for at tilføje et element i en kø. For at begynde at arbejde med køen skal du først importere modulkøen, som vist i eksemplet nedenfor.
For at tilføje et element kan du bruge put() metoden som vist i eksemplet:
import queue q1 = queue.Queue() q1.put(10) #this will additem 10 to the queue.
Som standard er størrelsen på køen uendelig, og du kan tilføje et hvilket som helst antal elementer til den. Hvis du ønsker at definere størrelsen af køen, kan det samme gøres som følger
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.
Output:
True
Nu er køens størrelse 5, og det vil ikke tage mere end 5 elementer, og metoden q1.full() vil returnere sand. Tilføjelse af flere elementer vil ikke udføre koden yderligere.
Fjern en vare fra køen
For at fjerne et element fra køen kan du bruge metoden kaldet get(). Denne metode tillader elementer fra køen, når de kaldes.
Følgende eksempel viser, hvordan du fjerner en vare fra køen.
import queue
q1 = queue.Queue()
q1.put(10)
item1 = q1.get()
print('The item removed from the queue is ', item1)
Output:
The item removed from the queue is 10
Sidst ind først ud kø Eksempel
I tilfælde af sidst i køen først ud, vil det element, der indtastes sidst, være det første, der kommer ud.
For at arbejde med LIFO, dvs. sidst i køen først ud, skal vi importere kømodulet og gøre brug af LifoQueue() metoden.
Tilføj og vare i en kø
Her vil vi forstå, hvordan man tilføjer en vare til LIFO-køen.
import queue q1 = queue.LifoQueue() q1.put(10)
Du skal bruge put() metoden på LifoQueue, som vist i ovenstående eksempel.
Fjern en vare fra køen
For at fjerne et element fra LIFO-køen kan du bruge get() metoden.
import queue
q1 = queue.LifoQueue()
q1.put(10)
item1 = q1.get()
print('The item removed from the LIFO queue is ', item1)
Output:
The item removed from the LIFO queue is 10
Tilføj mere end 1 vare i en kø
I ovenstående eksempler har vi set, hvordan man tilføjer et enkelt element og fjerner elementet for FIFO og LIFOqueue. Nu vil vi se, hvordan du tilføjer mere end et element og også fjerner det.
Tilføj og element i en FIFO-kø
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Fjern et element fra FIFO-køen
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.
Output:
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
Tilføj og vare i en LIFO-kø
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Fjern en vare fra LIFO-køen
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.
Output:
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
Sorteringskø
Følgende eksempel viser køsortering. Algoritmen, der bruges til sortering, er boblesortering.
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()
Output:
3 4 5 10 11 21
Reversing Kø
For at vende køen kan du gøre brug af en anden kø og rekursion.
Følgende eksempel viser, hvordan man får vendt køen.
Eksempel:
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()
Output:
10 3 21 4 5 11
Resumé
- En kø er en container, der indeholder data. Der er to typer kø, FIFO og LIFO.
- For en FIFO (First in First Out Queue) vil det element, der går først, være det første, der kommer ud.
- For en LIFO (Last in First Out Queue) vil det element, der indtastes sidst, være det første, der kommer ud.
- Et element i en kø tilføjes ved hjælp af put(item) metoden.
- For at fjerne et element, bruges get() metoden.
