Radha (lloji abstrakt i të dhënave)

Queue
Paraqitja e një radhe FIFO (first in, first out)
Kompleksiteti kohor në shënimin O e madhe Veprimi Mesatarja Rasti më i keq Kërkimi O(n) O(n) Futja O(1) O(1) Fshirja O(1) O(1) Kompleksiteti hapësinor Hapësira O(n) O(n)

Në shkencën kompjuterike, një radhë është një koleksion entitetesh që mbahen në një sekuencë dhe mund të modifikohen duke shtuar entitete në njërin skaj të sekuencës dhe heqjen e entiteteve nga skaji tjetër i sekuencës. Sipas konventës, fundi i sekuencës në të cilën shtohen elementët quhet pjesa e pasme, bishti ose pjesa e pasme e radhës, dhe fundi në të cilin hiqen elementët quhet kreu ose pjesa e përparme e radhës, në mënyrë analoge me fjalët e përdorura kur njerëzit rreshtohen për të pritur mallra ose shërbime.

Veprimi i shtimit të një elementi në pjesën e pasme të radhës njihet si enqueue, dhe operacioni i heqjes së një elementi nga pjesa e përparme njihet si dequeue . Veprimi të tjera mund të lejohen gjithashtu, shpesh duke përfshirë një veprim të shikimit ose të përparmë që kthen vlerën e elementit tjetër që do të hiqet pa e hequr atë.

Operacionet e një radhe e bëjnë atë një strukturë e para hyn, e para del (FIFO) . Në një strukturë të dhënash FIFO, elementi i parë i shtuar në radhë do të jetë i pari që hiqet. Kjo është e njëvlerëshme me kërkesën që pasi të shtohet një element i ri, të gjithë elementët që janë shtuar më parë duhet të hiqen përpara se të hiqet elementi i ri. Një radhë është një shembull i një strukture lineare të të dhënave. Radhët janë të zakonshme në programet kompjuterike, ku ato zbatohen si struktura të dhënash të shoqëruara me rutinat e aksesit, si një strukturë abstrakte e të dhënave ose në gjuhët e orientuara nga objekti si klasa. Implementimet e zakonshme janë buferat rrethorë dhe listat e lidhura.

Radhët ofrojnë shërbime në shkencë kompjuterike, transport dhe kërkime operacional ku entitete të ndryshme si të dhëna, objekte, persona ose ngjarje ruhen dhe mbahen për t'u përpunuar më vonë. Në këto kontekste, radha kryen funksionin e një buffer-i . Një përdorim tjetër i radhëve është në zbatimin e kërkimit të parë në gjerësi.

Implementimi i radhës

Teorikisht, një karakteristikë e një radhe është se ajo nuk ka një nxënësi specifike. Pavarësisht se sa elementë janë përfshirë tashmë, një element i ri mund të shtohet gjithmonë. Mund të jetë gjithashtu bosh, në të cilën pikë heqja e një elementi do të jetë e pamundur derisa të shtohet përsëri një element i ri.

Ka disa implementime efikase të radhëve FIFO. Një zbatim efikas është ai që mund të kryejë veprimet - enqueue dhe dequeue - në kohën O(1) .

• Lista e lidhur
  • Një listë e lidhur dyfish ka futje dhe fshirje O(1) në të dy skajet, kështu që është një zgjedhje e natyrshme për radhët.
  • Një listë e rregullt e lidhur veçmas ka vetëm futje dhe fshirje efikase në një fund. Sidoqoftë, një modifikim i vogël - duke mbajtur një tregues në nyjen e fundit përveç të parës - do t'i mundësojë atij të zbatojë një radhë efikase.
• Një deque e implementuar duke përdorur një vektor dinamik të modifikuar

Radhët dhe gjuhët e programimit

Radhët mund të zbatohen si një lloj i veçantë i të dhënave, ose mund të konsiderohet një rast i veçantë i një radhe të dyfishtë (deque) dhe nuk jo të zbatuara veçmas. Për shembull, Perl dhe Ruby lejojnë shtyrjen dhe heqjen nga një vektor tek të dyja skajet, kështu që mund të përdoren funksionet shtytje dhe zhvendosje për enqueue dhe dequeue në radhë një listë (ose, në të kundërt, mund të përdoren unshift dhe pop ), edhe pse në disa në rastet kur këto veprime nuk janë efikase.

Libraria standarde e shablloneve të C++ ofron një klasë të modeluar " queue " e cila është e kufizuar vetëm në veprimet push/pop. Që nga J2SE5.0, libraria e gjuhës Java përmban një ndërfaqe Queue që specifikon veprimet e radhës; klasat implementuese përfshijnë LinkedList dhe (që nga J2SE 1.6) ArrayDeque . PHP ka një klasë SplQueue dhe librari të palëve të treta si beanstalk'd dhe Gearman .

