Doug LLOYD: Mela jekk inti stajt jaraw l-video fuq munzell, dan huwa probabbilment se jħossu bħal xi ftit ta 'deja vu. Huwa ser kunċett simili ħafna, biss bi twist żgħir fuqha. Aħna qed tmur biex jitkellmu issa dwar kjuwijiet. Allura kju, simili għal munzell, huwa tip ieħor ta 'struttura data li nistgħu nużaw biex iżommu data b'mod organizzat. Simili għal munzell, dan jista 'jiġi implimentat bħala firxa jew lista marbuta. B'differenza munzell, ir-regoli li nużaw biex jiddeterminaw meta l-affarijiet nikseb miżjud u mneħħija mill kju huma xi ftit differenti. B'differenza munzell, li hija struttura LIFO, aħħar li l-ewwel out, kju huwa FIFO istruttura, FIFO, l-ewwel fl-ewwel li joħroġ. Issa kjuwijiet, inti probabilment għandhom analoġija biex kjuwijiet. Jekk inti stajt qatt kienu fil-linja fil park ta 'divertiment jew fil-bank, hemm tip ta 'ekwità implimentazzjoni istruttura. L-ewwel persuna fil-linja fil l-bank huwa l-ewwel persuna li jottjeni biex tkellem lill-kaxxiera. 

Ikun tip ta 'razza sal-qiegħ jekk l-uniku mod idea li jkellem lill-kaxxiera fil- bank kellha tkun l-aħħar persuna fil-linja. Kulħadd dejjem tixtieq tkun l-aħħar persuna fil-linja, u l-persuna li kien hemm l-ewwel li baqgħet tistenna għal xi ftit, jista 'jkun hemm għal siegħa, u siegħat, u sigħat qabel ma jkollhom ċans li attwalment jirtira xi flus fil-bank. U hekk kjuwijiet huma tip ta 'l- ġustizzja implimentazzjoni istruttura. Iżda dan ma jfissirx neċessarjament li stacks huma xi ħaġa ħażina, biss li kjuwijiet huma mod ieħor biex tagħmel dan. Għalhekk għal darb'oħra kju huwa l-ewwel fl-ewwel out, versus munzell li jdum fil- ewwel out. Simili għal munzell, għandna żewġ operazzjonijiet li nistgħu twettaq fuq kjuwijiet. L-ismijiet huma enqueue, li huwa li żżid element ġdid sa l-aħħar tal-kju, u dequeue, li hija biex jitneħħew l-eqdem element minn quddiem tal-kju. Allura aħna qed tmur biex jiżdiedu elementi fuq il-aħħar tal-kju, u aħna qed tmur biex jitneħħew l-elementi minn quddiem tal-kju. Għal darb'oħra, bl-munzell, konna żżid Elementi għall-quċċata tal-munzell u t-tneħħija elementi mill-quċċata tal-munzell. Allura ma enqueue, huwa jżid mal l-aħħar, it-tneħħija minn quddiem. Allura l-eqdem ħaġa fil hemm huwa dejjem l-ħaġa li jmiss li toħroġ jekk nippruvaw u dequeue xi ħaġa. 

Għalhekk għal darb'oħra, ma kjuwijiet, nistgħu implimentazzjonijiet bbażati fuq array u marbuta mal-lista implimentazzjonijiet bbażata. Aħna ser tibda mill-ġdid ma implimentazzjonijiet bbażati fuq array. Id-definizzjoni istruttura jistenna pretty simili. Għandna firxa ieħor hemm valur tip ta 'dejta, għalhekk tista 'żżomm tipi ta' data arbitrarji. Aħna darb'oħra ser tuża interi F'dan l-eżempju. 

U bħad bil tagħna implimentazzjoni munzell bbażati fuq firxa, għaliex aħna qed tuża firxa, aħna neċessarjament jkollhom din il-limitazzjoni dan it-tip C tal tinforza fuqna, li hija aħna m'għandhom l-ebda dinamiżmu fil tagħna abbiltà li jikbru u tiċkien il-firxa. Irridu jiddeċiedu fil-bidu X'inhu n-numru massimu ta 'affarijiet li nistgħu npoġġu fis dan kju, u f'dan il-każ, kapaċità tkun xi lira definit kostanti fil-kodiċi tagħna. U għall-finijiet ta 'dan video, il-kapaċità se tkun 10. 

