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

merkkijono java korvata

>

>

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ää adeque>alkaencollections>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 anIndexError>. 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 alkaenqueue>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>

taulukoiden luominen lateksista