რა არის რიგი და სად გამოიყენება ის?

Question

Accepted Answer

**რიგი** არის **FIFO** (First-In, First-Out) კოლექცია: ელემენტები ემატებიან **უკან** და ამოღებული იქნებიან **წინიდან**, როგორც ხალხის რიგი. ## ოპერაციები ```text enqueue(1) enqueue(2) enqueue(3) dequeue()->1 front ->[1][2][3]<- back front ->[2][3]<- back ``` ## მაგალითი ```python from collections import deque queue = deque() queue.append('a') # enqueue (back) queue.append('b') first = queue.popleft() # dequeue (front) -> 'a' ``` ჩვეულებრივი Python `list` აკეთებს `pop(0)` **O(n)** ოპერაციას, ამიტომ გამოიყენეთ `deque` **O(1)** ორივე ბოლოში. | ოპერაცია | დრო (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## ჩვეულებრივი გამოყენება - **დავალების / სამუშაოს განრიგი** — დამუშავდეს სამუშაო ჩამოსვლის თანმიმდევრობით. - **breadth-first ძებნა (BFS)** — ეწვიეთ კვანძებს დონე-დონე. - **ბუფერირება** — პროდიუსერ/მომხმარებელი კონვეიერი, ბეჭდის რიგი, მოთხოვნის რიგი. ## რატომ არის ეს მნიშვნელოვანი რიგები იძლევიან სამართლიანობასა და თანმიმდევრობას, რაც კრიტიკულია განრიგის შემქმნელებისთვის, მესიჯინგ სისტემებისთვის და BFS-ისთვის. ოდესმე სამუშაო უნდა იყოს დამუშავებული "ჩამოსვლის თანმიმდევრობით", რიგი არის ბუნებრივი არჩევანი.