DOUG LLOYD: Takže, ak ste sledoval video na zásobníku, je to pravdepodobne bude cítiť ako trochou déjà vu. Bude to veľmi podobným konceptom, len s miernym twist na to. Budeme hovoriť teraz o frontoch. Takže front, podobne ako zásobníka, je ďalší druh dátové štruktúry že môžeme použiť na udržanie Dáta v organizovaným spôsobom. Podobne ako stack, aby mohol byť zavedený ako pole alebo prepojenom zoznamu. Na rozdiel od zásobníka, pravidlá že sme sa použiť na určenie keď sa veci dostať pridané a odstránený z front je trochu inak. Na rozdiel od stohu, ktorý je je štruktúra LIFO, posledný dnu, prvý von, front je FIFO Štruktúra, FIFO, prvý dovnútra, prvý von. Teraz fronty, budete pravdepodobne majú analógiu k front. Ak ste niekedy boli v rade na zábavný park, alebo v banke, je tu akýsi spravodlivosti vykonávacie štruktúru. Prvá osoba vo fronte u banka je prvou osobou, kto dostane hovoriť s prepážke. 

Bolo by to akýsi závod do spodnej časti v prípade, že jediným spôsobom, ako musíš hovoriť s Teller At The Banka mala byť posledná, kto v rade. Každý by vždycky chcú byť posledný, kto v rade, a osoba, ktorá tam bol ako prvý ktorý bol čakal na chvíľu, by mohlo byť celé hodiny, a hodiny a hodiny pred tým, než majú šancu skutočne stiahnuť nejaké peniaze v banke. A tak fronty sú hornín spravodlivosť vykonávacie štruktúru. Ale to nemusí nutne znamenať, že komíny sú zlá vec, len že fronty sú ďalším spôsobom, ako to urobiť. Takže opäť frontu je prvý, najprv out, proti stohu, ktorý ako posledný, first out. Podobne ako stack, Máme dve operácie že môžeme hrať na frontoch. Mená sú Enqueue, čo je pridanie nový prvok na koniec frontu, a dequeue, ktorý je na odstránenie najstaršie element z frontu. Takže budeme pridávať prvky na konci fronty, a budeme odstrániť prvky z frontu. Opäť platí, že sa v zásobníku, sme pridávali prvky na vrchol stohu a odoberanie prvkov z vrcholu zásobníka. Tak s Zaradí, je to pridaním koniec, vybratí z prednej strany. A tak najstarší vec v tú je vždy ďalšia vec, vyjsť von, keď sa pokúsime a dequeue niečo. 

Takže znova, s frontami, môžeme implementácia založená na poli a spojený-list na základe implementácie. Začneme znovu s implementácia založená na poli. Definícia štruktúra Vyzerá dosť podobné. Máme ďalšie pole tam typu dátové hodnoty, takže to môže držať ľubovoľné dátové typy. Máme ísť znova na použitie celé čísla v tomto príklade. 

A rovnako ako s našimi Implementácia zásobníka založená na poli, preto, že sme za použitia poľa, sme nutne má toto obmedzenie, že C druh z vynucuje na nás, čo je, že sme nemajú žiadnu dynamiku v našej schopnosť rásť a zmenšiť pole. Musíme sa rozhodnúť, na začiatku aká je maximálny počet vecí že môžeme dať do toho front, a v tomto prípade, kapacita by mala byť asi libra definovaná konštantou nášho kódu. A na účely tohto video, kapacita bude 10. 

Musíme sledovať predné fronty takže vieme, ktoré element chceme dequeue, a musíme tiež sledovať niečo else-- počet prvkov že máme v našej fronte. Všimnite si, nie sme sledovanie na konci fronty, len veľkosť fronty. A dôvod pre to, dúfajme, stať sa trochu jasnejšie za chvíľu. Potom, čo sme dokončili táto definícia typu, máme nový dátový typ volal fronta, ktorú môžeme teraz deklarovať premenné tohto typu dát. A trochu mätúci, rozhodol som sa volať tento fronty Q, písmeno Q namiesto dátového typu q. 

Takže tu je naša fronta. Jedná sa o štruktúru. Obsahuje tri členmi alebo tri pole, pole kapacity veľkosti. V tomto prípade, kapacita je 10. A toto pole je bude držať celé čísla. V zelenom je predná časť našej frontu, Ďalším prvkom, ktorý bude odobratý, a v červenej bude veľkosť frontu, koľko prvky sú v súčasnej dobe existujúci vo fronte. Takže keď povieme q.front rovní 0, a veľkosť q.size rovná 0-- Dávame 0s do týchto polí. A v tomto bode, sme celkom veľa pripravení začať pracovať s naším fronty. 

