DOUG LLOYD: Takže, pokud jste sledoval video na zásobníku, je to pravděpodobně bude cítit jako trochou déjà vu. Bude to velmi podobným konceptem, jen s mírným twist na to. Budeme mluvit teď o frontách. Takže fronta, podobně jako zásobníku, je další druh datové struktury že můžeme použít k udržení Data v organizovaným způsobem. Podobně jako stack, aby mohl být zaveden jako pole nebo propojeném seznamu. Na rozdíl od zásobníku, pravidla že jsme se použít k určení když se věci dostat přidáno a odstraněn z fronta je trochu jinak. Na rozdíl od stohu, který je je struktura LIFO, poslední dovnitř, první ven, fronta je FIFO Struktura, FIFO, první dovnitř, první ven. Nyní fronty, budete pravděpodobně mají analogii k front. Pokud jste někdy byli ve frontě na zábavní park, nebo v bance, je tu jakýsi spravedlnosti prováděcí strukturu. První osoba ve frontě u banka je první osobou, kdo dostane mluvit s přepážce. 

Bylo by to jakýsi závod do spodní části v případě, že jediným způsobem, jak musíš mluvit s Teller At The Banka měla být poslední, kdo v řadě. Každý by vždycky chtějí být poslední, kdo v řadě, a osoba, která tam byl jako první který byl čekal na chvíli, by mohlo být celé hodiny, a hodiny a hodiny před tím, než mají šanci skutečně stáhnout nějaké peníze v bance. A tak fronty jsou hornin spravedlivost prováděcí strukturu. Ale to nemusí nutně znamenat, že komíny jsou špatná věc, jen že fronty jsou dalším způsobem, jak to udělat. Takže opět fronty je první, nejprve out, proti stohu, který jako poslední, first out. Podobně jako stack, Máme dvě operace že můžeme hrát na frontách. Jména jsou Enqueue, což je přidání nový prvek na konec fronty, a dequeue, který je k odstranění nejstarší element z fronty. Takže budeme přidávat prvky na konci fronty, a budeme odstranit prvky z fronty. Opět platí, že se v zásobníku, jsme přidávali prvky na vrchol stohu a odebírání prvků z vrcholu zásobníku. Tak s Zařadí, je to přidáním konec, vyjmutí z přední strany. A tak nejstarší věc v tu je vždy další věc, vyjít ven, když se pokusíme a dequeue něco. 

Takže znovu, s frontami, můžeme implementace založená na poli a spojený-list na základě implementace. Začneme znovu s implementace založená na poli. Definice struktura Vypadá dost podobné. Máme další pole tam typu datové hodnoty, takže to může držet libovolné datové typy. Máme jít znovu k použití celá čísla v tomto příkladu. 

A stejně jako s našimi Implementace zásobníku založená na poli, proto, že jsme za použití pole, jsme nutně má toto omezení, že C druh z vynucuje na nás, což je, že jsme nemají žádnou dynamiku v naší schopnost růst a zmenšit pole. Musíme se rozhodnout, na začátku jaká je maximální počet věcí že můžeme dát do toho fronta, a v tomto případě, kapacita by měla být asi libra definovaná konstantou našeho kódu. A pro účely tohoto video, kapacita bude 10. 

Musíme sledovat přední fronty takže víme, které element chceme dequeue, a musíme také sledovat něco else-- počet prvků že máme v naší frontě. Všimněte si, nejsme sledování na konci fronty, jen velikost fronty. A důvod pro to, doufejme, stát se trochu jasnější za chvíli. Poté, co jsme dokončili tato definice typu, máme nový datový typ volal fronta, kterou můžeme nyní deklarovat proměnné tohoto typu dat. A poněkud matouce, rozhodl jsem se volat tento fronty Q, písmeno Q namísto datového typu q. 

Takže tady je naše fronta. Jedná se o strukturu. Obsahuje tři členy nebo tři pole, pole kapacity velikosti. V tomto případě, kapacita je 10. A toto pole je bude držet celá čísla. V zeleném je přední část naší fronty, Dalším prvkem, který bude odebrán, a v červené bude velikost fronty, kolik prvky jsou v současné době existující ve frontě. Takže když řekneme q.front rovni 0, a velikost q.size rovná 0-- Dáváme 0s do těchto polí. A v tomto bodě, jsme docela hodně připraveni začít pracovat s naším fronty. 

