DOUG LLOYD: Kaya kung na sa iyo pinapanood ang mga video sa stack, ito ay marahil pagpunta sa pakiramdam tulad ng isang maliit na piraso ng deja vu. Ito ay pagpunta sa isang halos katulad na konsepto, sa pamamagitan lamang ng isang bahagyang iba ng kahulugan sa mga ito. Kami ay pagpunta sa makipag-usap ngayon tungkol sa queue. Kaya isang pila, katulad ng isang stack, ay isa pang uri ng mga istraktura ng data na maaari naming gamitin upang mapanatili ang data sa isang organisadong paraan. Katulad sa isang stack, ito ay ipinatupad bilang isang array o isang listahan ng mga link. Hindi tulad ng isang stack, ang mga patakaran na ginagamit namin upang matukoy kapag ang mga bagay makakuha ng idinagdag at inalis mula sa isang pila ay Medyo naiiba. Hindi tulad ng isang stack, na ay isang istraktura LIFO, huling in, unang-out, isang pila ay isang FIFO istraktura, FIFO, sa unang, unang out. Ngayon queues, ikaw ay malamang na Mayroon isang pagkakatulad sa queue. Kung sakaling kayo ay sa linya sa isang amusement park o sa isang bangko, may uri ng isang pagkamakatarungan pagpapatupad ng istraktura. Ang unang tao sa linya sa ang bangko ay ang unang tao sino upang makipag-usap sa teller. 

Gusto Ito ay uri ng isang lahi hanggang sa ibaba kung ang tanging paraan nakuha mo na magsalita sa mga teller sa bank ay upang maging ang huling tao sa linya. Laging gusto ng lahat ng tao na ang huling tao sa linya, at ang mga tao na noon ay doon muna sino ay naghihintay para sa isang habang, maaaring doon para sa oras, at oras, at oras bago sila magkaroon ng pagkakataon na talagang withdraw ng pera sa bangko. At kaya queue ay isang uri ng pagkamakatarungan pagpapatupad istraktura. Ngunit iyon ay hindi nangangahulugan na na stack ay isang masamang bagay, lamang na queue ay isa pang paraan upang gawin ito. Kaya muli isang pila ay sa unang, unang out, kumpara sa isang stack na huling in, out muna. Katulad sa isang stack, kami ay may dalawang mga operasyon maaari naming gawin sa queue. Ang mga pangalan ay enqueue, na kung saan ay ang magdagdag ng isang bagong sangkap sa dulo ng pila, at dequeue, na kung saan ay alisin ang pinakaluma elemento mula sa harap ng pila. Kaya kami ay pagpunta sa magdagdag ng mga elemento papunta sa dulo ng pila, at kami ay pagpunta sa alisin ang mga elemento mula sa harap ng pila. Muli, sa stack, ay namin ang pagdaragdag mga elemento sa itaas ng stack at pag-aalis ng mga elemento mula sa tuktok ng stack. Kaya sa enqueue, ito ay ang pagdaragdag sa Sa katapusan, pag-alis mula sa harap. Kaya ang pinakaluma bagay sa doon palaging ay ang susunod na bagay sa labas kung susubukan namin at dequeue isang bagay. 

Kaya muli, sa queue, maaari naming pagpapatupad array-based at naka-link-list batay pagpapatupad. Sisimulan naming muli gamit array-based na pagpapatupad. Ang kahulugan ng istraktura mukhang medyo katulad. Mayroon kaming isa pang array doon ng halaga uri ng data, kaya ito ay maaaring humawak ng arbitrary uri ng data. Muli Kami ay pagpunta sa gamitin ang integer sa halimbawang ito. 

At tulad ng sa aming mga array-based stack pagpapatupad, dahil kami ay gumagamit ng isang array, kami ay palaging Mayroon limitasyon na na C uri ng nagpapatupad ka sa amin, na kung saan ay namin walang anumang dynamism sa ating kakayahan sa paglaki at pag-urong ng array. Mayroon kaming upang magpasya sa simula kung ano ang pinakamataas na bilang ng mga bagay-bagay na maaari naming ilagay sa ito pila, at sa kasong ito, kapasidad ay ang ilang pound tinukoy pare-pareho sa aming mga code. At para sa mga layunin ng video, kapasidad ay magiging 10. 

