Wat is wachtrijgegevensstructuur in Python?

Zoals u in het vorige artikel al hebt bestudeerd over het belang van datastructuren, laten we direct in het onderwerp van het artikel duiken, d.w.z. Wachtrijgegevensstructuur. Ik bespreek de volgende onderwerpen:

• Behoefte aan wachtrijgegevensstructuur
• Voorbeelden van dagelijkse wachtrijen
• Een wachtrijgegevensstructuur maken
• In wachtrij
• De wachtrij verwijderen
• Toepassingen van Queue

Behoefte aan wachtrijgegevensstructuur

Stel dat je op een dag een film wilt. In de multiplex werden de tickets uitgegeven op basis van wie het eerst komt, het eerst maalt en stonden mensen achter elkaar te wachten op hun beurt. Dus wat ga je doen?? Je moet naar achteren zijn gegaan en achter de laatste persoon hebben gestaan ​​die op het kaartje wachtte.

Hier staan ​​de mensen achter elkaar en worden ze bediend op basis van de First-in-first-out (FIFO) mechanisme. Een dergelijke opstelling staat bekend als een Wachtrij.

Voorbeelden van dagelijkse wachtrijen

Laten we eens kijken naar enkele voorbeelden waarbij wachtrijtypen in het dagelijks leven werken:

• Telefoonbeantwoordingssysteem De persoon die als eerste op uw gadget belt, wordt als eerste bezocht.
• Bagage-controlemachine - Controleert de Bagage die als eerste op de lopende band heeft gestaan.
• Voertuigen op de tolbrug - De voertuigen die vroeg aankomen, vertrekken als eerste.
• Call center - telefoonsystemen gebruiken wachtrijen om mensen die ze bellen op volgorde te houden totdat een servicemedewerker vrij is.

Al deze voorbeelden volgen First-in-last-out strategie.

Een wachtrijgegevensstructuur maken

Afgezien van de aanvullende bewerkingen, kan ik zeggen dat de belangrijkste bewerkingen die mogelijk zijn op de wachtrij zijn:

een. In wachtrij of voeg een element toe aan het einde van de wachtrij.

2. De wachtrij verwijderen of verwijder een element van de voorkant van de wachtrij

Laten we nu beginnen met het maken van klassenwachtrij in Python:

class Wachtrij: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0

• max_size is het maximale aantal elementen dat in de wachtrij wordt verwacht.
• Elementen van de wachtrij worden opgeslagen in de python-lijst
• achterzijde geeft de indexpositie van het laatste element in de wachtrij aan.
• De achterkant wordt aanvankelijk als -1 beschouwd omdat de wachtrij leeg is
• Front geeft de positie van het eerste element in de wachtrij aan.
• De voorkant wordt aanvankelijk als 0 beschouwd omdat deze altijd naar het eerste element van de wachtrij verwijst

In wachtrij plaatsen

Als u nu probeert elementen in de wachtrij te plaatsen, moet u de volgende punten onthouden:

• Of er nog ruimte over is in de wachtrij of niet, d.w.z. of achterzijde gelijk is aan max_size -1
• De achterkant wijst naar het laatste element dat in de wachtrij is geplaatst.

Dus, wat wordt het algoritme?

#returns max_size van wachtrij def get_max_size (self): return self .__ max_size #returns bool-waarde, ongeacht of de wachtrij vol is of niet, True if full en False anders def is_full (self): return self .__ rear == self .__ max_size-1 # voegt gegevens in de wachtrij in / zet deze in de wachtrij als deze niet volledig in de wachtrij staat. def enqueue (self, data): if (self.is_full ()): print ('Wachtrij is vol. Geen wachtrij mogelijk') else: self .__ rear + = 1 self. __elements [self .__ rear] = data #display alle inhoud van de wachtrij def display (self): for i in range (0, self .__ rear + 1): print (self .__ elements [i]) #U kunt de onder __str __ () om de elementen van het DS-object af te drukken tijdens het debuggen def __str __ (self): msg = [] index = self .__ front while (index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg

Nu, wanneer u het volgende uitvoert:

queue1 = Wachtrij (5)

#Maak alle vereiste element (en) in de wachtrij.

queue1.enqueue ('A')

queue1.enqueue ('B')

queue1.enqueue ('C')

queue1.enqueue ('D')

queue1.enqueue ('E')

wachtrij1.display ()

queue1.enqueue ('F')

print (wachtrij1)

Uitgang:

NAAR

java c ++ python

B.

C

D

IS

Wachtrij is vol. Geen wachtrij mogelijk

Wachtrijgegevens (voor naar achter): A B C D E

De wachtrij verwijderen

Nu je de elementen in de wachtrij hebt ingevoegd / in de wachtrij hebt gezet, wil je ze van voren verwijderen / verwijderen, dus je moet voor het volgende zorgen:

• Er zijn elementen in de wachtrij, d.w.z. achterkant mag niet gelijk zijn aan -1.
• Ten tweede moet u onthouden dat als elementen van de voorkant worden verwijderd, dus na het verwijderen van de voorkant moet worden opgehoogd om naar de volgende voorkant te wijzen.
• De voorkant mag niet naar het einde van de wachtrij wijzen, d.w.z. gelijk aan max_size.

