[Powered by Google Translate] [Queue] [Chris Gerber, Harvard University] See on CS50, CS50.TV] Üks kasulik andmestruktuuri talletamiseks järjestatud kogum elemente on järjekorda. Seda kasutatakse siis, kui tunnuste tuleb kõrvaldada samas järjekorras nagu need on loodud. See kontseptsioon on edaspidi FIFO, mis on lühend esimesena sisse, esimesena välja. Et aidata visualiseerida seda, see võib olla kasulik pilti kassas real poes. Kuna inimesed jõuavad nad ootama taga rida. Kassapidaja siis võtab pöördeid teenindavad kliente ees, kes lahkub sealt rida ühe korraga. Computer Science, räägitakse ees järjekorras juhina ja tagasi nagu saba. Näiteks, kui me võiksime seda kasutada rakenduse on ooteloendisse klassi õpilase. Nagu istmed muutuvad kättesaadavaks klassis, inimene eesotsas ootejärjekorras on andnud võimaluse registreeruda klassi. 

Järjekorda saab konstrueerida kasutades kogumine mis salvestab andmeid, et, nagu massiiv või seotud nimekirja. Koos kogumise salvestada objekte järjekorras, vajame ka meetod lisada punkte lõpus järjekorda, mida nimetatakse enqueuing, ja teise objekti eemaldamiseks juht järjekorda, mida nimetatakse dequeuing. Sageli on kasulik lisada teine ​​meetod tagastama praeguse pikkuse järjekorda samuti meetod kontrollida, kas järjekord on tühi. Vaatame, kuidas me võiksime rakendada järjekorda täisarvude C, kasutades massiivi elementide kogu. Esiteks, me luua struktuuri, mida nimetatakse järjekorda hoida meie muutujad. Me kasutame fikseeritud suurus 0 indeksiga massiivi täisarvud salvestada elemente. Me ka muutuja nimega peaga mis talletab indeks element, mis on praegu eesotsas järjekorda. 3. muutuja, mida nimetatakse pikkus, mida kasutatakse jälgida elementide arvu massiivis. Alternatiivina võite kaaluda, kasutades muutuja nimega saba osutada viimane väli element massiivi. Enne kui me kirjutada enam koodi, proovime läbi meie disain. Alustame tühi massiiv pikkusega 0, peaga 0.. Nüüd olgem Lisa järjekorda 4 väärtust - 6, 2, 3 ja 1. Pikkus on nüüd 4, ja pea jääb 0. 

Mis juhtub, kui me dequeue väärtus? Me lühendada kuni 3, määratud arvuni 1, ja tagastab väärtuse 6. See kood võib näeb välja selline. Siin on meil dequeue funktsioon, mis võtab kursor järjekorda - Q - ja viit elementi, mis on teatud tüüpi int. Esiteks me kontrollime pikkuse järjekorda veendumaks, et see on rohkem kui 0, tagama, et on olemas osa on võimalik dequeued. Siis me vaatame elementide massiiv, kohas, pea, ja määrake väärtus element väärtus selles asendis. Siis muudame pea olema järgmine indeks % Võimsust. Siis lühendada järjekorda 1.. Lõpuks oleme tagasi true näitab, et dequeue oli edukas. Kui me dequeue uuesti, pikkus muutub 2 pea muutub ka 2 ja tagastab väärtuse on 2. 

Mis juhtub, kui me Lisa järjekorda teine ​​väärtus näiteks 7? Kuna me olime lõpus järjekorda, peame ümbritsev ja hoidke väärtus element 0 massiivi. Matemaatiliselt see võib olla esindaja, lisades pikkus et indeks pea ja esituskunstide moodul kasutades järjekorda võimsust. Siin see on 2 +2, mis on 4% 4 mis on 0. Tõlkimine selle idee, et kood on meil see funktsioon. Siin näeme Lisa järjekorda funktsioon, mis võtab kursor järjekorda - Q - ja võtab osa on võimalik enqueued, mis on täisarv. Meie kõrval veenduge, et võime järjekorda on ikkagi suurem kui praegune pikkuse järjekorda. Edasi me salvestada osa elemente massiivi kell indeks, mis määratakse pea + pikkus% võimsusega järjekorda. Siis tõsta järjekorra pikkus 1, ja siis tagasi tõsi, et näidata, et Lisa järjekorda funktsioon oli edukas. 

Lisaks kaks ülesannet oleme mainitud, on kaks lisafunktsioone. Esiteks on isEmpty funktsioon, mis võtab kursor järjekorda ja kontrollib, et pikkus on 0.. Teine on pikkus funktsioon, mis võtab kursor järjekorda ja tagastab praeguse pikkus struct. See lühike ülevaade näitas üks võimalik rakendamise järjekorda. Üks piirangud sellele rakendamise on see, et järjekorda on fikseeritud maksimaalne suurus. Kui me püüame lisada rohkem elemente kui järjekorda mahub, meil tekkida vajadus soovi ignoreerida ja tilk element, või me võib eelistada tagasi mingi veaga. Kasutades seotud nimekirja mitte massiiv oleks lihtsam dünaamiliselt suurus järjekorda. Kuid kuna meil ei ole otsest juurdepääsu elemendid seotud nimekirja, kui me ei jälgida saba, oleks meil skaneerida kogu seotud nimekirja jõuda lõpuks iga kord. Me võiksime kaaluda ka massiivi teise andmetüüp, nagu structs, et luua järjekorrad keerukamaid elemente. Mõeldes tagasi meie näide klassi ooteloendisse, Need struktuurid võivad esindada üksikute õpilastega. 

Minu nimi on Chris Gerber, ja see on CS50. [CS50.TV] Ja tagastab - >> Veel üks kord. Ja tagasi true näitab, et - järjekord oli edukas. -% Võimsuse järjekorras - See saab olema lõbus edit. [Naer]