Čo je to dátová štruktúra frontu v Pythone?

Ako ste si už v predchádzajúcom článku študovali dôležitosť dátových štruktúr, poďme sa ponoriť priamo do témy článku, tj. Dátová štruktúra frontu. Budem diskutovať o nasledujúcich témach:

• Potreba dátovej štruktúry frontu
• Príklady každodenného života v rade
• Vytvorenie dátovej štruktúry frontu
• Zoradiť do frontu
• Zrušiť poradie
• Aplikácie frontu

Potreba dátovej štruktúry frontu

Predpokladajme, že raz chcete film. V multiplexe boli lístky vydávané na princípe „kto prvý príde - prvý slúži“ a ľudia stáli za sebou a čakali na svoju príležitosť. Takže, čo urobíš ?? Určite ste išli dozadu a postavili sa za poslednú osobu čakajúcu na lístok.

Ľudia tu stoja jeden za druhým a na základe nich sa poskytuje servis Prvý-prvý-prvý-von (FIFO) mechanizmus. Takéto usporiadanie je známe ako a Fronta.

Príklady každodenného života v rade

Zoberme si niekoľko príkladov, keď vyberáme typy front pracujúce v každodennom živote:

• Telefónny záznamník - Osoba, ktorá najskôr zavolá na váš modul gadget, sa najskôr zúčastní.
• Stroj na kontrolu batožiny - Skontroluje batožinu, ktorá bola na dopravnom páse ponechaná ako prvá.
• Vozidlá na moste k plateniu mýta - Vozidlá prichádzajúce skoro ráno odchádzajú prvé.
• Call centrum - telefónne systémy budú používať fronty, aby udržali ľudí, ktorí im volajú, v poriadku, kým servisný zástupca nebude zadarmo.

Nasledujú všetky tieto príklady Prvý-posledný-posledný stratégia.

Vytvorenie dátovej štruktúry frontu

Okrem doplnkových operácií môžem povedať, že hlavné možné operácie vo fronte sú:

jeden. Zoradiť do frontu alebo pridať prvok na koniec poradia.

2. Zrušiť poradie alebo odstráňte prvok z prednej časti frontu

Teraz začnime vytvorením triedy frontu v Pythone:

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

• max_size je maximálny počet prvkov očakávaných vo fronte.
• Prvky frontu sú uložené v zozname pythónov
• vzadu označuje pozíciu indexu posledného prvku vo fronte.
• Zadná strana sa pôvodne považovala za -1, pretože poradie je prázdne
• Predná strana označuje pozíciu prvého prvku vo fronte.
• Predná strana sa na začiatku považuje za 0, pretože bude vždy smerovať na prvý prvok poradia

Zaradiť do poradia

Keď sa teraz snažíte zaradiť prvky do frontu, musíte si zapamätať nasledujúce body:

• Či už vo fronte zostane miesto alebo nie, teda či sa zadná rovná max_size -1
• Zadná strana bude smerovať k poslednému prvku vloženému do poradia.

Aký bude teda algoritmus?

#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 otherwise def is_full (self): return self .__ rear == self .__ max_size-1 # vloží / zaradí dáta do poradia, ak nie je úplné def enqueue (self, data): if (self.is_full ()): print ('Fronta je plná. Nie je možné zaradenie do frontu') else: self .__ vzadu + = 1 self. __elements [self .__ rear] = data # zobraziť všetok obsah zobrazenia def. frontu (self): pre i v rozsahu (0, self .__ rear + 1): print (self .__ elements [i]) #Môžete použiť nižšie __str __ () na vytlačenie prvkov objektu DS pri ladení 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

Teraz, keď vykonáte nasledovné:

queue1 = Queue (5)

# Zaškrtnite všetky požadované prvky.

queue1.enqueue („A“)

queue1.enqueue („B“)

queue1.enqueue („C“)

queue1.enqueue („D“)

queue1.enqueue („E“)

queue1.display ()

queue1.enqueue („F“)

tlač (front 1)

Výkon:

TO

B

C.

D

JE

Fronta je plná. Nie je možné zaradiť žiadny rad

Údaje o poradí (spredu dozadu): A B C D E

Zrušenie poradia

Teraz, keď ste vložili / zaradili prvky do fronty, chcete ich zoradiť / vymazať spredu, takže je potrebné dbať na nasledujúce:

• Vo fronte sú prvky, t. J. zadná strana by sa nemala rovnať hodnote -1.
• Po druhé, musíte si uvedomiť, že keď sa prvky mazajú spredu, mali by sa po odstránení spredu zvyšovať aj ďalšie body.
• Predná strana by nemala smerovať na koniec poradia, t. J. Rovná sa max_size.

Aký bude teda algoritmus?

