Kao što ste već proučavali važnost struktura podataka u prethodnom članku, zaronimo točno u temu članka, tj. Struktura podataka u redu čekanja. Razgovarat ću o sljedećim temama:
- Potreba za strukturom podataka o redu čekanja
- Primjeri svakodnevnog života u redu
- Stvaranje strukture podataka u redu čekanja
- Stavite u red čekanja
- Izbaci red
- Primjene u redu čekanja
Potreba za strukturom podataka o redu čekanja
Pretpostavimo da jednog dana želite film. U multipleksu su se karte izdavale po principu 'Prvo dođi-prvi posluži', a ljudi su stajali jedni iza drugih i čekali svoj red. Pa, što ćeš učiniti ?? Sigurno ste otišli pozadi i stali iza zadnje osobe koja je čekala kartu.
Ovdje ljudi stoje jedan iza drugog i opslužuju se na temelju Prvo u prvom (FIFO) mehanizam. Takav je raspored poznat pod nazivom Red.
Primjeri svakodnevnog života u redu
Razmotrimo neke primjere gdje imamo redove koji rade u svakodnevnom životu:
- Telefonska sekretarica- Osoba koja prva nazove vaš gadget prvo bude prisutna.
- Stroj za provjeru prtljage - provjerava prtljagu koja je prva zadržana na transportnoj traci.
- Vozila na mostu s naplatom cestarine - Vozila koja rano kreću prva kreću.
- Pozivni centar - telefonski će sustavi koristiti redove čekanja kako bi zadržali ljude koji ih zovu redom, sve dok predstavnik usluge ne bude slobodan.
Svi ovi primjeri slijede Prvo u posljednjem strategija.
Stvaranje strukture podataka u redu čekanja
Osim dopunskih operacija, mogu reći da su glavne operacije moguće u redu čekanja:
jedan. Stavite u red čekanja ili dodajte element na kraj reda.
2. Izbaci red ili uklonite element s prednje strane reda
Sada krenimo s stvaranjem reda klasa u Pythonu:
class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ stražnji = -1 self .__ front = 0
- max_size je maksimalan broj elemenata koji se očekuju u redu čekanja.
- Elementi reda pohranjeni su na popisu python
- straga označava položaj indeksa posljednjeg elementa u redu.
- Straga se u početku uzima -1 jer je red prazan
- Sprijeda označava položaj prvog elementa u redu čekanja.
- Prednja strana u početku se uzima kao 0, jer će uvijek usmjeravati na prvi element reda
Stavite u red čekanja
Sada, kada pokušavate elemente staviti u red čekanja, morate upamtiti sljedeće točke:
- Ostaje li mjesta u redu ili ne, tj. Ako je straga jednako max_size -1
- Stražnja strana usmjerava na zadnji element umetnut u red čekanja.
Pa, koji će biti algoritam ??
#returns max_size of queue def get_max_size (self): return self .__ max_size #retts bool value je li red pun ili nije, True if full i False inače def is_full (self): return self .__ stražnji == self .__ max_size-1 # u redoslijed ubacuje / stavlja podatke u red ako nije pun def enque (self, data): if (self.is_full ()): print ('Red čekanja je pun. Nije moguć nijedan redoslijed') else: self .__ stražnji + = 1 self. __elementi [self .__ stražnji] = podaci #prikazati sav sadržaj prikaza reda čekanja (self): za i u rasponu (0, self .__ stražnji + 1): ispis (self .__ elementi [i]) # Možete koristiti ispod __str __ () za ispis elemenata DS objekta tijekom uklanjanja pogrešaka 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
Sada, kada izvršite sljedeće:
red čekanja1 = Red čekanja (5)
# Izbacite sve potrebne elemente u red.
java za primjere programa petlje
queue1.enqueue ('A')
queue1.enqueue ('B')
queue1.enqueue ('C')
queue1.enqueue ('D')
queue1.enqueue ('E')
queue1.display ()
queue1.enqueue ('F')
ispis (red 1)
Izlaz:
DO
B
C
D
JE
Red je pun. Nijedan redoslijed nije moguć
Podaci o redu čekanja (sprijeda prema straga): A B C D E
De-Queue
Sada, kako ste umetnuli / stavili elemente u red čekanja, želite ih ukloniti iz redova / izbrisati s prednje strane, pa morate voditi računa o sljedećem:
- Postoje elementi u redu čekanja, tj. Stražnja strana ne smije biti jednaka -1.
- Drugo, morate imati na umu da se elementi brišu s prednje strane pa bi nakon brisanja prednji trebali biti povećani na sljedeću prednju.
- Prednja strana ne smije usmjeravati kraj reda, tj. Jednaka je max_size.
Pa, koji će biti algoritam ??
#funkcija za provjeru je li red prazan ili nije def is_empty (self): if (self .__ stražnji == - 1 ili self .__ front == self .__ max_size): return True else: return False # function za deque element i return def defueque (self): if (self.is_empty ()): print ('red je već prazan') else: data = self .__ elementi [self .__ front] self .__ front + = 1 return data # function za prikaz elemenata iz sprijeda prema natrag ako red nije prazan def display (self): if (not self.is_empty ()): for i in range (self .__ front, self .__ stražnji + 1): print (self .__ elements [i]) else : print ('prazan red čekanja')
Sada kada izvršite sljedeće:
red čekanja1 = Red čekanja (5)
# Izbaci sve potrebne elemente u red
queue1.enqueue ('A')
queue1.enqueue ('B')
queue1.enqueue ('C')
queue1.enqueue ('D')
queue1.enqueue ('E')
ispis (red 1)
#Dequeue sve potrebne elemente
ispis („Dequeued:“, queue1.dequeue ())
ispis („Dequeued:“, queue1.dequeue ())
što radi .trim u javi
ispis („Dequeued:“, queue1.dequeue ())
ispis („Dequeued:“, queue1.dequeue ())
ispis („Dequeued:“, queue1.dequeue ())
ispis („Dequeued:“, queue1.dequeue ())
# Prikaži sve elemente u redu.
queue1.display ()
Izlaz:
Podaci o redu čekanja (sprijeda prema straga): A B C D E
Izgubljeno: A
Dequeued: B
Izgubljeno: C
Izgubljeno: D
Izgubljeno: E
red je već prazan
Dequeued: Nijedan
prazan red
Primjene u redu čekanja
Od sada ste već razumjeli osnove reda čekanja. Sada ćemo dublje zaroniti u neke od njegovih primjena.
kako pretvoriti double u int u javi
- Primjer 1:
Red čekanja za ispis u sustavu Windows koristi red za spremanje svih aktivnih i ispisa na čekanju. Kada želimo ispisati dokumente, izdajemo naredbe za ispis jednu za drugom. Na temelju naredbi za ispis, dokumenti će se poredati u redu za ispis. Kad je pisač spreman, dokument će se poslati prvi prema prvom kako bi se ispisao.
Pretpostavimo da ste izdali naredbe za ispis za 3 dokumenta redoslijedom doc1, a zatim doc2 i doc3.
Red čekanja za ispis popunit će se kao što je prikazano u nastavku:
doc-n, gdje je dokument dokument poslan na ispis i n, je broj stranica u dokumentu. Na primjer, doc2-10 znači da se doc2 treba ispisati i ima 10 stranica. Ovdje je kod koji simulira rad reda čekanja za ispis. Prođite kroz kod i promatrajte kako se red koristi u ovoj implementaciji.
class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ stražnji = -1 self .__ front = 0 def is_full (self): if (self .__ stražnji = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ front> self .__ straga): return True return False def enqueue (self, data): if (self.is_full ()): print ('Red čekanja je pun !!!') else: self .__ stražnji + = 1 self .__ elementi [self .__ stražnji] = data def dequeue (self): if (self.is_empty ()): print ('Red čekanja je prazan! !! ') else: data = self .__ elementi [self .__ front] self .__ front + = 1 return data def display (self): za indeks u dometu (self .__ front, self .__ stražnji + 1): print (self .__ elements [index]) def get_max_size (self): return self .__ max_size # Možete koristiti __str __ () za ispis elemenata DS objekta dok #debug 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()
Izlaz:
doc1-5 poslan na tisak
doc2-3 poslan na tisak
doc3-6 poslan na tisak
doc1-5 tiskan
Preostali br. stranica u pisaču: 7
doc2-3 tiskan
Preostali br. stranica u pisaču: 4
Nije moguće ispisati doc3. Nema dovoljno stranica u pisaču
- Primjer 2:
Pokušajmo razumjeti još jedan primjer koji koristi strukturu podataka reda čekanja. Možete li pokušati razumjeti kod i reći što radi sljedeća funkcija?
- def zabava (n):
- vodeno = Red (100)
- za broj u rasponu (1, n + 1):
- red (broj)
- rezultat = 1
- while (ne (aqueue.is_empty ())):
- num = AQUUE.DEQUEUE ()
- rezultat * = num
- ispis (rezultat)
Kada se funkcija fun () pozove dodavanjem n,
- retci 2 do 4 stavljaju u red elemente od 1 do n
- retci 5 do 8 pronalaze umnožak tih elemenata odmještanjem jednog po jednog
Ovim smo došli do kraja ovog članka o strukturi podataka o redu čekanja. Ako ste sami uspješno razumjeli i pokrenuli kodove, više niste novak u strukturi podataka reda čekanja.
Imate pitanje za nas? Molimo navedite ga u odjeljku za komentare ovog članka i javit ćemo vam se što je prije moguće.
Da biste stekli detaljno znanje o Pythonu, zajedno s raznim aplikacijama, možete se prijaviti uživo s 24/7 podrškom i doživotnim pristupom.