Kaj je struktura podatkov v čakalni vrsti v Pythonu?

Kot ste že proučevali pomen podatkovnih struktur v prejšnjem članku, pojdimo naravnost v temo članka, tj. Struktura podatkov v čakalni vrsti. Razpravljal bom o naslednjih temah:

• Potreba po strukturi podatkov v čakalni vrsti
• Primeri vsakdanjega življenja v vrsti
• Ustvarjanje strukture podatkov o čakalni vrsti
• V čakalno vrsto
• Ustavi čakalno vrsto
• Aplikacije v čakalni vrsti

Potreba po strukturi podatkov v čakalni vrsti

Recimo, da si nekega dne želite film. V multipleksu so bile vstopnice izdane po načelu 'Naj pride-prvi dobi' in ljudje so stali drug za drugim in čakali, da pridejo na vrsto. Torej, kaj boš naredil ?? Gotovo ste šli zadaj in stali za zadnjim, ki je čakal na vozovnico.

Tu ljudje stojijo eden za drugim in jih oskrbujejo na podlagi Prvi v prvem (FIFO) mehanizem. Takšna ureditev je znana kot Čakalna vrsta.

Primeri vsakdanjega življenja v vrsti

Oglejmo si nekaj primerov, ko imamo vrsto čakalnih vrst, ki delujejo v vsakdanjem življenju:

• Telefonski odzivnik- Oseba, ki najprej pokliče vaš pripomoček, se najprej udeleži.
• Stroj za preverjanje prtljage - Pregleda prtljago, ki je bila najprej zadržana na transportnem traku.
• Vozila na cestninskem mostu - Vozila, ki prej prispejo zgodaj
• Klicni center - telefonski sistemi bodo uporabljali čakalne vrste za zadrževanje ljudi, ki jih kličejo, dokler predstavnik storitve ne bo prost.

Vsi ti primeri sledijo Prvi v zadnjem strategijo.

Ustvarjanje strukture podatkov o čakalni vrsti

Poleg dopolnilnih operacij lahko rečem, da so glavne operacije, ki so možne v čakalni vrsti, naslednje:

eno. V čakalno vrsto ali dodajte element na konec čakalne vrste.

2. Ustavi čakalno vrsto ali odstranite element s sprednje strani čakalne vrste

Zdaj pa začnimo z ustvarjanjem čakalne vrste razreda v Pythonu:

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

• max_size je največje število pričakovanih elementov v čakalni vrsti.
• Elementi čakalne vrste so shranjeni na seznamu python
• zadaj označuje položaj indeksa zadnjega elementa v čakalni vrsti.
• Za zadnji del se sprva šteje -1, ker je vrsta prazna
• Spredaj označuje položaj prvega elementa v čakalni vrsti.
• Spredaj se najprej upošteva 0, ker bo vedno kazal na prvi element čakalne vrste

V čakalno vrsto

Zdaj, ko poskušate uvrstiti elemente v čakalno vrsto, si morate zapomniti naslednje točke:

• Ali je v čakalni vrsti še dovolj prostora ali ne, tj.če je zadaj enako max_size -1
• Zadnji del kaže na zadnji element, vstavljen v čakalno vrsto.

Torej, kakšen bo algoritem ??

#returns max_size of queue def get_max_size (self): return self .__ max_size #returns vrednost bool, ali je čakalna vrsta polna ali ne, True če je polna in False sicer def is_full (self): return self .__ zadaj == self .__ max_size-1 # v čakalno vrsto vstavi / postavi podatke v čakalno vrsto, če ni popolna def enqueue (self, data): if (self.is_full ()): print ('Čakalna vrsta je polna. Nobena čakalna vrsta ni mogoča') else: self .__ zadaj + = 1 self. __elementi [samo .__ zadaj] = podatki # prikaži vso vsebino prikaza čakalne vrste def (self): za i v območju (0, self .__ zadaj + 1): tiskanje (self .__ elementi [i]) # Lahko uporabite spodaj __str __ () za tiskanje elementov predmeta DS med odpravljanjem napak 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

Zdaj, ko izvedete naslednje:

čakalna vrsta1 = Čakalna vrsta (5)

funkcija razvrščanja v c ++

# Izpraznite vse zahtevane elemente.

queue1.enqueue (“A”)

queue1.enqueue (“B”)

queue1.enqueue (“C”)

queue1.enqueue (“D”)

queue1.enqueue (“E”)

queue1.display ()

queue1.enqueue (“F”)

tiskanje (čakalna vrsta1)

Izhod:

TO

B

C

D

JE

Čakalna vrsta je polna. Nobena vrsta ni mogoča

Podatki o vrsti (od spredaj do zadaj): A B C D E

Izbriši čakalno vrsto

Zdaj, ko ste elemente v čakalno vrsto vstavili / postavili v čakalno vrsto, jih želite odstraniti iz sprednje strani, zato morate poskrbeti za naslednje:

• V čakalni vrsti so elementi, tj zadnja stran ne sme biti enaka -1.
• Drugič, ne pozabite, da se elementi črtajo s sprednje strani, zato je treba po brisanju sprednjo stran povečati na točko spredaj.
• Sprednja stran ne sme kazati na konec čakalne vrste, kar je enako max_size.