Kailangan namin upang subaybayan ang mga sa harap ng pila upang malaman namin kung aling mga elemento gusto naming dequeue, at kailangan din namin upang subaybayan ang mga isang bagay else-- ang bilang ng mga elemento na mayroon kami sa aming pila. Pansinin na hindi kami nag-iingat subaybayan mga dulo ng pila, makatarungan ang laki ng queue. At ang mga dahilan para sa na ay inaasahan namin na maging mas malinaw ng kaunti sa isang sandali. Kapag nakumpleto namin sa ganitong uri ng kahulugan, kami ay may isang bagong uri ng data tinatawag queue, na kung saan maaari naming ngayon magpahayag ng variable na ng uri ng data. At medyo confusingly, ako ay nagpasya upang tumawag queue q ito, ang mga titik q sa halip na ang uri ng data q. 

Kaya dito ay ang aming queue. Ito ay isang istraktura. Ito ay naglalaman ng tatlong miyembro o tatlong larangan, isang hanay ng mga laki ng kapasidad. Sa kasong ito, kapasidad ay 10. At ito array ay pagpunta sa hold integer. Sa green ay ang harap ng aming pila, ang susunod na elemento na aalisin, at sa pula ay ang laki ng pila, kung gaano karaming mga elemento ay kasalukuyan umiiral sa queue. Kaya kung sinasabi namin q.front equals 0, at laki q.size katumbas 0-- kami ay paglalagay ng 0s sa mga patlang. At sa puntong ito, hindi namin medyo marami handa na upang simulan ang nagtatrabaho sa aming pila. 

Kaya ang unang operasyon ng aming makakaya maisagawa ay upang enqueue ang isang bagay, upang magdagdag ng isang bagong sangkap sa ang dulo ng pila. Well kung ano ang kailangan namin upang gawin sa pangkalahatang kaso? Well ang function na ito enqueue pangangailangan upang tanggapin ang isang pointer sa aming pila. Muli, kung maisaysay na namin aming queue globally, hindi namin kailangan upang gawin ito kinakailangan, ngunit sa pangkalahatan, kami ay kailangang tanggapin payo na istruktura ng data tulad nito, dahil kung hindi man, kami ay pagpasa sa pamamagitan value-- hindi namin pagpasa sa kopya ng pila, at sa gayon kami ay hindi tunay na pagbabago pila na balak namin na baguhin. 

Ang iba pang mga bagay na kinakailangan nito upang gawin ay tanggapin isang elemento ng data sa mga naaangkop na uri. Muli, sa kasong ito, ito ay magiging integer, ngunit maaari mong nagkataon Ipinahahayag ng mga uri ng data bilang halaga at gamitin ito sa mas pangkalahatang. Iyan ay ang elemento na gusto naming enqueue, gusto naming idagdag sa dulo ng pila. Pagkatapos talaga namin nais na ilagay ang data na iyon sa pila. Sa kasong ito, ilagay ito sa tamang lokasyon ng aming array, at pagkatapos ay gusto naming baguhin ang laki ng pila, kung ilang mga elemento namin may kasalukuyang. 

Kaya sabihin makapagsimula. Narito ang, muli, na pangkalahatang anyo function deklarasyon para sa kung ano ang maaaring enqueue hitsura. At ayan na naman. Enqueue ni ang bilang Ipaalam 28 sa queue. Kaya ano pa ang gagawin natin? Well, sa harap ng aming pila ay sa 0, at ang laki ng aming mga queue ay sa 0, at kaya malamang na namin nais na ilagay ang ang bilang 28 sa number element ng array 0, di ba? Kaya ngayon inilagay namin na lumalabag sa doon. Kaya ngayon kung ano ang kailangan namin upang baguhin? Hindi namin nais na baguhin sa harap ng pila, dahil gusto naming malaman kung ano ang element maaaring kailanganin naming dequeue mamaya. Kaya ang dahilan na namin front doon ay isang uri ng isang tagapagpahiwatig ng kung ano ang ang pinakalumang bagay sa array. Well ang pinakaluma bagay sa array-- in katunayan, ang tanging bagay na sa array karapatan now-- ay 28, na kung saan ay sa array lokasyon 0. Kaya hindi namin nais na baguhin na green number, dahil iyon ang pinakaluma element. Sa halip, gusto naming baguhin ang laki. Kaya sa kasong ito, ipapakita namin dagdagan size sa 1. 

Ngayon ang isang pangkalahatang uri ng ideya ng kung saan ang susunod na elemento ay pagpunta sa pumunta sa isang queue ay upang magdagdag ng mga dalawang numero sama-sama, ang harap at laki, at makikita na ang magsasabi sa iyo kung saan ang susunod element sa pila ay pagpunta sa pumunta. Kaya enqueue ni isa pang numero ngayon hayaan. Ni enqueue 33 Hayaan. Kaya 33 ay pagpunta sa pumunta sa array lokasyon 0 plus 1. Kaya sa kasong ito, ito ay pagpunta upang pumunta sa lokasyon array 1, at ngayon ang laki ng aming pila ay 2. 