Għandna bżonn li jżommu rekord ta ' quddiem tal-kju hekk nafu liema element irridu dequeue, u wkoll għandna bżonn li jżommu rekord ta ' xi ħaġa else---numru ta 'elementi li għandna fil-kju tagħna. Avviż aħna mhux qed iżżomm rekord tal-aħħar tal-kju, just id-daqs tal-kju. U r-raġuni għal dik se nisperaw issir daqsxejn aktar ċara fil-mument. Ladarba aħna temmew din id-definizzjoni tat-tip, għandna tip ta 'dejta ġdida imsejħa kju, li nistgħu issa tiddikjara varjabbli ta 'dak it-tip tad-data. U kemmxejn joħloq konfużjoni, stajt iddeċieda biex sejħa dan kju q, l-ittra q minflok il-q tip ta 'data. 

Allura hawnhekk huwa kju tagħna. Hija struttura. Fiha tliet membri jew tlieta oqsma, firxa ta 'KAPAĊITÀ daqs. F'dan il-każ, il-kapaċità hija 10. U dan array huwa se jżommu interi. Fil ħadra hija l-quddiem tal-kju tagħna, il- element jmiss li jitneħħew, u bl-aħmar se jkun id-daqs tal-kju, kemm elementi bħalissa huma eżistenti fil-kju. Allura jekk aħna ngħidu ugwali q.front 0, u d-daqs q.size ugwali 0-- aħna qed tqegħid 0s f'dawk l-oqsma. U f'dan il-punt, aħna qed pretty ħafna lest li tibda taħdem ma kju tagħna. 

Allura l-ewwel operazzjoni nistgħu tagħmel huwa li enqueue xi ħaġa, li żżid element ġdid li l-aħħar tal-kju. Well dak li għandna bżonn biex tagħmel fil-każ ġenerali? Ukoll din il-funzjoni enqueue bżonnijiet li jaċċetta pointer li kju tagħna. Għal darb'oħra, jekk aħna kien iddikjara kju tagħna globalment, aħna ma bżonn tagħmel dan neċessarjament, iżda b'mod ġenerali, aħna bżonn li jaċċettaw pointers li strutturi ta 'dejta bħal dan, għax inkella, aħna qed tgħaddi minn value-- aħna qed tgħaddi kopji tal-kju, u hekk aħna mhux qed attwalment qed jinbidlu -kju li għandna l-intenzjoni li jibdlu. 

Il-ħaġa oħra li teħtieġ li tagħmel huwa jaċċetta element tad-data tat-tip xieraq. Għal darb'oħra, f'dan il-każ, huwa se tkun interi, imma int tista arbitrarjament tiddikjara t-tip tad-data kif valur u jużaw dan b'mod aktar ġenerali. Dik hija l-element li rridu enqueue, irridu li żżid mal-aħħar tal-kju. Imbagħad aħna attwalment jridu post li d-data fil-kju. F'dan il-każ, it-tqegħid tagħha fis- post korretta tal array tagħna, u mbagħad irridu li jibdlu l-daqs tal-kju, kemm elementi aħna bħalissa għandhom. 

Mela ejja tibda. Hawnhekk huwa, għal darb'oħra, li āenerali Dikjarazzjoni funzjoni formola għal dak enqueue jista 'dehra. U here we go. Ejja enqueue-numru 28 fil-kju. Allura dak li aħna se jagħmlu? Ukoll, il-faċċata tal kju tagħna huwa f'0, u d-daqs ta 'kju tagħna huwa ta '0, u hekk aħna probabilment tixtieq li tqiegħed in-numru 28 fil-firxa numru element 0, id-dritt? Allura konna issa imqiegħda li fil hemmhekk. Allura issa dak li għandna bżonn għall-bidla? Aħna ma jridux bidla quddiem tal-kju, għaliex irridu li taf liema element nistgħu bżonn li dequeue aktar tard. Allura r-raġuni għandna quddiem hemm huwa tip ta 'indikatur ta' x'hemm l-eqdem ħaġa fil-firxa. Ukoll l-eqdem ħaġa fil-array-- fil fatt, l-unika ħaġa fil-firxa dritt now-- huwa 28, li huwa fil-post array 0. Allura aħna ma rridux li bidla dak in-numru aħdar, minħabba li l-element eqdem. Pjuttost, irridu li jibdlu l-daqs. Allura f'dan il-każ, aħna ser inkrement daqs għal 1. 