Dus, wat wordt het algoritme?

#functie om te controleren of de wachtrij leeg is of niet def is_empty (self): if (self .__ rear == - 1 of self .__ front == self .__ max_size): return True else: return False #function om een ​​element te verwijderen en terug te geven it def dequeue (self): if (self.is_empty ()): print ('wachtrij is al leeg') else: data = self .__ elements [self .__ front] self .__ front + = 1 retourneer data #functie om elementen weer te geven van van voren naar achteren als wachtrij niet leeg is def display (self): if (not self.is_empty ()): for i in range (self .__ front, self .__ rear + 1): print (self .__ elements [i]) else : print ('lege wachtrij')

Nu als u het volgende uitvoert:

queue1 = Wachtrij (5)

#Maak alle vereiste element (en) in de wachtrij

queue1.enqueue ('A')

queue1.enqueue ('B')

queue1.enqueue ('C')

queue1.enqueue ('D')

queue1.enqueue ('E')

print (wachtrij1)

#De wachtrij maken van alle vereiste element (en)

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

# Geef alle elementen in de wachtrij weer.

wachtrij1.display ()

Uitgang:

Wachtrijgegevens (voor naar achter): A B C D E

Uit wachtrij: A

Uit wachtrij: B

Uit wachtrij: C

Uit wachtrij: D

Uit wachtrij: E

wachtrij is al leeg

Uit wachtrij: geen

lege wachtrij

Toepassingen van Queue

Vanaf nu heb je de basisprincipes van wachtrij al begrepen. Om nu dieper te duiken, zullen we enkele van de toepassingen ervan bekijken.

• Voorbeeld 1:

Afdrukwachtrij in Windows gebruikt een wachtrij om alle actieve en wachtende afdruktaken op te slaan. Als we documenten willen afdrukken, geven we de een na de ander afdrukopdrachten. Op basis van de afdrukopdrachten worden de documenten in de afdrukwachtrij geplaatst. Als de printer klaar is, wordt het document als eerste verzonden om het te laten afdrukken.

Stel dat u afdrukopdrachten hebt gegeven voor 3 documenten in de volgorde doc1, gevolgd door doc2 en doc3.
De afdrukwachtrij wordt gevuld zoals hieronder weergegeven:

doc-n, waarbij het document het document is dat voor afdrukken is verzonden en n, is het aantal pagina's in het document. Doc2-10 betekent bijvoorbeeld dat doc2 moet worden afgedrukt en dat het 10 pagina's heeft. Hier is een code die de werking van de afdrukwachtrij simuleert. Doorloop de code en kijk hoe de wachtrij wordt gebruikt in deze implementatie.

class Wachtrij: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0 def is_full (self): if (self .__ rear = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ front> self .__ rear): return True return False def enqueue (self, data): if (self.is_full ()): print ('Wachtrij is vol !!!') else: zelf .__ achterkant + = 1 zelf .__ elementen [zelf .__ achterkant] = data def de wachtrij (zelf): if (self.is_empty ()): print ('Wachtrij is leeg! !! ') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data def display (self): voor index binnen bereik (self .__ front, self .__ rear + 1): print (self .__ elementen [index]) def get_max_size (self): return self .__ max_size #U kunt de onderstaande __str __ () gebruiken om de elementen van het DS-object af te drukken terwijl #debugging def __str __ (self): msg = [] index = self .__ front while (inhoudsopgave<=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()

Uitgang:

doc1-5 verzonden voor afdrukken

doc2-3 verzonden voor afdrukken

doc3-6 verzonden voor afdrukken

doc1-5 gedrukt

Resterende nr. Aantal pagina's in printer: 7

doc2-3 afgedrukt

Resterende nr. Aantal pagina's in printer: 4

Kan doc3 niet afdrukken. Niet genoeg pagina's in de printer

• Voorbeeld 2:

Laten we proberen een ander voorbeeld te begrijpen waarin de Queue-gegevensstructuur wordt gebruikt. Kun je proberen de code te begrijpen en te vertellen wat de volgende functie doet?

1. zeker leuk (n):
2. aqueue = Wachtrij (100)
3. voor num in bereik (1, n + 1):
4. wachtrij (num)
5. resultaat = 1
6. while (niet (aqueue.is_empty ())):
7. num = AQUUE.DEQUEUE ()
8. resultaat * = num
9. print (resultaat)

Wanneer de functie fun () wordt aangeroepen door n door te geven,

ansible vs marionet vs chef

• regels 2 tot 4 zetten de elementen van 1 tot n in de wachtrij
• regel 5 t / m 8 vindt het product van die elementen door het een voor een uit de wachtrij te halen

Hiermee komen we aan het einde van dit artikel Queue Data Structure. Als je de codes met succes hebt begrepen en zelf hebt uitgevoerd, ben je niet langer een nieuweling van Queue Data Structure.

Heeft u een vraag voor ons? Vermeld het in het opmerkingengedeelte van dit artikel en we nemen zo snel mogelijk contact met u op.

Om diepgaande kennis op te doen over Python en de verschillende applicaties, kunt u zich live inschrijven met 24/7 ondersteuning en levenslange toegang.