Kaip ir krūva, eilė yra linijinė duomenų struktūra, kuri saugo elementus „First In First Out“ ( FIFO ) būdas. Esant eilei, pirmiausia pašalinamas mažiausiai neseniai pridėtas elementas. Geras eilės pavyzdys yra bet kokia vartotojų eilė prie išteklių, kur pirmas aptarnaujamas vartotojas, kuris buvo pirmasis.

Su eile susijusios operacijos yra šios:

• Eilė: Prideda elementą į eilę. Jei eilė pilna, vadinasi, tai yra perpildymo sąlyga – laiko sudėtingumas: O(1)
• Atitinkamai: Pašalina elementą iš eilės. Elementai iššokami ta pačia tvarka, kuria jie stumiami. Jei eilė tuščia, tai laikoma nepakankamo srauto sąlyga – laiko sudėtingumas: O(1)
• Priekyje: Gaukite priekinį elementą iš eilės – laiko sudėtingumas: O(1)
• Galinis: Gaukite paskutinį elementą iš eilės – laiko sudėtingumas: O(1)

Įdiekite eilę „Python“.

Yra įvairių būdų, kaip įdiegti eilę Python. Šiame straipsnyje aprašomas eilės įgyvendinimas naudojant duomenų struktūras ir modulius iš Python bibliotekos. Python eilę galima įdiegti šiais būdais:

• sąrašą
• kolekcijos.deque
• uodega.uodega

Įgyvendinimas naudojant sąrašą

Sąrašas yra Python integruota duomenų struktūra, kurią galima naudoti kaip eilę. Vietoj enqueue() ir atitinkamai () , pridėti () ir pop () funkcija naudojama. Tačiau sąrašai šiam tikslui yra gana lėti, nes įterpiant ar ištrinant elementą pradžioje reikia visus kitus elementus perkelti po vieną, o tam reikia O(n) laiko.
Kodas imituoja eilę naudodamas Python sąrašą. Tai prideda elementų 'a' , 'b' , ir 'c' į eilę, o tada iškeliauja iš eilės, todėl eilė pabaigoje lieka tuščia. Išvestyje rodoma pradinė eilė, elementai, išvesti iš eilės ( 'a' , 'b' , 'c' ), o eilės būsena tuščia.

Python3

Išvestis:

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 

Įgyvendinimas naudojant kolekcijas.deque

Eilė Python gali būti įdiegta naudojant deque klasę iš rinkinių modulio. Deque yra teikiama pirmenybė, o ne sąrašas tais atvejais, kai reikia greitesnių pridėjimo ir iššokimo operacijų iš abiejų sudėtinio rodinio galų, nes deque suteikia O(1) laiko sudėtingumą pridėjimo ir iššokimo operacijoms, palyginti su sąrašu, kuris suteikia O(n) laiko sudėtingumą. . Vietoj enqueue ir deque naudojamos funkcijos append() ir popleft().
Kode naudojama a deque> nuo collections> modulis, vaizduojantis eilę. Tai prideda 'a' , 'b' , ir 'c' į eilę ir nurašo juos su q.popleft()> , todėl eilė tuščia. Nekomentuojama q.popleft()> po to, kai eilė tuščia, kiltų an IndexError> . Kodas parodo eilės operacijas ir tvarko tuščios eilės scenarijų.

Python3

Išvestis:

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 

Diegimas naudojant eilę.Eilę

Eilė yra integruotas Python modulis, naudojamas eilei įgyvendinti. queue.Queue(maxsize) inicijuoja kintamąjį iki didžiausio maksimalaus dydžio. Maksimalus dydis nulis „0“ reiškia begalinę eilę. Ši eilė atitinka FIFO taisyklę.
Šiame modulyje yra įvairių funkcijų:

• maksimalus dydis – Eilėje leidžiamų prekių skaičius.
• tuščia() – Grąžinkite True, jei eilė tuščia, kitu atveju – False.
• pilnas () – Grąžinkite „True“, jei eilėje yra maksimalaus dydžio elementų. Jei eilė buvo inicijuota su maxsize=0 (numatytasis), full() niekada nepateikia True.
• gauti () – Pašalinti ir grąžinti prekę iš eilės. Jei eilė tuščia, palaukite, kol prekė atsiras.
• get_nowait() – Grąžinkite prekę, jei ji iš karto pasiekiama, kitu atveju pakelkite eilęEmpty.
• įdėti (prekė) – Įdėkite prekę į eilę. Jei eilė pilna, prieš įtraukdami prekę palaukite, kol atsiras laisva vieta.
• įdėti_dabar (prekė) – Įdėkite prekę į eilę neužblokuodami. Jei iš karto nėra laisvos vietos, pakelkite „QueueFull“.
• qsize() – Grąžinti eilėje esančių elementų skaičių.

Pavyzdys: Šis kodas naudoja Queue> klasė iš queue> modulis. Ji prasideda tuščia eile ir užpildoma „ a', 'b' , ir 'c' . Nutraukus eilę, eilė tampa tuščia ir pridedamas „1“. Nepaisant to, kad anksčiau buvo tuščias, jis lieka pilnas, nes nustatytas didžiausias dydis 3. Kodas parodo eilės operacijas, įskaitant pilnumo ir tuštumos tikrinimą.

Python3

Išvestis:

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