Kuten pino, jono on lineaarinen tietorakenne, joka tallentaa kohteet First In First Out ( FIFO ) tavalla. Jonossa viimeksi lisätty kohde poistetaan ensin. Hyvä esimerkki jonosta on mikä tahansa kuluttajien jono resurssille, jossa ensin palvellaan ensin tullutta kuluttajaa.

Jonoon liittyvät toiminnot ovat:

• Jono: Lisää kohteen jonoon. Jos jono on täynnä, sen sanotaan olevan ylivuotoehto – Aika monimutkaisuus: O(1)
• Asianmukaisesti: Poistaa kohteen jonosta. Kohteet pompataan samassa järjestyksessä, jossa ne työnnetään. Jos jono on tyhjä, sen sanotaan olevan alivuotoehto – Aika monimutkaisuus: O(1)
• Edessä: Hae etukappale jonosta – Aika monimutkaisuus: O(1)
• Takaosa: Hae viimeinen kohde jonosta – Aika monimutkaisuus: O(1)

Toteuta jono Pythonissa

Jonon toteuttamiseen on useita tapoja Python. Tämä artikkeli kattaa jonon toteuttamisen Python-kirjaston tietorakenteilla ja moduuleilla. Python Queue voidaan toteuttaa seuraavilla tavoilla:

• lista
• kokoelmat.deque
• häntä.häntä

Toteutus listan avulla

Lista on Pythonin sisäänrakennettu tietorakenne, jota voidaan käyttää jonona. Sen sijaan enqueue() and asianmukaisesti () , liitä() ja pop() toimintoa käytetään. Listat ovat kuitenkin melko hitaita tähän tarkoitukseen, koska elementin lisääminen tai poistaminen alussa vaatii kaikkien muiden elementtien siirtämistä yhdellä, mikä vaatii O(n) aikaa.
Koodi simuloi jonoa Python-luettelon avulla. Se lisää elementtejä 'a' , 'b' , ja 'c' jonoon ja poistaa ne sitten jonosta, mikä johtaa tyhjään jonoon lopussa. Tulos näyttää alkuperäisen jonon, jonosta poistetut elementit ( 'a' , 'b' , 'c' ) ja jonon tyhjä tila.

Python 3

Lähtö:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements [] 

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list 

Toteutus collections.dequen avulla

Pythonin Queue voidaan toteuttaa käyttämällä deque-luokkaa kokoelmamoduulista. Deque on suositeltavampi kuin luettelo tapauksissa, joissa tarvitsemme nopeampia liite- ja pop-operaatioita säilön molemmista päistä, koska deque tarjoaa O(1)-aikaisen monimutkaisuuden liittämis- ja pop-operaatioille verrattuna luetteloon, joka tarjoaa O(n)-ajan monimutkaisuuden. . Enqueue- ja deque-funktioiden sijaan käytetään append()- ja popleft()-funktioita.
Koodi käyttää a deque> alkaen collections> moduuli edustamaan jonoa. Se liittää 'a' , 'b' , ja 'c' jonoon ja jättää ne jonoon q.popleft()> , jolloin jono on tyhjä. Kommentoimaton q.popleft()> kun jono on tyhjä, nostaisi an IndexError> . Koodi esittelee jonotoimintoja ja käsittelee tyhjän jonon skenaarion.

Python 3

Lähtö:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([]) 

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque 

Toteutus käyttäen queue.Queuea

Jono on Pythonin sisäänrakennettu moduuli, jota käytetään jonon toteuttamiseen. queue.Queue(maxsize) alustaa muuttujan enimmäiskoon maksimikokoon. Maksimikoko nolla '0' tarkoittaa ääretöntä jonoa. Tämä jono noudattaa FIFO-sääntöä.
Tässä moduulissa on saatavilla useita toimintoja:

• suurin koko – Jonossa sallittujen kohteiden määrä.
• tyhjä() – Palauta True, jos jono on tyhjä, muussa tapauksessa False.
• koko() – Palauta True, jos jonossa on maksimikokoisia kohteita. Jos jono alustettiin arvolla maxsize=0 (oletus), full() ei koskaan palauta arvoa True.
• saada() – Poista ja palauta kohde jonosta. Jos jono on tyhjä, odota, kunnes tuote on saatavilla.
• get_nowait() – Palauta tuote, jos sellainen on heti saatavilla, muuten nosta QueueEmpty.
• laittaa (tuote) – Aseta tuote jonoon. Jos jono on täynnä, odota, kunnes vapaa paikka on käytettävissä, ennen kuin lisäät tuotteen.
• put_nowait(tuote) – Aseta kohde jonoon ilman estämistä. Jos vapaata paikkaa ei ole heti saatavilla, nosta QueueFull.
• qsize() – Palauta jonossa olevien kohteiden määrä.

Esimerkki: Tämä koodi hyödyntää Queue> luokasta alkaen queue> moduuli. Se alkaa tyhjällä jonolla ja täyttää sen ' a’, 'b' , ja 'c' . Jonon purkamisen jälkeen jono tyhjenee ja '1' lisätään. Huolimatta siitä, että se oli tyhjä aiemmin, se pysyy täynnä, koska enimmäiskoko on asetettu 3:een. Koodi näyttää jonotoiminnot, mukaan lukien täyteyden ja tyhjyyden tarkistamisen.

Python 3

Lähtö:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False