Radhët: i pari brenda, i pari jashtë

I pari brenda, i pari jashtë

Një radhë (queue) është pasqyra e një stack-u. Aty ku një stack shërben më parë njësinë më të fundit, një radhë shërben më parë më të vjetrën: çfarëdo që hyri më herët del më herët. Emri i shkurtër është FIFO, nga anglishtja first in, first out.

Ti rri në radhë çdo ditë. Përfytyro rreshtin te arka e një dyqani. Njerëzit e rinj bashkohen në fund. Personi që shërbehet i radhës është gjithmonë në krye, ai që ka pritur më gjatë. Askush nuk kërcen përpara, dhe askush në krye nuk kapërcehet. Ajo drejtësi, i pari që vjen i pari shërbehet, është e gjithë poenta e strukturës.

Dy veprime e drejtojnë një radhë. Enqueue shton një njësi në fund. Dequeue heq njësinë në krye dhe ta jep mbrapsht. Vër re se dy veprimet veprojnë në skaje të kundërta, ndryshe nga një stack ku të dyja veprojnë te maja. Ky është ndryshimi i vogël që e kthen LIFO-n në FIFO.

Ndërtimi i një radhe nga një listë

Një listë Python mund të shërbejë si radhë. Përdor .append() për enqueue në fund, saktësisht si më parë. Për dequeue nga kryeja, përdor .pop(0), që heq dhe kthen njësinë në indeksin 0:

radha = []
radha.append("zgjohu")        # enqueue
radha.append("mëngjesi")      # enqueue
radha.append("shko në punë")  # enqueue

print(radha.pop(0))   # zgjohu        (i pari brenda, i pari jashtë)
print(radha.pop(0))   # mëngjesi
print(radha.pop(0))   # shko në punë

Njësitë largohen në të njëjtën radhë që erdhën, që është pikërisht ajo që një stack nuk do ta bënte. Si te një stack, dequeue nga një radhë bosh është gabim, ndaj kontrollo me if radha: para se të bësh pop.

Ku shfaqen radhët

Radhët shfaqen kudo ku gjërat duhen trajtuar sipas radhës në të cilën erdhën:

• Një radhë printimi. Kur disa dokumente i dërgohen një printeri, ato printohen sipas radhës së marrjes, jo cilido që bërtet më shumë. Puna e parë e dërguar është e para e printuar.
• Një listë detyrash a ngjarjesh. Ndërsa ndodhin klikime e shtypje tastesh, secila shtohet në fund të një radhe, që programi t'i trajtojë një nga një, me radhë, pa humbur asnjë.
• Çdo radhë e drejtë pritjeje: bileta mbështetjeje, porosi në një kuzhinë, kërkesa te një server. I pari që pyet është i pari që shërbehet.

Filli i përbashkët është drejtësia përmes radhës. Kur "kush ishte këtu i pari?" është pyetja e duhur, një radhë i përgjigjet nga vetë ndërtimi.

Një shembull i punuar: shërbimi i klientëve me radhë

Le të themi se një furrë e vogël merr porosi dhe i plotëson një nga një, më e vjetra e para. Një radhë e modelon këtë drejtpërdrejt. Klientët bëhen enqueue ndërsa vijnë, dhe furrtari bën dequeue për të shërbyer atë që ka pritur më gjatë:

def sherbe_te_gjithe(klientet):
    radha = []
    for emri in klientet:
        radha.append(emri)          # çdo klient bashkohet në fund

    while radha:
        aktuali = radha.pop(0)      # shërbe kryeun, atë që pret më gjatë
        print("Po shërbehet:", aktuali)

sherbe_te_gjithe(["Ana", "Beni", "Kara"])

Kjo shtyp emrat sipas radhës së ardhjes: Ana, pastaj Beni, pastaj Kara. Cikli i parë i rreshton të gjithë në fund të radhës. Cikli while radha: pastaj bën dequeue nga kryeja derisa s'mbetet askush, dhe meqë .pop(0) merr gjithmonë kryeun, ardhësi më i hershëm shërbehet gjithmonë i radhës. Ndërroje radhën me një stack këtu dhe Kara do të shërbehej para Anës, gjë që asnjë furrë e drejtë s'do ta lejonte. Zgjedhja e FIFO-s është ajo që e bën radhën të drejtë.

Do ta shohësh të shpjeguar? Ja leksioni i regjistruar i Code for Albania për këtë temë.

Provo veten

1. Thuaj rregullin FIFO në një fjali, dhe jep një situatë të përditshme ku shërbimi më parë i njësisë më të vjetër është qartë zgjedhja e drejtë.
2. Një radhë mbi një listë Python bën enqueue me .append() dhe dequeue me .pop(0). Në cilin skaj vepron secili veprim, dhe si ndryshon kjo nga një stack?
3. Në shembullin e furrës, çfarë do të ndryshonte te dalja nëse do ta zëvendësoje radhën me një stack, dhe pse kjo do të ishte e padrejtë ndaj klientëve?