Muli, hindi namin binabago sa harap ng aming pila, dahil 28 pa rin ang pinakaluma element, at kami gusto to-- kapag huli naming makuha upang dequeuing, pag-alis mga elemento na ito mula sa queue, gusto naming malaman kung saan ang pinakaluma element ay. At kaya laging kailangan namin upang mapanatili ang ilang tagapagpahiwatig ng kung saan na. Kaya na kung ano ang 0 ay may para sa. Iyon ay kung ano harap ay may para sa. 

Sabihin sa enqueue isa pang elemento, 19. Ako ba na maaari mong hulaan kung saan 19 ay pagpunta sa pumunta. Ito ay pagpunta sa pumunta sa array lokasyon number 2. Iyan ay 0 plus 2. At ngayon, ang laki ng aming mga queue ay 3. Kami ay may 3 mga elemento sa loob nito. Kaya kung kami ay sa, at hindi namin ang pagpunta sa ngayon, enqueue isa pang elemento, ito ay pumunta sa lokasyon array number 3, at ang laki ng aming mga queue ay 4. Kaya enqueued namin ang ilang mga elemento na ngayon. Ngayon sabihin simulan upang alisin ang mga ito ipaalam. Dequeue ni ito mula sa queue Hayaan. 

Kaya katulad ng pop, na kung saan ay uri ng analog ng ito para sa mga stack, pangangailangan dequeue upang tanggapin ang isang pointer muli sa queue--, maliban kung globally ito ay ipinahayag. Ngayon gusto naming upang baguhin ang lokasyon ng harap ng pila. Ito ay kung saan ito uri ng pagdating sa play, na front variable, dahil sa sandaling namin tanggalin isang elemento, gusto naming upang ilipat ito sa susunod na pinakamatandang element. 

Pagkatapos gusto naming bawasan ang laki ng pila, at pagkatapos ay nais naming ibalik ang halaga na ay tinanggal mula sa pila. Muli, hindi namin nais upang itapon lamang ito. Siguro Kami ay extract ito mula sa mga queue-- hindi namin dequeuing ito dahil pinapahalagahan namin ang tungkol dito. Kaya gusto namin ang function na ito upang bumalik isang elemento ng data ng halaga type. Muli, sa kasong ito, ang halaga ay integer. 

Kaya dequeue ni ng isang bagay sa ngayon. Alisin ni isang elemento mula sa pila Hayaan. Kung sinasabi nating int x ay katumbas ng & q, ampersand q-- muli na isang pointer sa q data structure-- ano element ay magiging dequeued? Sa kasong ito, sapagkat ito ay isang unang in, first out istraktura ng data, FIFO, ang unang bagay na namin ilagay sa ito queue ay 28, at kaya sa kasong ito, kami ay pagpunta sa tumagal ng 28 labas ng pila, hindi 19, na kung saan ay kung ano ang Gusto kaming ginawa kung ito ay isang stack. Kami ay pagpunta sa tumagal ng 28 labas ng queue. 

Katulad sa kung ano ang ginawa namin sa isang stack, hindi kami talaga pagpunta sa tanggalin ang 28 mula sa pila mismo, lang namin ang pagpunta sa uri ng magpanggap na ito ay hindi doon. Kaya ito ay pagpunta upang manatili doon sa memorya, ngunit hindi namin lamang pagpunta sa uri ng balewalain ito sa pamamagitan ng paggalaw ang iba pang dalawang mga patlang ng aming q data istraktura. Kami ay pagpunta upang baguhin ang front. Q.front ngayon ay pagpunta sa 1, dahil iyon ay ngayon ang pinakalumang element na namin sa aming pila, dahil mayroon na inalis na namin ang 28, na kung saan ay ang dating pinakaluma element. 

At ngayon, gusto naming baguhin ang laki ng pila sa dalawang mga elemento sa halip na tatlo. Ngayon tandaan sinabi ko mas maaga kapag kami nais na magdagdag ng mga elemento sa pila, inilalagay namin ang mga ito sa isang lokasyon array na kung saan ay ang kabuuan ng harap at laki. Kaya sa kasong ito, hindi pa rin namin ang paglalagay ng ito, ang susunod na elemento sa pila, sa array lokasyon 3, at kami ay makikita na sa isang segundo. 

