Mikä on jono (queue) ja missä sitä käytetään?

Question

Accepted Answer

**Jono** on **FIFO** (First-In, First-Out) -kokoelma: alkiot lisätään **takaa** ja poistetaan **edestä**, kuten ihmisten jono. ## Operaatiot ```text enqueue(1) enqueue(2) enqueue(3) dequeue()->1 front ->[1][2][3]<- back front ->[2][3]<- back ``` ## Esimerkki ```python from collections import deque queue = deque() queue.append('a') # enqueue (back) queue.append('b') first = queue.popleft() # dequeue (front) -> 'a' ``` Pelkkä Python `list` tekee `pop(0)` operaatiosta **O(n)** operaation, joten käytä `deque` saavuttaaksesi **O(1)** molemmissa päissä. | Operaatio | Aika (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## Yleiset käyttötarkoitukset - **Tehtävien / töiden ajoitus** — käsittele töitä saapumisjärjestyksessä. - **Leveyshaku (BFS)** — käy solmuja tasolla tasolla. - **Puskurointi** — tuottaja/kuluttaja -liukuhihnat, tulostinjonot, pyyntöjonot. ## Miksi se on tärkeää Jonot pakottavat reiluuden ja järjestyksen, joka on kriittistä ajoituksille, viestijonoille ja BFS:lle. Jos työtä on käsiteltävä "saapumisjärjestyksessä", jono on luonnollinen valinta.