Takže první operace můžeme proveďte je Zařadí něco, přidat nový prvek konec fronty. No co potřebujeme dělat v obecném případě? No to funkce Zařadí potřeby k přijetí ukazatele na naší fronty. Opět platí, že pokud bychom prohlásil naše fronta globálně, nebudeme potřebovat to udělat nutně, ale obecně, jsme je třeba přijmout ukazatele do datových struktur jako je tento, protože jinak, jsme kolem value-- jsme předáním kopie frontě, a proto nejsme skutečně mění, fronta, že máme v úmyslu změnit. 

Další věc, kterou je třeba udělat, je přijmout datový prvek příslušného typu. Opět platí, že v tomto případě je to bude celá čísla, ale můžete libovolně deklarovat datový typ jako hodnotu a použít obecněji. To je prvek, chceme Zařadí, chceme přidat na konec fronty. Pak jsme se skutečně chtějí umístit tato data ve frontě. V tomto případě, umístění do Správné umístění našeho pole, a pak chceme změnit velikost fronty, kolik prvků jsme V současné době máme. 

Tak pojďme začít. Zde je, opět, že obecná deklarace funkce forma za to, co Enqueue by mohl vypadat. A je to tady. Pojďme Zařadí číslo 28 do fronty. Tak co budeme dělat? No, před naší frontě při 0 ° C, a velikosti našeho fronty je 0, a tak jsme asi chcete dát číslo 28 v poli číslo prvku 0, jo? Takže jsme teď umístěny tak, aby se tam. Takže teď co musíme změnit? Nechceme měnit přední fronty, protože chceme vědět, jaký prvek bychom mohli potřebovat, aby dequeue později. Takže důvod, proč jsme tam front je jakýmsi ukazatelem toho, co je nejstarší věc na poli. No nejstarší věc na array-- v Skutečnost, jediná věc, v poli vpravo now-- je 28, který je v místě pole 0. Takže nechceme, aby změnit tuto zelenou linku, protože to je nejstarší element. Spíše chceme změnit velikost. Takže v tomto případě, budeme zvýšit velikost na 1. 

Nyní obecný jakousi myšlenkou, kde se další prvek se chystá jít ve frontě je přidat těchto dvou čísel spolu, přední a velikost, a že tě kde vyprávět další prvek ve frontě se chystá jít. Takže teď pojďme Zařadí jiné číslo. Pojďme Zařadí 33. Takže 33 se chystá jít do Poloha pole 0 a 1. Takže v tomto případě, bude to jít do umístění pole 1, a nyní velikost naší fronty je 2. 

Opět platí, že nejsme mění přední část naší fronty, 28, protože je stále nejstarší element, a my Chcete-to-- když se nakonec dostal na dequeuing, odebírání prvků z této fronty, chceme vědět kde je nejstarší element. A tak jsme vždycky je třeba zachovat některé ukazatel, kde to je. Takže to je to, co je tu pro 0. To je to, co přední straně je tam. 

Pojďme v Zařadí ještě jeden prvek, 19. Jsem si jistý, můžete hádat, kde 19 se chystá jít. Bude to jít do pole číslo umístění 2. To je 0 a 2. A nyní je velikost naší fronty je 3. Máme 3 elementy v tom. Takže pokud jsme měli, a nebudeme právě teď, Zařadí další prvek, to by jít do místa pole číslo 3, a velikost naší fronty bude 4. Proto jsme enqueued několik prvků teď. Nyní začněme k jejich odstranění. Pojďme dequeue z fronty. 

Takže podobně jako pop, který je trochu analogu tohoto pro komíny, dequeue třeba akceptovat Ukazatel na queue-- znovu pokud je to v celosvětovém měřítku deklarována. Nyní chceme změnit umístění z fronty. To je místo, kde to tak nějak přijde do hry, že přední variabilní, protože jakmile jsme se odstranit prvek, chceme přesunout do dalšího nejstarší prvek. 

Pak chceme snížit velikost fronty, a pak jsme se chcete vrátit hodnotu , který byl odebrán z fronty. Opět platí, že nechceme, aby prostě odhodit to. Jsme pravděpodobně Extrahujete to z queue-- kterém jsme dequeuing to, protože nám záleží na tom. Takže chceme, aby tato funkce se vrátit datový prvek typu hodnoty. Opět platí, že v tomto případě, že hodnota je celé číslo. 

