Kuten olet jo tutkinut tietorakenteiden merkityksestä edellisessä artikkelissa, sukeltaa suoraan artikkelin aiheeseen eli jonon tietorakenteeseen. Keskustelen seuraavista aiheista:
- Jonon tietorakenteen tarve
- Päivittäisen elämän esimerkkejä jonosta
- Jonon tietorakenteen luominen
- En-jono
- Poista jono
- Jonon sovellukset
Jonon tietorakenteen tarve
Oletetaan, että haluat elokuvan jonain päivänä. Multipleksissä liput annettiin First-Come-First-Serve -periaatteella ja ihmiset seisoivat toistensa takana odottaen vuoroaan. Joten mitä aiot tehdä ?? Olet mennyt taaksepäin ja seisonut viimeisen lipun odottavan henkilön takana.
Täällä ihmiset seisovat toistensa takana ja heitä palvellaan Ensimmäinen sisään-ensimmäiseksi-ulos (FIFO) mekanismi. Tällainen järjestely tunnetaan nimellä Jonottaa.
Päivittäisen elämän esimerkkejä jonosta
Tarkastellaan joitain esimerkkejä, joissa näkemme jonotyypin työskentelemisen päivittäisessä elämässä:
- Puhelinvastaaja- Henkilö, joka soittaa ensin laitteellasi, osallistuu ensin.
- Matkalaukkujen tarkastuskone - Tarkistaa ensin kuljetinhihnalla pidetyt matkatavarat.
- Ajoneuvot tietullisillalla - Aikaisin saapuvat ajoneuvot lähtevät ensin.
- Puhelukeskus - puhelinjärjestelmät käyttävät jonoja pitääkseen heitä soittavat järjestyksessä, kunnes huoltoedustaja on vapaa.
Kaikki nämä esimerkit seuraavat Ensimmäinen-viimeinen-ulos strategia.
Jonon tietorakenteen luominen
Täydentävien operaatioiden lisäksi voin sanoa, että tärkeimmät toiminnot jonossa ovat:
yksi. En-jono tai lisää elementti jonon loppuun.
2. Poista jono tai poista elementti jonon etuosasta
Aloitetaan nyt luomalla luokan jono Pythonissa:
class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0
- max_size on jonossa odotettavissa olevien elementtien enimmäismäärä.
- Jonon elementit tallennetaan python-luetteloon
- takaosa osoittaa jonon viimeisen elementin hakemistokohdan.
- Takana pidetään aluksi -1, koska jono on tyhjä
- Etu osoittaa jonon ensimmäisen elementin sijainnin.
- Rintaman oletetaan olevan aluksi 0, koska se osoittaa aina jonon ensimmäiseen elementtiin
Enqueue
Kun yrität sijoittaa elementtejä jonoon, sinun on muistettava seuraavat seikat:
- Onko jonossa tilaa jäljellä vai ei, ts. Jos takaosa on sama kuin max_size -1
- Takana on viimeinen jonoon lisätty elementti.
Joten mikä on algoritmi?
# palauttaa jonon enimmäiskoon def get_max_size (itse): return self .__ max_size #returns bool value riippumatta siitä, onko jono täynnä vai ei, True jos täysi ja False muuten def on_full (itse): return self .__ rear == self .__ max_size-1 # lisää / jonottaa tietoja jonoon, jos se ei ole täysi def enqueue (itse, data): if (self.is_full ()): print ('Jono on täynnä. Ei enqueue mahdollista') muu: self .__ takaosa = = 1 itse. __elements [self .__ rear] = data #näytä koko jonon def-näytön sisältö (self): i-alueella (0, self .__ taka + 1): print (self .__-elementit [i]) #Voit käyttää alla __str __ () tulostaa DS-objektin elementit virheenkorjauksen aikana 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
Nyt kun suoritat seuraavat:
jono1 = jono (5)
#Käytä kaikki vaaditut elementit.
queue1.enqueue (“A”)
queue1.enqueue (“B”)
queue1.enqueue (“C”)
queue1.enqueue (“D”)
queue1.enqueue (“E”)
queue1.display ()
queue1.enqueue (“F”)
tulosta (jono1)
Tuotos:
TO
B
C
D
ON
Jono on täynnä. Enkee ei ole mahdollista
Jonotiedot (edestä taakse): A B C D E
Poista jono
Kun olet lisännyt / kiinnittänyt elementit jonoon, haluat purkaa / poistaa ne edestä, joten sinun on huolehdittava seuraavista:
- Jonossa on elementtejä, ts. Takaosan ei pitäisi olla yhtä suuri kuin -1.
- Toiseksi, sinun on muistettava, että kun elementit poistetaan edestä, niin etupuolen poistamisen jälkeen tulisi lisätä seuraavaan etuosaan.
- Etuosan ei tulisi osoittaa jonon loppua, eli yhtä suuri kuin max_size.
Joten mikä on algoritmi?
#toiminto tarkistaaksesi onko jono tyhjä vai ei def is_empty (itse): jos (itse .__ taka == - 1 tai itse .__ edessä == itse .__ max_size): palaa Tosi muu: palauta Väärä #funktio elementin irrotukseen ja paluu it def dequeue (self): if (self.is_empty ()): print ('jono on jo tyhjä') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data # function to display elements from edestä taakse, jos jono ei ole tyhjä def-näyttö (itse): jos (ei itse.is_tyhjä ()): i-alueella (itse .__ edessä, itse .__taka + 1): tulosta (itse .__elementit [i]) muu : tulosta ('tyhjä jono')
Nyt kun suoritat seuraavat:
jono1 = jono (5)
#Enqueue kaikki vaaditut elementit
queue1.enqueue (“A”)
queue1.enqueue (“B”)
queue1.enqueue (“C”)
queue1.enqueue (“D”)
queue1.enqueue (“E”)
tulosta (jono1)
#Dequeue kaikki vaaditut elementit
tulosta (“Dequeued:“, jono1.dequeue ())
tulosta (“Dequeued:“, jono1.dequeue ())
tulosta (“Dequeued:“, jono1.dequeue ())
tulosta (“Dequeued:“, jono1.dequeue ())
tulosta (“Dequeued:“, jono1.dequeue ())
tulosta (“Dequeued:“, jono1.dequeue ())
#Näytä kaikki jonon elementit.
queue1.display ()
Tuotos:
Jonotiedot (edestä taakse): A B C D E
Purettu: A
Irrotettu: B
Purettu: C
Irrotettu: D
Purettu: E
jono on jo tyhjä
Dequeued: Ei mitään
tyhjä jono
Jonon sovellukset
Tähän mennessä olet jo ymmärtänyt jonon perusteet. Nyt sukeltaa syvemmälle, tutkimme joitain sen sovelluksia.
- Esimerkki 1:
Tulostusjono Windowsissa käyttää jonoa kaikkien aktiivisten ja odottavien tulostustöiden tallentamiseen. Kun haluamme tulostaa asiakirjoja, annamme tulostuskomennot peräkkäin. Tulostuskomentojen perusteella asiakirjat järjestetään tulostusjonoon. Kun tulostin on valmis, asiakirja lähetetään ensimmäisenä ensimmäiseksi tulostettavaksi.
Oletetaan, että olet antanut tulostuskomennot 3 dokumentille järjestyksessä doc1, jota seuraa doc2 ja doc3.
Tulostusjono täytetään alla olevan kuvan mukaisesti:
oracle pl sql -virheiden käsittelyn parhaat käytännöt
doc-n, jossa doc on tulostettavaksi lähetetty asiakirja, ja n, on asiakirjan sivujen määrä. Esimerkiksi doc2-10 tarkoittaa, että doc2 on tulostettava ja siinä on 10 sivua. Tässä on koodi, joka simuloi tulostusjonon toimintaa. Käy läpi koodi ja tarkkaile, kuinka jonoa käytetään tässä toteutuksessa.
class Queue: 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 (itse .__ taka = = 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 ('Jono on täynnä !!!') muu: itse .__ taka + = 1 itse .__ elementti [itse .__ takaosa] = data def dequeue (itse): jos (itse.is_tyhjä ()): tulosta ('Jono on tyhjä! !! ') else: data = self .__ elementit [self .__ front] self .__ front + = 1 return data def display (self): hakemistoon alueella (self .__ front, self .__ rear + 1): tulosta (self .__ elementit [index]) def get_max_size (self): return self .__ max_size #Voit käyttää alla olevaa __str __ () tulostaa DS-objektin elementit, kun #debugging def __str __ (self): msg = [] index = self .__ front (indeksi<=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()
Tuotos:
doc1-5 lähetetty tulostettavaksi
doc2-3 lähetetty tulostettavaksi
doc3-6 lähetetty tulostettavaksi
doc1-5 painettu
Jäljellä oleva ei. tulostimen sivuja: 7
doc2-3 painettu
Jäljellä oleva ei. sivuja tulostimessa: 4
Dokumentin 3 tulostaminen epäonnistui. Tulostimessa ei ole tarpeeksi sivuja
- Esimerkki 2:
Yritetään ymmärtää toinen esimerkki, joka käyttää jonon tietorakennetta. Voitteko yrittää ymmärtää koodin ja kertoa, mitä seuraava toiminto tekee?
- def hauska (n):
- aqueue = jono (100)
- alueen lukumäärälle (1, n + 1):
- enqueue (numero)
- tulos = 1
- while (ei (aqueue.is_empty ())):
- numero = AQUUE.DEQUEUE ()
- tulos * = numero
- tulosta (tulos)
Kun funktio fun () kutsutaan välittämällä n,
- rivit 2 - 4 jonottavat elementit välillä 1 - n
- rivit 5-8 löytävät näiden elementtien tuloksen poistamalla jonot yksitellen
Tämän avulla olemme päässeet tämän jonon tietorakenteen artikkelin loppuun. Jos olet ymmärtänyt koodit ja suorittanut ne itse, et ole enää aloittelija jonon tietorakenteessa.
Onko sinulla kysymys meille? Mainitse se tämän artikkelin kommenttiosassa ja otamme sinuun yhteyttä mahdollisimman pian.
Saadaksesi syvällistä tietoa Pythonista sen eri sovellusten kanssa, voit ilmoittautua livenä 24/7 -tuella ja käyttöikällä.