Som du allerede har studert om viktigheten av datastrukturer i forrige artikkel, kan vi dykke rett i emnet for artikkelen, dvs. kødatastruktur. Jeg skal diskutere følgende emner:
- Behov for kødatastruktur
- Daglige liv Eksempler på kø
- Opprette en kødatastruktur
- En kø
- Avkjøring
- Søknader om kø
Behov for kødatastruktur
Anta at du vil ha en film en dag. I multipleksen ble billettene utstedt på først-til-mølla-basis, og folk sto bak hverandre og ventet på sin tur. Så hva vil du gjøre?? Du må ha gått bak og stått bak den siste personen som ventet på billetten.
Her står folket bak hverandre og de betjenes basert på First-in-First-Out (FIFO) mekanisme. En slik ordning er kjent som en Kø.
Daglige liv Eksempler på kø
La oss se på noen eksempler der vi ser kø som fungerer i det daglige:
- Telefonsvarer- Personen som ringer først på gadgeten din, blir først møtt.
- Bagasjekontrollmaskin - Sjekker bagasjen som har blitt oppbevart først på transportbåndet.
- Kjøretøy på avgiftsbrua - Kjøretøyene som ankommer tidlig går først.
- Telefonsenter - telefonsystemer vil bruke køer for å holde folk som ringer dem i orden, til en servicerepresentant er gratis.
Alle disse eksemplene følger Først-inn-siste-ut strategi.
Opprette en kødatastruktur
Bortsett fra komplementære operasjoner, kan jeg si at de viktigste operasjonene som er mulige i køen er:
en. En kø eller legg til et element på slutten av køen.
2. Avkjøring eller fjern et element fra forsiden av køen
La oss nå starte med å lage klassekø i Python:
klasse Kø: def __init __ (selv, max_size): selv .__ max_size = max_size selv .__ elementer = [Ingen] * selv .__ max_size selv .__ bak = -1 selv .__ front = 0
- maks. størrelse er det maksimale antall elementer som forventes i køen.
- Elementer i køen lagres i pythonlisten
- bak indikerer indeksposisjonen til det siste elementet i køen.
- Baksiden blir først tatt til -1 fordi køen er tom
- Front indikerer plasseringen til det første elementet i køen.
- Fronten blir til å være 0 i utgangspunktet fordi den alltid vil peke på det første elementet i køen
Enqueue
Nå, når du prøver å innhente elementer i køen, må du huske følgende punkter:
- Om det er plass igjen i køen eller ikke, dvs. hvis bak er lik max_size -1
- Den bakre vil peke på det siste elementet satt inn i køen.
Så, hva blir algoritmen ??
#returns max_size of queue def get_max_size (self): return self .__ max_size #returns bool value whether queue is full or not, True if full and False ellers def is_full (self): return self .__ rear == self .__ max_size-1 # setter inn / enqueue data til køen hvis den ikke er full def enqueue (self, data): if (self.is_full ()): print ('Queue is full. No enqueue possible') ellers: self .__ rear + = 1 self. __elements [self .__ rear] = data #display all the content of the kø def display (self): for i in range (0, self .__ rear + 1): print (self .__ elements [i]) #Du kan bruke under __str __ () for å skrive ut elementene i DS-objektet mens feilsøking def __str __ (selv): msg = [] indeks = selv .__ front mens (indeks<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg
Nå, når du utfører følgende:
kø1 = Kø (5)
#Enqueue alle nødvendige element (er).
kø1.enqueue (“A”)
kø1.enqueue (“B”)
kø1.enqueue (“C”)
kø1.enqueue (“D”)
kø1.enqueue (“E”)
kø1.display ()
kø1.enqueue (“F”)
skriv ut (kø1)
Produksjon:
TIL
B
C
D
ER
Køen er full. Ingen omgivelser mulig
Kødata (foran til bak): A B C D E
De-kø
Nå som du har satt inn / innhyllet elementene i køen, vil du dequeue / slette dem forfra, så du må ta vare på følgende:
- Det er elementer i køen, dvs. bak skal ikke være lik -1.
- For det andre må du huske at når elementer slettes fra fronten, så skal fronten økes for å peke neste front etter å ha slettet.
- Fronten skal ikke peke mot slutten av køen, dvs. lik maks_størrelse.
Så, hva blir algoritmen ??
#funksjon for å sjekke om køen er tom eller ikke def er_fri (selv): hvis (selv .__ bak == - 1 eller selv .__ front == selv .__ max_size): retur Sann ellers: returner Falsk # funksjon for å deque et element og return det def dequeue (selv): hvis (self.is_empty ()): skriv ut ('køen er allerede tom') ellers: data = selv .__ elementer [selv .__ front] selv .__ front + = 1 retur data #funksjon for å vise elementer fra foran til bak hvis køen ikke er tom def display (selv): hvis (ikke selv.is_empty ()): for jeg innen rekkevidde (selv .__ foran, selv .__ bak + 1): skriv ut (selv .__ elementer [i]) annet : skriv ut ('tom kø')
Nå når du utfører følgende:
kø1 = Kø (5)
#Enqueue alle nødvendige element (er)
kø1.enqueue (“A”)
kø1.enqueue (“B”)
kø1.enqueue (“C”)
kø1.enqueue (“D”)
kø1.enqueue (“E”)
skriv ut (kø1)
#Dekuer alle nødvendige element (er)
print (“Dequeued:“, queue1.dequeue ())
print (“Dequeued:“, queue1.dequeue ())
print (“Dequeued:“, queue1.dequeue ())
print (“Dequeued:“, queue1.dequeue ())
print (“Dequeued:“, queue1.dequeue ())
print (“Dequeued:“, queue1.dequeue ())
#Vis alle elementene i køen.
kø1.display ()
Produksjon:
Kødata (foran til bak): A B C D E
Dekquert: A
Dekquert: B
Dekquert: C
Dekquert: D
Dequeued: E
køen er allerede tom
Dekquert: Ingen
tom kø
Søknader om kø
Fra nå av har du allerede forstått det grunnleggende om kø. For å dykke dypere, vil vi se på noen av programmene.
- Eksempel 1:
Skriv ut kø i Windows bruker en kø for å lagre alle aktive og ventende utskriftsjobber. Når vi vil skrive ut dokumenter, gir vi utskriftskommandoer etter hverandre. Basert på utskriftskommandoer vil dokumentene bli stilt opp i utskriftskøen. Når skriveren er klar, sendes dokumentet først i første utgang for å få det skrevet ut.
Anta at du har gitt utskriftskommandoer for tre dokumenter i ordren doc1, etterfulgt av doc2 og doc3.
Utskriftskøen fylles ut som vist nedenfor:
doc-n, der doc er dokumentet som sendes for utskrift og n, er antall sider i dokumentet. For eksempel betyr doc2-10 at doc2 skal skrives ut og den har 10 sider. Her er en kode som simulerer utskriftskøoperasjon. Gå gjennom koden og observer hvordan køen brukes i denne implementeringen.
klasse Kø: def __init __ (selv, maks_størrelse): selv .__ max_size = max_size selv .__ elementer = [Ingen] * selv .__ max_size selv .__ bak = -1 selv .__ front = 0 def er_full (selv): hvis (selv .__ bak = = self .__ max_size-1): returner True return False def is_empty (self): if (self .__ front> self .__ rear): return True return False def enqueue (self, data): if (self.is_full ()): skriv ut ('Køen er full !!!') annet: selv .__ bak + = 1 selv .__ elementer [selv .__ bak] = data def dequeue (selv): hvis (self.is_empty ()): skriv ut ('Køen er tom! !! ') annet: data = selv .__ elementer [selv .__ foran] selv .__ foran + = 1 retur data def display (selv): for indeks i rekkevidde (selv .__ foran, selv .__ bak + 1): skriv ut (selv .__ elementer [index]) def get_max_size (self): return self .__ max_size #You can use the below __str __ () to print the elements of the DS object while #debugging def __str __ (self): msg = [] index = self .__ front while (indeks<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg #function that enqueue are the documents to be printed in Queue named print_queue def send_for_print(doc): global print_queue if(print_queue.is_full()): print('Queue is full') else: print_queue.enqueue(doc) print(doc,'sent for printing') #function that prints the document if number of pages of document is less than #total number of pages in printer def start_printing(): global print_queue while(not print_queue.is_empty()): #here we dequeue the Queue and take the coument that was input first for printing. doc=print_queue.dequeue() global pages_in_printer #the aim of this for loop is to find number of pages of the of document which is doc name followed by “-“ for i in range(0,len(doc)): if(doc[i]=='-'): no_of_pages=int(doc[i+1:]) break if(no_of_pages<=pages_in_printer): print(doc,'printed') pages_in_printer-=no_of_pages print('Remaining no. of pages in printer:', pages_in_printer) else: print('Couldn't print',doc[:i],'. Not enough pages in the printer.') pages_in_printer=12 print_queue=Queue(10) send_for_print('doc1-5') send_for_print('doc2-3') send_for_print('doc3-6') start_printing()
Produksjon:
doc1-5 sendt for utskrift
doc2-3 sendt for utskrift
doc3-6 sendt for utskrift
dok1-5 trykt
Gjenværende nr. av sider i skriveren: 7
doc2-3 trykt
Gjenværende nr. av sider i skriveren: 4
Kunne ikke skrive ut doc3. Ikke nok sider i skriveren
- Eksempel 2:
La oss prøve å forstå et annet eksempel som bruker kødatastruktur. Kan du prøve å forstå koden og fortelle hva følgende funksjon gjør?
- def moro (n):
- aqueue = Kø (100)
- for antall i rekkevidde (1, n + 1):
- enqueue (num)
- resultat = 1
- mens (ikke (aqueue.is_empty ())):
- num = AQUUE.DEQUEUE ()
- resultat * = antall
- skriv ut (resultat)
Når funksjons moro () påkalles ved å passere n,
- linje 2 til 4 en-køer elementene fra 1 til n
- linje 5 til 8 finner produktet av disse elementene ved å sette det i kø en etter en
Med dette kommer vi til en slutt på denne kødatastrukturartikkelen. Hvis du med suksess har forstått og kjørt kodene, er du ikke lenger en nybegynner i kødatastruktur.
Har du spørsmål til oss? Vennligst nevn det i kommentarfeltet i denne artikkelen, og vi vil kontakte deg så snart som mulig.
er en mastergrad en doktorgrad
For å få grundig kunnskap om Python sammen med de forskjellige applikasjonene, kan du registrere deg for live med 24/7 support og levetidstilgang.