Takže teď pojďme dequeue něco. Pojďme odstranit prvek z fronty. Říkáme-li, int x rovná & q, ampersand q-- Znovu to je ukazatel na tento q dat structure-- co element se bude dequeued? V tomto případě, protože se jedná o prvním in, first out datové struktury, FIFO, První věc, kterou jsme se dát do toho fronta byla 28, a tedy v tomto případě, budeme brát 28 z fronty, ne 19, který je co bychom udělali, jestli to byla hromada. Chystáme se přijmout 28 z fronty. 

Podobně k tomu, co jsme to udělali s stoh, nejsme ve skutečnosti chystá vymazat 28 z fronty samotné, my jen tak druhu z předstírat, že tam není. Takže to bude tam zůstat v paměti, ale my jsme prostě bude druh ignorovat pohybem další dvě pole naší q dat struktura. Chystáme se změnit frontu. Q.front se nyní chystá být 1, protože to je nyní nejstarší prvek máme v naší fronta, protože jsme už odstraněno 28, což byl bývalý nejstarší element. 

A teď, chceme změnit velikost fronty na dva prvky místo tří. Teď pamatovat dříve jsem řekl, když jsme Chcete přidat prvky do fronty, dáme to v místě pole který je součtem přední a velikosti. Takže v tomto případě, jsme stále uvedení to, další element ve frontě, do umístění pole 3, a budeme vidět, že v druhém. 

Proto jsme nyní naše dequeued První element z fronty. Udělejme to znovu. Pojďme odstranit další element z fronty. V případě, aktuální nejstarší prvkem je umístění pole 1. To je to, co nám říká q.front. To zelené pole nám říká, že že je to nejstarší element. A tak, x se stane 33. Budeme tak nějak zapomněl 33, že existuje v poli, a budeme říkat, že teď, Nový nejstarší element ve frontě je v místě pole 2 a velikost fronty, počet prvků máme ve frontě, je 1. Nyní pojďme Zařadí něco, a já nějak dal to pryč před vteřinou, ale pokud chceme dát 40 do fronta, kde je 40 jít? Dobře jsme se ho uvedení v q.front a fronty velikosti, a tak to dává smysl, aby skutečně dát 40 sem. Nyní si všimněte, že v nějaký bod, jdeme se dostat do konce roku Naše pole uvnitř q, ale že vybledla 28 a 33-- jsou to ve skutečnosti, technicky otevřené prostory, je to tak? A tak můžeme eventually-- že pravidlo přidání ti dva together-- jsme může nakonec je třeba mod podle velikosti kapacity takže můžeme zabalit kolem. 

Takže pokud se dostaneme do prvku číslo 10, když jsme nahradí ji v elementu číslo 10, měli bychom skutečně dát do lokalitě pole 0. A když jsme se chystali array mě location-- omluvte, pokud jsme přidali je spolu, a dostali jsme se na číslo 11 z nich by být tam, kde bychom dát to, která neexistuje v tomto array-- to by měl jít mimo hrací plochu. Mohli bychom mod o 10 a dal že v místě pole 1. Tak to je, jak fungují fronty. Vždycky jít zleva doprava a případně zábal kolem. A víte, že jsou plné výši, pokud velikost, že červené pole, stává stejnou kapacitu. A tak poté, co jsme přidali 40 do fronta, no co musíme udělat? No, nejstarší element ve frontě je stále 19, takže nechceme měnit přední fronty, ale teď máme dvě prvky ve frontě, a tak chceme zvýšit naší velikosti od 1 do 2. 

To je docela hodně to s pracovat s front založená na poli, a podobně jako komín, tam je také způsob, realizovat fronty jako Google seznamu. Nyní, pokud tento typ struktura dat vypadá povědomě vám, to je. Není to jednotlivě spojový seznam, je to dvojnásob provázaný seznam. A teď, jak stranou, to je ve skutečnosti je to možné realizovat fronta jako jednotlivě spojový seznam, ale Myslím si, že pokud jde o vizualizaci, to vlastně mohlo pomoci k zobrazení to jako dvojnásobně Google seznamu. Ale je to určitě možné dělat to jako singly provázaný seznam. 