Issa tip ġenerali ta 'idea ta' fejn l- element jmiss se jmorru fil-kju huwa li żżid dawn iż-żewġ numri flimkien, quddiem u d-daqs, u li ser jgħidlek meta l-li jmiss element fil-kju se jmorru. Allura issa ejja enqueue numru ieħor. Ejja enqueue 33. Allura 33 huwa se jmorru fil post array 0 plus 1. Allura f'dan il-każ, li għaddej li jmorru fis lokazzjoni firxa 1, u issa d-daqs ta 'kju tagħna huwa ta' 2. 

Għal darb'oħra, aħna mhux qed jinbidlu quddiem tal-kju tagħna, minħabba 28 għadu l- eqdem element, u aħna tixtieq to-- meta aħna eventwalment jiksbu li dequeuing, it-tneħħija elementi minn dan kju, li rridu nkunu nafu fejn l-element eqdem hu. U hekk aħna dejjem bżonn li jinżamm xi indikatur ta 'fejn dan huwa. Allura dak hu li l-0 qiegħed hemm għall. Dak hu quddiem huwa hemm għal. 

Ejja fil enqueue wieħed aktar element, 19. Jien ċert li inti tista 'raden fejn 19 se jmorru. Li għaddej biex tmur fil firxa numru lokazzjoni 2. C'est 0 plus 2. U issa id-daqs ta 'kju tagħna huwa ta' 3. Aħna 3 elementi fiha. Hekk jekk konna biex, u aħna mhux qed tmur li dritt issa, enqueue element ieħor, dan imur fis lokazzjoni firxa numru 3, u d-daqs ta 'kju tagħna tkun 4. Allura konna enqueued diversi elementi issa. Issa ejja nibdew biex jitneħħew. Ejja dequeue minnhom mill-kju. 

Allura simili li pop, li huwa tip tal-Analog ta 'dan għal stacks, dequeue jeħtieġ li taċċetta pointer għall-queue-- mill-ġdid, sakemm huwa globalment iddikjarat. Issa rridu li jibdlu l-post ta 'quddiem tal-kju. Dan huwa fejn tip ta 'niġu fis-rwol, dak il-varjabbli ta 'quddiem, għaliex ladarba aħna tneħħi element, irridu li jġorrhom għall-element li jmiss eqdem. 

Imbagħad irridu li jnaqqsu id-daqs tal-kju, u allura aħna jridu jirritornaw il-valur li tneħħa mill-kju. Għal darb'oħra, aħna ma jridux biss armiha. Aħna preżumibbilment huma estrazzjoni mis-queue-- aħna qed dequeuing għaliex aħna kura dwar dan. Allura rridu din il-funzjoni li jirritornaw element tad-data ta 'valur tip. Għal darb'oħra, f'dan il-każ, il-valur huwa numru sħiħ. 

Allura issa ejja dequeue xi ħaġa. Ejja neħħi element mill-kju. Jekk aħna ngħidu int x ugwali u q, ampersand q-- għal darb'oħra li l-pointer li din id-data q structure-- dak element se tkun dequeued? F'dan il-każ, għaliex hija l-ewwel fl-ewwel out istruttura ta 'data, FIFO, l-ewwel ħaġa li għandna jitqiegħdu fis dan kju kien 28, u għalhekk f'dan il-każ, aħna qed tmur biex tieħu 28 minn -kju, mhux 19, li huwa dak aħna kien jagħmel kieku dan kien munzell. Aħna qed tmur biex tieħu 28 mill-kju. 

Simili għal dak li għamilna ma ' munzell, aħna mhux qed attwalment ser tħassar 28 mill-kju innifsu, aħna qed biss ser tip ta nippretendu ma jkunx hemm. Allura li għaddej biex tibqa 'hemm fil-memorja, imma aħna qed biss ser tip ta 'jinjoraha billi mexxew iż-żewġ oqsma oħra ta 'data q tagħna istruttura. Aħna ser jibdlu l-front. Q.front issa se jkun 1, minħabba li issa huwa l-element eqdem għandna fil tagħna kju, għaliex aħna stajt diġà tneħħiet 28, li kienet l-element ta 'qabel eqdem. 