Takže prvé operácie môžeme vykonajte je Zaradí niečo, pridať nový prvok koniec fronty. No čo potrebujeme robiť vo všeobecnom prípade? No to funkcia Zaradí potreby na prijatie ukazovateľa na našej fronty. Opäť platí, že ak by sme vyhlásil naše front globálne, nebudeme potrebovať to urobiť nutne, ale všeobecne, sme je potrebné prijať ukazovatele do dátových štruktúr ako je tento, pretože inak, sme okolo value-- sme odovzdaním kópie fronte, a preto nie sme skutočne mení, fronta, že máme v úmysle zmeniť. 

Ďalšia vec, ktorú treba urobiť, je prijať dátový prvok príslušného typu. Opäť platí, že v tomto prípade je to bude celé čísla, ale môžete ľubovoľne deklarovať dátový typ ako hodnotu a použiť všeobecnejšie. To je prvok, chceme Zaradí, chceme pridať na koniec fronty. Potom sme sa skutočne chcú umiestniť tieto dáta vo fronte. V tomto prípade, umiestnenie do Správne umiestnenie nášho poľa, a potom chceme zmeniť veľkosť frontu, koľko prvkov sme V súčasnej dobe máme. 

Tak poďme začať. Tu je, opäť, že všeobecná deklarácia funkcie forma za to, čo Enqueue by mohol vyzerať. A je to tu. Poďme Zaradí číslo 28 do fronty. Tak čo budeme robiť? No, pred našou fronte pri 0 ° C, a veľkosti nášho fronty je 0, a tak sme asi chcete dať číslo 28 v poli číslo prvku 0, jo? Takže sme teraz umiestnené tak, aby sa tam. Takže teraz čo musíme zmeniť? Nechceme meniť predné frontu, pretože chceme vedieť, aký prvok by sme mohli potrebovať, aby dequeue neskôr. Takže dôvod, prečo sme tam front je akýmsi ukazovateľom toho, čo je najstaršia vec na poli. No najstaršia vec na array-- v Skutočnosť, jediná vec, v poli vpravo now-- je 28, ktorý je v mieste poľa 0. Takže nechceme, aby zmeniť túto zelenú linku, pretože to je najstarší element. Skôr chceme zmeniť veľkosť. Takže v tomto prípade, budeme zvýšiť veľkosť na 1. 

Teraz všeobecný akúsi myšlienkou, kde sa ďalší prvok sa chystá ísť vo fronte je pridať týchto dvoch čísel spolu, predné a veľkosť, a že ťa kde rozprávať ďalšie prvok vo fronte sa chystá ísť. Takže teraz poďme Zaradí iné číslo. Poďme Zaradí 33. Takže 33 sa chystá ísť do Poloha poľa 0 a 1. Takže v tomto prípade, bude to ísť do umiestnenia poľa 1, a teraz veľkosť našej frontu je 2. 

Opäť platí, že nie sme mení predná časť našej frontu, 28, pretože je stále najstarší element, a my Ak to-- keď sa nakoniec dostal na dequeuing, odoberanie prvkov z tejto fronty, chceme vedieť kde je najstarší element. A tak sme vždy je potrebné zachovať niektoré ukazovateľ, kde to je. Takže to je to, čo je tu pre 0. To je to, čo prednej strane je tam. 

Poďme v Zaradí ešte jeden prvok, 19. Som si istý, môžete hádať, kde 19 sa chystá ísť. Bude to ísť do poľa číslo umiestnenia 2. To je 0 a 2. A teraz je veľkosť našej frontu je 3. Máme 3 elementy v tom. Takže ak sme mali, a nebudeme práve teraz, Zaradí ďalší prvok, to by ísť do miesta poľa číslo 3, a veľkosť našej fronty bude 4. Preto sme enqueued niekoľko prvkov teraz. Teraz začnime na ich odstránenie. Poďme dequeue z frontu. 

Takže podobne ako pop, ktorý je trochu analógu tohto pre komíny, dequeue treba akceptovať Ukazovateľ na queue-- znovu ak je to v celosvetovom meradle deklarovaná. Teraz chceme zmeniť umiestnenie z frontu. To je miesto, kde to tak nejako príde do hry, že predné variabilné, pretože akonáhle sme sa odstrániť prvok, chceme presunúť do ďalšieho najstarší prvok. 