Shembull

Një radhë e thjeshtë e implementuar në JavaScript :

class Queue {
    constructor() {
        this.items = [];
    }

    enqueue(element) {
        this.items.push(element);
    }

    dequeue() {
        return this.items.shift();
    }
}

Zbatim thjesht funksional

Radhët mund të zbatohen gjithashtu si një strukturë e pastër funksionale e të dhënave . Ka dy zbatime. E para arrin vetëm $O(1)$ mesatarisht për veprim. Domethënë koha e amortizuar është $O(1)$, por veprimet individuale mund të zgjasin $O(n)$ ku n është numri i elementeve në radhë. Zbatimi i dytë quhet një radhë në kohë reale dhe lejon që radha të jetë e qëndrueshme me operacionet në kohën më të keqe O(1). Është një zbatim më i ndërlikuar dhe kërkon lista përtace me memoizim .

Radhë në kohë reale

Radha në kohë reale arrin kohë $O(1)$ për të gjitha veprimet, pa amortizim. Ky diskutim do të jetë teknik, ndaj kujtoni se, për një listë $l$, $|l|$ shënon gjatësinë e saj, se NIL përfaqëson një listë boshe dhe $\operatorname {CONS} (h,t)$ paraqet listën koka e së cilës është h dhe bishti t .

Struktura e të dhënave e përdorur për të zbatuar radhët tona përbëhet nga tre lista të lidhura njëshe $(f,r,s)$ ku f është pjesa e përparme e radhës dhe r është pjesa e pasme e radhës në rend të kundërt. Invarianti i strukturës është se s është pjesa e pasme e f pa $|r|$ elementet e para, pra $|s|=|f|-|r|$ . Bishti i radhës $(\operatorname {CONS} (x,f),r,s)$ është atëherë pothuajse $(f,r,s)$ dhe duke futur një element x në $(f,r,s)$ është pothuajse $(f,\operatorname {CONS} (x,r),s)$ . Thuhet pothuajse, sepse në të dyja këto rezultate, $|s|=|f|-|r|+1$ . Atëherë duhet thirrur një funksion ndihmës $aux$ që invarianti të plotësohet. Duhet të merren parasysh dy raste, në varësi të faktit nëse $s$ është lista bosh, në këtë rast $|r|=|f|+1$, ose jo. Përkufizimi formal është $\operatorname {aux} (f,r,\operatorname {Cons} (\_,s))=(f,r,s)$ dhe $\operatorname {aux} (f,r,{\text{NIL}})=(f',{\text{NIL}},f')$ ku $f'$ është f e ndjekur nga r anasjelltas.

Le të shënojmë $\operatorname {reverse} (f,r)$ funksionin i cili kthen f të ndjekur nga r e përmbysur. Për më tepër, le të supozojmë se $|r|=|f|+1$, pasi është rasti kur thirret ky funksion. Më saktësisht, ne përcaktojmë një funksion përtac $\operatorname {rotate} (f,r,a)$ i cili merr si hyrje tri lista të tilla që $|r|=|f|+1$, dhe kthejnë përngjitjen e f, të r të kundërt dhe të a . Pastaj $\operatorname {reverse} (f,r)=\operatorname {rotate} (f,r,{\text{NIL}})$ . Përkufizimi induktiv i rrotullimit është $\operatorname {rotate} ({\text{NIL}},\operatorname {Cons} (y,{\text{NIL}}),a)=\operatorname {Cons} (y,a)$ dhe $\operatorname {rotate} (\operatorname {CONS} (x,f),\operatorname {CONS} (y,r),a)=\operatorname {Cons} (x,\operatorname {rotate} (f,r,\operatorname {CONS} (y,a)))$ . Koha e ekzekutimit të saj është $O(r)$, por, meqë përdoret vlerësimi përtac, llogaritja vonohet derisa rezultatet të detyrohen nga llogaritja.

Lista s në strukturën e të dhënave ka dy qëllime. Kjo listë shërben si një numërues për $|f|-|r|$, me të vërtetë, $|f|=|r|$ nëse dhe vetëm nëse s është lista boshe. Ky numërues na lejon të sigurohemi që pjesa e pasme të mos jetë kurrë më e gjatë se lista e përparme. Për më tepër, duke përdorur s, që është një bisht i f, detyron llogaritjen e një pjese të listës (përtace) f gjatë çdo veprimi tail dhe insert . Prandaj, kur $|f|=|r|$, lista f është totalisht e detyruar. Nëse nuk do të ishte kështu, paraqitja e brendshme e f mund të ishte një shtojcë e shtojcës së ... i shtojcës, dhe detyrimi nuk do të ishte më një veprim i vazhdueshëm në kohë.