Torej, kakšen bo algoritem ??

# function za preverjanje, ali je vrsta prazna ali ne, def is_empty (self): if (self .__ zadaj == - 1 ali self .__ front == self .__ max_size): return True else: return False # function za deque element in return def defueque (self): if (self.is_empty ()): print ('čakalna vrsta je že prazna') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data # function za prikaz elementov iz spredaj zadaj, če vrsta ni prazna def display (self): if (not self.is_empty ()): for i in range (self .__ front, self .__ zadaj + 1): print (self .__ elements [i]) else : print ('prazna vrsta')

Zdaj, ko izvedete naslednje:

čakalna vrsta1 = Čakalna vrsta (5)

# Izprazni vse zahtevane elemente

queue1.enqueue (“A”)

queue1.enqueue (“B”)

queue1.enqueue (“C”)

queue1.enqueue (“D”)

queue1.enqueue (“E”)

tiskanje (čakalna vrsta1)

#Dequeue vse zahtevane elemente

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

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

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

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

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

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

#Prikaži vse elemente v čakalni vrsti.

queue1.display ()

Izhod:

Podatki o vrsti (od spredaj do zadaj): A B C D E

Dequeuque: A

Dequeuque: B

Dequeuque: C

Dequeuque: D

Dequeuque: E

čakalna vrsta je že prazna

Dequeuque: Noben

prazna vrsta

Aplikacije v čakalni vrsti

Od zdaj ste že razumeli osnove čakalne vrste. Zdaj, da se poglobimo, bomo preučili nekaj njenih aplikacij.

• Primer 1:

Čakalna vrsta tiskanja v sistemu Windows uporablja čakalno vrsto za shranjevanje vseh aktivnih in čakajočih tiskalnih opravil. Ko želimo natisniti dokumente, zapovedi za tiskanje izdajamo drug za drugim. Na podlagi ukazov za tiskanje bodo dokumenti razvrščeni v čakalno vrsto za tiskanje. Ko je tiskalnik pripravljen, bo dokument poslan prvi v prvem, da bo natisnjen.

Recimo, da ste izdali ukaze za tiskanje za 3 dokumente v vrstnem redu doc1, ki jim sledita doc2 in doc3.
Čakalna vrsta za tiskanje se zapolni, kot je prikazano spodaj:

doc-n, kjer je dokument dokument, poslan v tisk, in n, je število strani v dokumentu. Na primer, doc2-10 pomeni, da je treba doc2 natisniti in ima 10 strani. Tu je koda, ki simulira delovanje čakalne vrste za tiskanje. Preglejte kodo in opazujte, kako se vrsta uporablja pri tej izvedbi.

class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ zadaj = -1 self .__ front = 0 def is_full (self): if (self .__ zadaj = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ front> self .__ zadaj): return True return False def enqueue (self, data): if (self.is_full ()): print ('Čakalna vrsta je polna !!!') else: self .__ zadaj + = 1 self .__ elementi [self .__ zadaj] = data def dequeue (self): if (self.is_empty ()): print ('Čakalna vrsta je prazna! !! ') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data def display (self): za indeks v obsegu (self .__ spredaj, self .__ zadaj + 1): print (self .__ elements [index]) def get_max_size (self): vrni self .__ max_size # Spodnji __str __ () lahko uporabite za tiskanje elementov predmeta DS, medtem ko #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()

Izhod:

spremenljiv razred v primeru Java

doc1-5, poslan v tisk

doc2-3 poslan v tisk

doc3-6, poslano v tisk

doc1-5 natisnjeno

Preostala št. strani v tiskalniku: 7

doc2-3 natisnjeno

Preostala št. strani v tiskalniku: 4

Doc3 ni bilo mogoče natisniti. V tiskalniku ni dovolj strani

• 2. primer:

Poskusimo razumeti še en primer, ki uporablja strukturo podatkov čakalne vrste. Ali lahko poskusite razumeti kodo in povejte, kaj počne naslednja funkcija?

1. def zabava (n):
2. vodna vrsta = Čakalna vrsta (100)
3. za število v območju (1, n + 1):
4. čakalna vrsta (število)
5. rezultat = 1
6. while (ne (aqueue.is_empty ())):
7. num = AQUUE.DEQUEUE ()
8. rezultat * = štev
9. natisni (rezultat)

Ko se funkcija fun () prikliče s predajo n,

• vrstice 2 do 4 uvrstijo elemente od 1 do n v čakalno vrsto
• vrstice 5 do 8 najdejo zmnožek teh elementov, tako da ga razvrstijo enega za drugim

S tem smo prišli do konca tega članka o strukturi podatkov o čakalni vrsti. Če ste kode uspešno razumeli in zagnali sami, niste več novinec v podatkovni strukturi čakalne vrste.

Imate vprašanje za nas? Prosimo, omenite ga v oddelku za komentarje tega članka in odgovorili vam bomo v najkrajšem možnem času.

Če želite pridobiti poglobljeno znanje o Pythonu skupaj z različnimi aplikacijami, se lahko prijavite v živo s 24-urno podporo in življenjskim dostopom.