Python Kø: FIFO, LIFO Eksempel
Hva er Python Kø?
En kø er en beholder som inneholder data. Dataene som legges inn først vil bli fjernet først, og derfor kalles en kø også "First in First Out" (FIFO). Køen har to ender foran og bak. Varene legges inn fra baksiden og fjernes fra forsiden.
Hvordan gjør Python Kø arbeid?
Køen kan enkelt sammenlignes med det virkelige eksemplet, køen av mennesker som står i kø ved billettskranken, personen som står først får billetten først, etterfulgt av neste person og så videre. Den samme logikken gjelder også for kødatastrukturen.
Her er en diagrammatisk representasjon av køen:
De Bak representerer punktet der elementene settes inn i køen. I dette eksemplet er 7 verdien for det.
De Front representerer punktet hvor elementene fra køen vil bli fjernet. Fjerner du en vare fra køen, er det første elementet du får 1, som vist på figuren.
Vare 1 var den første som ble satt inn i køen, og mens den fjernes er den den første som kommer ut. Derfor kalles køen FØRST INN FØRST UT (FIFO)
I en kø fjernes varene i rekkefølge og kan ikke fjernes i mellom. Du kan bare ikke fjerne element 5 tilfeldig fra køen, for å gjøre det må du fjerne alle elementene før 5. Elementene i køen vil bli fjernet i den rekkefølgen de settes inn.
Typer kø i Python
Det er hovedsakelig to typer kø i Python:
- Først inn først ut-kø: For dette vil elementet som går først være det første som kommer ut. For å jobbe med FIFO, må du ringe Kø() klasse fra kømodul.
- Sist inn først ut-kø: Her vil elementet som legges inn sist være det første som kommer ut. For å jobbe med LIFO, må du ringe LifoQueue() klasse fra kømodulen.
Python kø Installasjon
Det er veldig enkelt å jobbe med kø i python. Her er trinnene du må følge for å bruke kø i koden din.
Trinn 1) Du trenger bare å importere kømodulen, som vist nedenfor:
import queue
Modulen er tilgjengelig som standard med python, og du trenger ingen ekstra installasjon for å begynne å jobbe med køen. Det er 2 typer kø-FIFO (først inn først ut) og LIFO (sist inn først ut).
Trinn 2) For å jobbe med FIFO-kø, kall opp Queue-klassen ved å bruke kømodulen importert som vist nedenfor:
import queue q1 = queue.Queue()
Trinn 3) For å jobbe med LIFO-kø ring klassen LifoQueue() som vist nedenfor:
import queue q1 = queue.LifoQueue()
Metoder tilgjengelig i Queue- og LifoQueue-klassen
Følgende er de viktige metodene som er tilgjengelige i Queue- og LifoQueue-klassen:
- put(item): Dette vil plassere varen i køen.
- bli(): Dette vil returnere deg en vare fra køen.
- tømme(): Den vil returnere sann hvis køen er tom og falsk hvis varer er tilstede.
- qsize(): returnerer størrelsen på køen.
- full(): returnerer sant hvis køen er full, ellers usant.
Eksempel på først inn først ut-kø
Ved først inn først ut vil elementet som går først være det første som kommer ut.
Legg til og element i en kø
La oss jobbe med et eksempel for å legge til et element i en kø. For å begynne å jobbe med køen, importer først modulkøen, som vist i eksemplet nedenfor.
For å legge til et element kan du bruke 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 legge til et hvilket som helst antall elementer til den. I tilfelle du ønsker å definere størrelsen på køen kan det samme gjø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.
Utgang:
True
Nå er størrelsen på køen 5, og det vil ikke ta mer enn 5 elementer, og metoden q1.full() vil returnere true. Å legge til flere elementer vil ikke kjøre koden lenger.
Fjern en vare fra køen
For å fjerne et element fra køen kan du bruke metoden som heter get(). Denne metoden tillater elementer fra køen når de kalles.
Følgende eksempel viser hvordan du fjerner et element fra køen.
import queue q1 = queue.Queue() q1.put(10) item1 = q1.get() print('The item removed from the queue is ', item1)
Utgang:
The item removed from the queue is 10
Eksempel på sist inn først ut kø
Ved sist i første ut-kø, vil elementet som legges inn sist være det første som kommer ut.
For å jobbe med LIFO, dvs. sist i første ut-kø, må vi importere kømodulen og bruke LifoQueue()-metoden.
Legg til og element i en kø
Her vil vi forstå hvordan du legger til en vare i LIFO-køen.
import queue q1 = queue.LifoQueue() q1.put(10)
Du må bruke put()-metoden på LifoQueue, som vist i eksemplet ovenfor.
Fjern en vare fra køen
For å fjerne et element fra LIFO-køen kan du bruke get()-metoden .
import queue q1 = queue.LifoQueue() q1.put(10) item1 = q1.get() print('The item removed from the LIFO queue is ', item1)
Utgang:
The item removed from the LIFO queue is 10
Legg til mer enn 1 element i en kø
I eksemplene ovenfor har vi sett hvordan du legger til et enkelt element og fjerner elementet for FIFO og LIFOqueue. Nå skal vi se hvordan du legger til mer enn ett element og også fjerner det.
Legg til 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.
Utgang:
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
Legg til og element 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 et element 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.
Utgang:
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 som brukes for 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()
Utgang:
3 4 5 10 11 21
Reversing kø
For å snu køen kan du benytte deg av en annen kø og rekursjon.
Følgende eksempel viser hvordan du får køen reversert.
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()
Utgang:
10 3 21 4 5 11
Oppsummering
- En kø er en beholder som inneholder data. Det er to typer kø, FIFO og LIFO.
- For en FIFO (First in First Out Queue), vil elementet som går først være det første som kommer ut.
- For en LIFO (Last in First Out Queue) vil elementet som legges inn sist være det første som kommer ut.
- Et element i en kø legges til ved å bruke put(item)-metoden.
- For å fjerne et element, brukes get()-metoden.