Potom chceme znížiť veľkosť frontu, a potom sme sa chcete vrátiť hodnotu , Ktorý bol odobratý z frontu. Opäť platí, že nechceme, aby jednoducho odhodiť to. Sme pravdepodobne extrahujete to z queue-- ktorom sme dequeuing to, pretože nám záleží na tom. Takže chceme, aby táto funkcia sa vrátiť dátový prvok typu hodnoty. Opäť platí, že v tomto prípade, že hodnota je celé číslo. 

Takže teraz poďme dequeue niečo. Poďme odstrániť prvok z fronty. Ak hovoríme, int x rovná & q, ampersand q-- Znovu to je ukazovateľ na tento q dát structure-- čo element sa bude dequeued? V tomto prípade, pretože sa jedná o prvom in, first out dátové štruktúry, FIFO, Prvá vec, ktorú sme sa dať do toho fronta bola 28, a teda v tomto prípade, budeme brať 28 z frontu, nie 19, ktorý je čo by sme urobili, či to bola hromada. Chystáme sa prijať 28 z frontu. 

Podobne k tomu, čo sme to urobili s stoh, nie sme v skutočnosti chystá vymazať 28 z frontu samotnej, my len tak druhu z predstierať, že tam nie je. Takže to bude tam zostať v pamäti, ale my sme jednoducho bude druh ignorovať pohybom ďalšie dve polia našej q dát štruktúra. Chystáme sa zmeniť front. Q.front sa teraz chystá byť 1, pretože to je teraz najstarší prvok máme v našej front, pretože sme už odstránené 28, čo bol bývalý najstarší element. 

A teraz, chceme zmeniť veľkosť fronty na dva prvky namiesto troch. Teraz pamätať predtým som povedal, keď sme Chcete pridať prvky do fronty, dáme to v mieste poľa ktorý je súčtom predné a veľkosti. Takže v tomto prípade, sme stále uvedenie to, ďalší element vo fronte, do umiestnenia poľa 3, a budeme vidieť, že v druhom. 

Preto sme teraz naše dequeued Prvý element z frontu. Urobme to znova. Poďme odstrániť ďalšie element z frontu. V prípade, aktuálny najstaršie prvkom je umiestnenie poľa 1. To je to, čo nám hovorí q.front. To zelené polia nám hovorí, že že je to najstaršie element. A tak, x sa stane 33. Budeme tak nejako zabudol 33, že existuje v poli, a budeme hovoriť, že teraz, Nový najstaršie element vo fronte je v mieste poľa 2 a veľkosť fronty, počet prvkov máme vo fronte, je 1. Teraz poďme Zaradí niečo, a ja nejako dal to preč pred sekundou, ale ak chceme dať 40 do front, kde je 40 ísť? Dobre sme sa ho uvedenia v q.front a fronty veľkosti, a tak to dáva zmysel, aby skutočne dať 40 sem. Teraz si všimnite, že v nejaký bod, ideme sa dostať do konca roka Naše pole vnútri q, ale že vybledla 28 a 33-- sú to v skutočnosti, technicky otvorené priestory, je to tak? A tak môžeme eventually-- že pravidlo pridania tí dvaja together-- sme môže nakoniec treba mod podľa veľkosti kapacity takže môžeme zabaliť okolo. 

Takže ak sa dostaneme do prvku číslo 10, keď sme nahradí ju v elemente číslo 10, mali by sme skutočne dať do lokalite poľa 0. A keď sme sa chystali array ma location-- ospravedlňte, ak sme pridali je spolu, a dostali sme sa na číslo 11 z nich by byť tam, kde by sme dať to, ktorá neexistuje v tomto array-- to by mal ísť mimo hraciu plochu. Mohli by sme mod o 10 a dal že v mieste poľa 1. Tak to je, ako fungujú fronty. Vždycky ísť zľava doprava a prípadne zábal okolo. A viete, že sú plnej výške, ak veľkosť, že červené pole, stáva rovnakú kapacitu. A tak potom, čo sme pridali 40 do front, no čo musíme urobiť? No, najstarší element vo fronte je stále 19, takže nechceme meniť predné frontu, ale teraz máme dve prvky vo fronte, a tak chceme zvýšiť našej veľkosti od 1 do 2. 

To je celkom veľa to s pracovať s front založená na poli, a podobne ako komín, tam je tiež spôsob, realizovať fronty ako Google zoznamu. Teraz, ak tento typ štruktúra dát vyzerá povedome vám, to je. Nie je to jednotlivo spájať zoznam, je to dvojnásobne previazaný zoznam. A teraz, ako stranou, to je v skutočnosti je to možné realizovať front ako jednotlivo spájať zoznam, ale Myslím si, že pokiaľ ide o vizualizáciu, to vlastne mohlo pomôcť k zobrazenie to ako dvojnásobne Google zoznamu. Ale je to určite možné robiť to ako single previazaný zoznam. 