Kaya ngayon dequeued namin ang aming unang elemento mula sa pila. Gawin natin ito muli. Ni alisin ang isa pang Ipaalam elemento mula sa pila. Sa kaso, ang kasalukuyang pinakamatandang element ay lokasyon array 1. Iyan ay kung ano ang sinasabi q.front amin. Sinasabi sa atin na ang berdeng kahon na iyan ay ang pinakaluma element. At ito, x ay magiging 33. Susubukan naming uri ng lamang kalimutan na 33 umiiral sa array, at kami na sabihin na ngayon, ang mga bagong pinakaluma element sa pila ay array lokasyon 2, at ang laki ng pila, ang bilang ng mga elemento kami ay may sa pila, ay 1. Ngayon enqueue ang isang bagay hayaan, at ako uri ng ibinigay na ito ang layo sa isang segundo ang nakalipas, ngunit kung nais namin na ilagay ang 40 sa queue, kung saan ay 40 pagpunta sa pumunta? Well kami ay paglagay ito sa q.front plus queue laki, at kung kaya't makatuwiran na aktwal na ilagay ang 40 dito. Ngayon pansinin na sa ilang mga punto, kami ay pagpunta upang makakuha ng hanggang sa dulo ng aming array sa loob ng q, ngunit na kupas out 28 at 33-- ang mga ito ay tunay na, technically buksan ang mga puwang, di ba? At ito, maaari naming eventually-- na patakaran ng pagdaragdag mga dalawang together-- maaari naming kalaunan kailangang mod pamamagitan ng sukat ng kapasidad upang maaari naming wrapper sa paligid. 

Kaya kung makuha namin sa element number 10, kung hindi namin palitan ito sa elemento bilang 10, gusto namin tunay na ilagay ito sa array lokasyon 0. At kung kami ay pagpunta sa array location-- patawarin ninyo ako, kung idinagdag namin ang mga ito up magkasama, at nakuha namin sa numero ng 11 ay kung saan kami ay may sa ilagay ito, na kung saan ay hindi na umiiral sa ganitong array-- ay ito ay pagpunta sa labas ng hangganan. Kami ay maaaring mod sa pamamagitan ng 10 at ilagay ito sa lokasyon ng array 1. Kaya na kung paano gumagana queue. Sila ay palaging pagpunta upang pumunta mula sa kaliwa papunta sa kanan at posibleng wrapper sa paligid. At alam mo na ang mga ito ganap na kung ang laki, na red box, nagiging katumbas ng kapasidad. At kaya pagkatapos nagdagdag kami ng 40 sa queue, na rin kung ano ang kailangan namin upang gawin? Well, ang pinakalumang element sa pila ay 19 pa rin, kaya hindi namin nais na baguhin sa harap ng pila, ngunit ngayon ay mayroon kaming dalawang elemento sa pila, at kaya gusto naming dagdagan aming sukat mula sa 1 sa 2. 

Iyan ay medyo magkano ito sa nagtatrabaho sa array-based queues, at katulad ng stack, diyan ay din ng isang paraan upang ipatupad ang isang queue ng isang naka-link na listahan. Ngayon kung ang ganitong uri ng istraktura ng data Mukhang pamilyar sa iyo, ito ay. Ito ay hindi isang isa-isa naka-link na listahan, ito ay isang doble-link na listahan. At ngayon, bilang isang bukod, ito ay tunay na posible upang ipatupad isang pila bilang isang isa-isa naka-link na listahan, ngunit Sa tingin ko sa mga tuntunin ng visualization, ito ang tunay na maaaring makatulong upang tingnan ito bilang isang doble-link na listahan. Ngunit ito ay tiyak na posible na gawin ito bilang isang isa-isa naka-link na listahan. 

