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:

Python Køarbeid

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)

Python Køarbeid

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.