Takže poďme sa pozrieť na čo by to mohlo vyzerať. Ak chceme, aby enquue-- takže teraz, opäť sme prepnutie na Google-list na základe modelu tu. Ak chceme, aby Zaradí, chceme pridať nový prvok, dobre Čo musíme urobiť? No, v prvom rade, pretože budeme pridávať na koniec a odstránenie z Spočiatku sme pravdepodobne chcú zachovať odkazy na oba hlava a chvost Google zoznamu? Chvost je ďalší termín pre koniec zoznamu Google, posledný prvok v pripojenom zozname. A to bude asi, opäť, byť prospešné pre nás ak sú globálne premenné. Ale teraz, keď chceme pridať nový prvok čo musíme urobiť? To, čo sme práve [? Malak?], Alebo dynamicky prideliť náš nový uzol pre seba. A potom, ako keď sme sa pridať niektorý prvok do dvojnásobne Google zoznamu my, jednoducho musí triediť of-- tie posledné tri kroky tu sú všetko len o presunutie ukazovatele v správnym spôsobom tak, že prvok dostane pridaný do reťaz bez prerušenia reťazca alebo robiť nejaký chyby alebo má nejaký nehody štát, v ktorom by sme náhodou orphan niektoré prvky našej fronty. Tu je to, čo by to mohlo vyzerať. Chceme pridať prvok 10 na konci tejto fronty. Takže najstarší prvok tu je reprezentovaný hlavy. To je prvá vec, ktorú kladieme do tohto hypotetického frontu tu. A chvost, 13, je najviac nedávno pridal prvok. A tak, ak chceme, aby do 10 Zaradí Táto fronta, chceme, aby to po 13. A tak budeme dynamicky prideliť priestor pre nový uzol a skontrolujte, či null, aby sa uistil nemáme zlyhanie pamäte. Potom sme sa chystáte miesto 10 do tohto uzla, a teraz musíme byť opatrní o tom, ako organizovať ukazovatele takže neporušujú reťaz. 

Môžeme nastaviť 10 je predchádzajúca pole poukázať späť do starého chvosta a pretože '10 bude nový chvost v určitom okamihu v čase, keď všetky tieto reťaze sú pripojené, nič sa príde po 10 práve teraz. A tak ďalší ukazovateľ 10 je bude ukazovať na null, a potom po tom, čo sme to urobiť, potom, čo sme pripojený 10 dozadu k reťazi, môžeme vziať staré hlavu, alebo, ospravedlnenie ja, starý chvost fronty. Starý koniec frontu, 13, a urobiť z neho poukazujú na 10. A teraz, v tomto bode, máme enqueued číslo 10 do tejto fronty. Všetko, čo musíme urobiť, je teraz len presunúť tail, aby ukazoval na 10 namiesto toho, aby 13. 

Dequeuing je vlastne veľmi podobné praskanie zo zásobníka, ktorý je realizovaný ako spájať zoznam ak ste videli stohy videa. Všetko, čo musíme urobiť, je začať u začiatok, nájsť druhý prvok, uvoľniť prvý prvok, a presuňte hlavu prejdite k druhému prvku. Pravdepodobne lepšie ho vizualizovať jednoducho byť extra jasné, o tom. Tak tu je zase naša fronta. 12 je najstaršia element v našej fronte, hlavy. 10 je najnovší prvok v našej fronte, chvostom. 

A tak, keď chceme, na dequeue prvok, chceme odstrániť najstarší prvok. Tak čo budeme robiť? Tak sme si stanovili ukazovatele traversal ktorý začína v čele, a my sme ho presunúť tak, aby sa poukazuje na druhý prvok z toho queue-- niečo tým, že hovorí tráv sa rovná tráv šípku, napríklad, by sa pohyboval tráv tu poukázať na 15, ktorý po tom, čo sme dequeue 12, alebo potom, čo sme odobratie 12, bude sa stal vtedajší najstarší element. 

Teraz máme držať na prvý prvok cez ukazovateľ hlavy a druhý prvok pomocou ukazovateľa tráv. Teraz môžeme bez hlavy, a potom môžeme teda pred 15. nič príde ešte. Takže môžeme zmeniť 15 je predchádzajúca ukazovateľ poukázať na null, a my len presunúť hlavu nad. A tam ideme. Teraz máme úspešne sa dequeued 12, a teraz sme majú ďalšie fronty 4 prvkov. To je skoro všetky tam je front, ako pole-based a spojený-list báze. Som Doug Lloyd. To je CS 50.