Kaya sabihin magkaroon ng isang pagtingin sa kung ano ang maaaring magmukhang. Kung gusto naming enquue-- kaya ngayon, muli kami ay lumipat sa isang naka-link-list based modelo dito. Kung gusto naming enqueue, gusto naming upang magdagdag ng isang bagong sangkap, well kung ano ang kailangan namin upang gawin? Well, una sa lahat, dahil kami ay nagdadagdag ng hanggang sa dulo at pag-aalis mula sa simula, kami ay marahil gusto mong mapanatili ang mga payo sa kapwa ang ulo at ang buntot ng listahan ng mga link? Buntot pagiging isa pang term para sa dulo ng listahan ng mga link, ang huling elemento sa mga naka-link na listahan. At ang mga ito ay marahil, muli, maging kapaki-pakinabang sa amin kung ang mga ito ay mga pangkalahatang variable. Ngunit ngayon kung gusto naming idagdag ang isang bagong element ano ang kailangan nating gawin? Kung ano ang aming lamang [? malak?] o dynamic magtalaga ng aming bagong node para sa ating sarili. At pagkatapos, tulad lamang kapag nagdagdag kami ng anumang sangkap sa isang doble-link list namin, mayroon lamang upang ayusin of-- mga huling tatlong hakbang dito ay lahat lamang tungkol sa paglipat sa mga payo sa tamang paraan upang ang mga elemento naidadagdag ang mga kadena na walang paglabag sa kadena o paggawa ng ilang uri ng mga pagkakamali o pagkakaroon ng ilang uri ng mga aksidente mangyari kung saan namin sinasadyang ulila ang ilang mga elemento ng aming queue. Narito kung ano ang maaaring magmukhang. Gusto naming idagdag ang elemento 10 hanggang sa dulo ng ito queue. Kaya ang pinakaluma elemento dito ay kinakatawan ng ulo. Iyan ay ang unang bagay na inilalagay namin sa hypothetical queue ito dito. At tail, 13, ay ang pinaka kamakailang idinagdag na sangkap. At kaya kung gusto naming enqueue 10 sa ito queue, gusto naming ilagay ito pagkatapos ng 13. At kaya kami ay pagpunta sa dynamically maglaan ng espasyo para sa isang bagong node at suriin para sa null upang tiyakin hindi namin ay may isang pagkabigo memory. Pagkatapos kami ay pagpunta sa ilagay 10 sa na node, at ngayon ay kailangan naming maging maingat tungkol sa kung paano namin ayusin ang mga payo kaya hindi namin basagin ang kadena. 

Maaari naming i-set ng 10 ni nakaraang field upang ituro bumalik sa lumang buntot, at dahil '10 ang magiging bagong buntot sa ilang mga punto sa pamamagitan ng oras sa lahat ng mga ay konektado chains, walang pupuntahan dumating pagkatapos ng 10 ngayon. At kaya 10 ng susunod pointer ay tumuturo sa null, at pagkatapos ay matapos namin gawin ito, pagkatapos namin nai kay 10 paurong sa chain, maaari naming gawin ang mga lumang ulo, o, excuse sa akin, ang lumang buntot ng queue. Ang lumang dulo ng pila, 13, at gawin itong point sa 10. At ngayon, sa puntong ito, kami ay enqueued ang bilang 10 sa mga ito queue. Lahat ng kailangan naming gawin ngayon ay lamang ilipat ang tail upang tumuro sa 10 sa halip ng hanggang 13. 

Dequeuing ay talagang halos kapareho sa pop mula sa isang stack na ipinatupad bilang isang listahan ng mga link kung nakita mo na ang mga stack video. Ang kailangan nating gawin ay magsimula sa simula, hanapin ang pangalawang elemento, libre ang unang elemento, at pagkatapos ay ilipat ang ulo upang ituro sa pangalawang elemento. Marahil mas mahusay na ilarawan sa isip ang mga ito upang maging labis na malinaw tungkol sa mga ito lamang. Kaya narito muli ang aming queue. 12 ay ang pinakaluma element sa aming pila, sa ulo. 10 ay ang pinakabago element sa aming pila, ang aming buntot. 

At kaya kapag gusto namin sa dequeue isang sangkap, gusto naming alisin ang pinakaluma element. Kaya kung ano ang gagawin namin? Well kaming magtakda ng isang traversal pointer na nagsisimula sa ulo, at ilipat namin ito upang ito ay puntos sa ang pangalawang elemento ng mga ito queue-- isang bagay sa pamamagitan ng pagsasabi trav katumbas trav arrow kasunod, halimbawa, nais ilipat trav doon upang tumuro sa 15, na kung saan, pagkatapos naming dequeue 12, o pagkatapos naming alisin 12, ay maging ang pagkatapos-pinakalumang element. 

Ngayon namin nakuha ng isang hold sa mga unang element sa pamamagitan ng pointer ulo at ang pangalawang elemento sa pamamagitan ng pointer trav. Maaari naming libreng ngayon ulo, at pagkatapos ay maaari naming sabihin walang dumating bago 15 anymore. Kaya maaari naming baguhin ang 15 ni nakaraan pointer upang tumuro sa null, at ilipat lang namin sa head over. At doon kami pumunta. Ngayon ay matagumpay na namin dequeued 12, at ngayon kami ay may isa pang pila ng 4 elemento. Iyan ay medyo marami ang lahat ng doon ay upang queues, parehong array-based at naka-link-list based. Ako Doug Lloyd. Ito ang CS 50.