U issa, aħna tixtieq li tibdel id-daqs tal-kju għal żewġ elementi minflok tlieta. Issa ftakar qabel I said meta aħna trid iżżid elementi għall-kju, aħna poġġih f'post firxa li hija s-somma ta 'quddiem u d-daqs. Allura f'dan il-każ, aħna qed għadhom tqegħid dan, l-element li jmiss fil-kju, fis lokazzjoni firxa 3, u Ser naraw li fit-tieni. 

Allura aħna issa stajt dequeued tagħna ewwel element mill-kju. Ejja nagħmlu dan mill-ġdid. Ejja neħħi ieħor element mill-kju. Fil-każ, l-kurrent eqdem element huwa post array 1. Dak hu li q.front tgħidilna. Li l-kaxxa ħadra tgħidilna li dak l-element eqdem. U għalhekk, x se jsiru 33. Aħna ser biss tip ta 'ninsew li 33 teżisti fil-firxa, u aħna ser ngħidu li issa, l- element ġdid eqdem fil-kju huwa fil-post array 2, u d-daqs tal-kju, in-numru ta 'elementi għandna fil-kju, huwa 1. Issa ejja enqueue xi ħaġa, u I tip ta 'taw din bogħod tieni ilu, imma jekk irridu li tqiegħed 40 fil- kju, fejn s-40 se jmorru? Well we kont qed tqegħid fil q.front plus kju daqs, u għalhekk jagħmel sens li fil-fatt li jpoġġu 40 hawn. Issa avviż li fil F'xi punt, aħna qed tmur biex jiksbu l-aħħar ta ' firxa tagħna ġewwa tal q, iżda li faded out 28 u 33-- dawn qed attwalment, teknikament spazji miftuħa, id-dritt? U hekk, aħna jistgħu eventually-- din ir-regola ta 'żżid dawn iż-żewġ together-- nistgħu eventwalment jeħtieġ li mod mid-daqs tal-kapaċità hekk nistgħu wrap madwar. 

Hekk jekk irridu jiksbu l-element numru 10, jekk aħna qed jissostitwixxih fil element numru 10, aħna'd attwalment tqiegħed fil-post array 0. U jekk konna se firxa location-- skuża me, jekk aħna miżjud up flimkien, u aħna ltqajna biex numru 11 Ikun fejn rridu naraw li jpoġġi dan, li ma teżistix f'dan il array-- ikun għaddej minn limiti. Nistgħu Mod b'10 u mqiegħda għalih fil-post array 1. Allura li kif kjuwijiet jaħdmu. Huma qed dejjem se jmorru minn fuq ix-xellug għal-lemin u possibilment around. U inti taf li dawn qed sħiħ jekk id-daqs, li l-kaxxa aħmar, isir ugwali għal kapaċità. U hekk wara konna miżjud 40 sa l- kju, sew dak li rridu nagħmlu? Ukoll, l-element eqdem fil-kju għadu 19, hekk aħna ma jridux bidla quddiem tal-kju, iżda issa għandna żewġ elementi fil-kju, u hekk aħna tixtieq li jiżdied daqs tagħna 1-2. 

Li pretty ħafna ma ' ħidma ma kjuwijiet bbażati fuq array, u simili munzell, hemm ukoll mod biex timplimenta kju bħala lista marbuta. Issa jekk dan it-tip istruttura tad-data jistenna familjari għalik, huwa. Mhuwiex lista marbuta waħdu, huwa lista marbuta doppjament. U issa, bħala twarrib, huwa fil-fatt possibbli li jiġu implimentati kju bħala lista marbuta waħdu, iżda I jaħsbu f'termini ta viżwalizzazzjoni, fil-fatt tista 'tgħin biex tara dan bħala lista marbuta doppjament. Iżda huwa definittivament possibbli li tagħmel dan bħala lista marbuta weħidhom. 

