Kas yra eilė ir kur ji naudojama?

Question

Accepted Answer

**Eilė** yra **FIFO** (First-In, First-Out) kolekcija: elementai pridedami **gale** ir pašalinami iš **priekio**, kaip žmonių eilė. ## Operacijos ```text enqueue(1) enqueue(2) enqueue(3) dequeue()->1 front ->[1][2][3]<- back front ->[2][3]<- back ``` ## Pavyzdys ```python from collections import deque queue = deque() queue.append('a') # enqueue (back) queue.append('b') first = queue.popleft() # dequeue (front) -> 'a' ``` Paprasta Python `list` daro `pop(0)` **O(n)** operacija, todėl naudokite `deque` dėl **O(1)** abiejuose galuose. | Operacija | Laikas (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## Dažniaustas naudojimas - **Užduoties / darbo planavimas** — apdoroti darbą atvykimo tvarka. - **Pirmiausia į plotį paieška (BFS)** — apsilankyti mazguose lygiu po lygiu. - **Buferravimas** — gamintojo/vartotojo vamzdynai, spausdintuvo eilės, užklausų eilės. ## Kodėl tai svarbu Eilės užtikrina sąžiningumą ir tvarką, o tai yra labai svarbu dėl planuotojų, pranešimų sistemų ir BFS. Kai tik darbas turi būti apdorotas "atvykimo tvarka", eilė yra natūralus pasirinkimas.