#function to check if queue is empty or not def is_empty (self): if (self .__ rear == - 1 or self .__ front == self .__ max_size): return True else: return False #function to deque an element and return to def dequeue (self): if (self.is_empty ()): print ('queue is already empty') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data #function to display elements from spredu dozadu, ak fronta nie je prázdna def display (self): if (not self.is_empty ()): for i in range (self .__ front, self .__ rear + 1): print (self .__ elements [i]) else : print ('prázdny front')

Teraz, keď vykonáte nasledujúce:

queue1 = Queue (5)

final vs konečne vs finalizovať

# Zaškrtnite všetky požadované prvky

queue1.enqueue („A“)

queue1.enqueue („B“)

queue1.enqueue („C“)

queue1.enqueue („D“)

queue1.enqueue („E“)

tlač (front 1)

# Zaškrtnite všetky povinné prvky

tlač („Založené:“, queue1.dequeue ())

tlač („Založené:“, queue1.dequeue ())

tlač („Založené:“, queue1.dequeue ())

tlač („Založené:“, queue1.dequeue ())

tlač („Založené:“, queue1.dequeue ())

tlač („Založené:“, queue1.dequeue ())

# Zobraziť všetky prvky vo fronte.

queue1.display ()

Výkon:

Údaje o poradí (spredu dozadu): A B C D E

Vyradené: A

Vyradené: B

Vyradené: C

Vyradené: D

Vyradené: E

poradie je už prázdne

Vyradené: Žiadne

prázdny rad

Aplikácie frontu

Odteraz ste už pochopili základy poradia. Teraz sa pozrieme hlbšie na niektoré z jej aplikácií.

prejsť na príkaz v c ++

• Príklad 1:

Tlačová fronta v systéme Windows používa front na ukladanie všetkých aktívnych a čakajúcich tlačových úloh. Keď chceme tlačiť dokumenty, vydávame tlačové príkazy jeden za druhým. Na základe príkazov na tlač sa dokumenty zoradia do tlačového frontu. Keď je tlačiareň pripravená, dokument sa odošle ako prvý, prvý von, aby sa mohol vytlačiť.

Predpokladajme, že ste zadali tlačové príkazy pre 3 dokumenty v poradí doc1, za ktorými nasledujú doc2 a doc3.
Tlačový front sa vyplní, ako je uvedené nižšie:

doc-n, kde doc je dokument odoslaný na tlač an, je počet strán v dokumente. Napríklad doc2-10 znamená, že sa má vytlačiť dokument2, ktorý má 10 strán. Tu je kód, ktorý simuluje činnosť tlačového frontu. Prejdite si kód a sledujte, ako sa fronta používa v tejto implementácii.

trieda fronty: 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 ('Queue is full !!!') else: self .__ rear + = 1 self .__ elements [self .__ rear] = data def dequeue (self): if (self.is_empty ()): print ('Queue is empty! !! ') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data def display (self): for index in range (self .__ front, self .__ rear + 1): print (self .__ elements [index]) def get_max_size (self): return self .__ max_size # Môžete použiť nasledujúci __str __ () na tlač prvkov DS objektu, zatiaľ čo #debugging def __str __ (self): msg = [] index = self .__ predný while (index<=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()

Výkon:

dokument 1-5 odoslaný na tlač

doc2-3 odoslaný na tlač

dokument doc3-6 odoslaný na tlač

doc1-5 vytlačené

Zvyšné č. strán v tlačiarni: 7

doc2-3 vytlačené

Zvyšné č. počet strán v tlačiarni: 4

Nepodarilo sa vytlačiť dokument doc3. V tlačiarni nie je dostatok stránok

• Príklad 2:

Pokúsme sa pochopiť ďalší príklad, ktorý využíva dátovú štruktúru frontu. Môžete skúsiť porozumieť kódu a povedať, čo robí nasledujúca funkcia?

1. def zábava (n):
2. aqueue = Queue (100)
3. pre počet v rozsahu (1, n + 1):
4. poradie (počet)
5. výsledok = 1
6. while (nie (aqueue.is_empty ())):
7. num = AQUUE.DEQUEUE ()
8. výsledok * = počet
9. tlač (výsledok)

Keď je funkcia fun () vyvolaná prechodom n,

• riadky 2 až 4 zaraďujú do radu prvky od 1 do n
• riadky 5 až 8 nájdu produkt týchto prvkov ich postupným radením jeden po druhom

Týmto sa dostávame na koniec tohto článku Queue Data Structure. Ak ste kódy sami úspešne pochopili a spustili, už nie ste nováčikom v dátovej štruktúre frontu.

Máte na nás otázku? Uveďte to prosím v sekcii komentárov tohto článku a my sa vám ozveme čo najskôr.

Ak chcete získať podrobné informácie o Pythone a jeho rôznych aplikáciách, môžete sa zaregistrovať naživo s nepretržitou podporou a doživotným prístupom.