Mela ejja jkollhom ħarsa lejn dak li dan jista 'dehra. Jekk irridu li enquue-- hekk issa, għal darb'oħra aħna qed jaqilbu għal-lista marbuta mudell ibbażat hawn. Jekk irridu li enqueue, irridu li żżid element ġdid, sew dak li rridu nagħmlu? Ukoll, qabel kollox, għaliex aħna qed jżid mal-aħħar u t-tneħħija mill- bidu, aħna probabbilment tixtieq li tinżamm pointers kemm lill- ras u d-denb tal-lista marbuta? Denb jkunu għal perijodu ieħor għal l-aħħar tal-lista marbuta, l-aħħar element fil-lista marbuta. U dawn se probabbilment, għal darb'oħra, tkun ta 'benefiċċju għalina jekk huma varjabbli globali. Imma issa jekk irridu li żżid ġdida element dak li għandna nagħmlu? Dak li aħna biss [? Malak?] jew dinamikament jallokaw node ġdid tagħna għalina. U mbagħad, biss bħal meta aħna żid xi element għal lista marbuta doppjament aħna, sempliċiment għandek issolvi of-- dawk aħħar tliet passi hawn huma biss kollha dwar jiċċaqilqu l- pointers fil-mod korrett sabiex l-element gets miżjuda mal il-katina mingħajr ma jitkissru l-katina jew jagħmlu xi tip ta 'żball jew li xi tip ta 'inċident jiġri li biha aħna aċċidentalment orfni xi elementi ta 'kju tagħna. Hawn dak li dan jista 'dehra. Aħna rridu li jżidu l-element 10 sa l-aħħar ta 'din kju. Allura l-element eqdem hawn hija rappreżentata minn ras. Dik hija l-ewwel ħaġa li nitfgħu fis dan kju ipotetiku hawnhekk. U denb, 13, huwa l-aktar element miżjuda riċentament. U hekk jekk irridu li enqueue 10 fis dan kju, irridu li tqiegħed lilha wara 13. U hekk aħna qed tmur biex dinamikament jalloka territorju għal node ġdid u ċċekkja għall null biex tiżgura aħna ma jkollhomx nuqqas memorja. Allura aħna qed tmur biex introduċi 10 f'dak node, u issa għandna bżonn li tkun attenta dwar kif norganizzaw pointers hekk aħna ma jqassmux il-katina. 

Nistgħu stabbilit 10 ta qasam preċedenti għall-punt lura għall-denb qodma, u peress '10 se tkun l- denb ġdid f'xi punt mill-ħin dawn kollha ktajjen huma konnessi, xejn għaddej biex jiġu wara 10 dritt issa. U hekk 10 ta pointer li jmiss se jindika null, u mbagħad wara nagħmlu dan, wara konna konnessi 10 lura għall-katina, nistgħu nieħdu l-kap qodma, jew, skuża me,-denb antika tal-kju. It-tmiem antika tal-kju, 13, u jagħmluha punt sa 10. U issa, f'dan il-punt, għandna enqueued-numru 10 fis dan kju. Kollha għandna bżonn tagħmel issa huwa biss jċaqalqu l- denb għall-punt 10 minflok sa 13. 

Dequeuing huwa attwalment simili ħafna għall popping minn munzell li hija implimentati bħala lista marbuta jekk inti stajt tidher l-video stacks. Kollha għandna bżonn tagħmel hu li tibda fil- bidu, isibu t-tieni element, ħielsa l-ewwel element, u mbagħad jimxu l-kap għall-punt li t-tieni element. Probabbilment aħjar li Ħares lilha biss sabiex ikunu extra ċara dwar dan. Allura hawnhekk kju tagħna għal darb'oħra. 12 huwa l-element eqdem fil-kju tagħna, il-kap. 10 huwa l-element l-aktar ġodda fil-kju tagħna, denb tagħna. 

U hekk meta rridu li dequeue element, irridu li tneħħi l-element eqdem. Allura dak li nagħmlu? Well waqqafna pointer traversal li jibda fil-ras, u nimxu hekk li Jinnota t-tieni element ta 'dan queue-- xi ħaġa billi qal trav ugwali trav vleġġa li jmiss, per eżempju, se jimxu trav hemm għall-punt li 15, li, wara we dequeue 12, jew wara we tneħħi 12, se jsiru l-element mbagħad-eqdem. 

Issa konna ltqajna istiva fuq l-ewwel element permezz tal-kap pointer u t-tieni element permezz tal-trav pointer. Nistgħu ras issa ħielsa, u mbagħad nistgħu jgħidu ma joħroġ xejn qabel il-15 aktar. Allura nistgħu nbiddlu 15 ta 'qabel pointer għall-punt li nulla, u aħna biss jiċċaqalqu l fuq ras. U hemm immorru. Issa aħna rnexxielna dequeued 12, u issa aħna jkollhom kju ieħor ta '4 elementi. Li pretty ħafna kollha hemm li jkunu kjuwijiet, tnejn li huma bbażati bbażati fuq firxa u marbuta mal-lista. Jien Doug Lloyd. Dan huwa CS 50.