Takže pojďme se podívat na co by to mohlo vypadat. Pokud chceme, aby enquue-- takže teď, opět jsme přepnutí na Google-list na základě modelu zde. Pokud chceme, aby Zařadí, chceme přidat nový prvek, dobře Co musíme udělat? No, v první řadě, protože budeme přidávat na konec a odstranění z Zpočátku jsme pravděpodobně chtějí zachovat odkazy na oba hlava a ocas Google seznamu? Ocas je další termín pro konec seznamu Google, poslední prvek v připojeném seznamu. A to bude asi, opět, být prospěšné pro nás pokud jsou globální proměnné. Ale teď, když chceme přidat nový prvek co musíme udělat? To, co jsme právě [? Malak?], nebo dynamicky přidělit náš nový uzel pro sebe. A pak, jako když jsme se přidat některý prvek do dvojnásobně Google seznamu my, prostě musí třídit of-- ty poslední tři kroky zde jsou všechno jen o přesunutí ukazatele v správným způsobem tak, že prvek dostane přidán do řetěz bez přerušení řetězce nebo dělat nějaký chyby nebo má nějaký nehody stát, v němž bychom náhodou orphan některé prvky naší fronty. Tady je to, co by to mohlo vypadat. Chceme přidat prvek 10 na konci této fronty. Takže nejstarší prvek zde je reprezentován hlavy. To je první věc, kterou klademe do tohoto hypotetického fronty zde. A ocas, 13, je nejvíce nedávno přidal prvek. A tak, pokud chceme, aby do 10 Zařadí Tato fronta, chceme, aby to po 13. A tak budeme dynamicky přidělit prostor pro nový uzel a zkontrolujte, zda null, aby se ujistil nemáme selhání paměti. Pak jsme se chystáte místo 10 do tohoto uzlu, a nyní musíme být opatrní o tom, jak organizovat ukazatele takže neporušují řetěz. 

Můžeme nastavit 10 je předchozí pole poukázat zpět do starého ocasu a protože '10 bude nový ocas v určitém okamžiku v době, kdy všechny tyto řetězy jsou připojeny, nic se přijde po 10 právě teď. A tak další ukazatel 10 je bude ukazovat na null, a pak poté, co jsme to udělat, poté, co jsme připojený 10 dozadu k řetězu, můžeme vzít staré hlavu, nebo, omluvu já, starý ocas fronty. Starý konec fronty, 13, a učinit z něj poukazují na 10. A nyní, v tomto bodě, máme enqueued číslo 10 do této fronty. Vše, co musíme udělat, je nyní jen přesunout tail, aby ukazoval na 10 místo toho, aby 13. 

Dequeuing je vlastně velmi podobné praskání ze zásobníku, který je realizován jako spojový seznam pokud jste viděli stohy videa. Vše, co musíme udělat, je začít u začátek, najít druhý prvek, uvolnit první prvek, a přesuňte hlavu přejděte k druhému prvku. Pravděpodobně lepší jej vizualizovat prostě být extra jasné, o tom. Tak tady je zase naše fronta. 12 je nejstarší element v naší frontě, hlavy. 10 je nejnovější prvek v naší frontě, ocasem. 

A tak, když chceme, na dequeue prvek, chceme odstranit nejstarší prvek. Tak co budeme dělat? Tak jsme si stanovili ukazatele traversal který začíná v čele, a my jsme jej přesunout tak, aby se poukazuje na druhý prvek z toho queue-- něco tím, že říká trav se rovná trav šipku, například, by se pohyboval trav zde poukázat na 15, který poté, co jsme dequeue 12, nebo poté, co jsme odebrání 12, bude se stal tehdejší nejstarší element. 

Nyní máme držet na první prvek přes ukazatel hlavy a druhý prvek pomocí ukazatele trav. Nyní můžeme bez hlavy, a pak můžeme tedy před 15. nic přijde ještě. Takže můžeme změnit 15 je předchozí ukazatel poukázat na null, a my jen přesunout hlavu nad. A tam jdeme. Nyní máme úspěšně se dequeued 12, a teď jsme mají další fronty 4 prvků. To je skoro všechny tam je front, jak pole-based a spojený-list bázi. Jsem Doug Lloyd. To je CS 50.