DOUG LLOYD: Hea küll, nii käesoleva punkti olete ilmselt päris tuttav massiivid ja ahelloendid mis on kaks peamist andmestruktuurid me oleme rääkis hoida komplekti andmed sarnaste andmete tüüpi organiseeritud. Nüüd me ei kavatse rääkida umbes paar variatsioonid kohta massiivid ja ahelloendid. Selle video me läheme rääkida korstnad. Nimelt me ​​ei kavatse rääkida umbes andmebaasi struktuuri nimetatakse virna. Meenuta eelmise arutelud umbes viiteid ja mälu et stack on ka nimi for segment mälu kus staatiliselt deklareeritud memory-- mälu, et teil Nime, muutujaid, siis nime, et cetera ja funktsiooni raamid, mida me ka pinu raamid olemas. Nii et see on virnas andmestruktuur ei virna segment mälu. OKEI. 

Aga milline on korstna? Nii et see on päris palju lihtsalt eriline struktuur mis säilitab andmed organiseeritud viisil. Ja seal on kaks väga levinumad viisid ellu korstnad kahe andmestruktuurid et me oleme juba tuttav, massiivid ja ahelloendid. Mis teeb virna eriliseks kuidas me paneme info virna ja kuidas me informatsiooni eemaldamiseks pinu. Eelkõige korstnad reegel on ainult kõige viimati lisatud element saab eemaldada. 

Nii mõelda, nagu oleks see pakk. Me tekkimise info peal ise, ja ainult asi tipus kuhi saab eemaldada. Me ei saa eemaldada asja all sest kõik muu oleks variseda ja kukkuda. Nii et me tõesti ehitame virna, et Siis pead kaotada jaokaupa. Sellepärast me tavaliselt viidata korstnat kui LIFO struktuuri, kesta sisse, esimesena välja. LIFO, kesta sisse, esimesena välja. 

Nii, sest see piirang kuidas teavet saab lisatud ja eemaldada korstna, seal on tõesti ainult kaks asja, mida me saame teha koos virna. Me ei lükka, mis on Mõiste, mida me kasutame, lisades uus element tippu Kestab, või kui virna ei ole olemas ja me luua nullist, luua pinu esimese koha oleks surudes. Ja siis pop, see on omamoodi CS Mõiste me kasutame eemaldada viimati lisada elemendi riidale. 

Nii et me läheme vaatama nii rakendusi, nii massiivi põhineb ja ahelloendid aluseks. Ja me ei kavatse Alustame massiivi aluseks. Nii et siin on põhiline idee, mida massiivi põhineb stack andmestruktuur näeks. Meil on trükitud määratluses. Toas, et meil on kaks liiget või väljade struktuuri. Meil on hulgaliselt. Ja jälle ma kasutan suvaline andmete tüübi väärtus. 

Nii et see võib olla mis tahes tüüpi andmetena int paalia või mõne muu andmeid kirjuta sa varem loodud. Nii et meil on hulgaliselt suurus võimsust. Võimsus on nael määratletud pidev, võibolla kusagil mujal meie faili. Nii märkate juba selle konkreetse rakendamise me piiravates end oli tavaliselt puhul massiivid, mida me ei saa dünaamiliselt suurust, kus seal on teatud arv elementide maksimaalne, et saame panna meie stack. Sel juhul võime elemente. 

Samuti jälgida top pinu. Mis element on kõige Hiljuti lisatud korstna? Ja nii me jälgida, et muutujale nimega top. Ja see kõik saab tõmmati kokku uude andmete tüübi nimega virna. Ja kui me loodud see uus andmetüüp saame ravida nagu muid andmeid tüübist. Me võime kuulutada stack s, nagu me võiks teha int x, või char y. Ja kui me ütleme, korstna s, hästi, mis juhtub on meil saada komplekt mälu kõrvale meile. 

Sel juhul võimsusega Olen ilmselt otsustanud 10 sest mul on Ühe muutuja tüüpi korstnat mis sisaldab kahte väljad meenutada. Array, sel juhul läheb olema massiivi täisarvud nagu see on enamikus minu näited. Ja teine ​​täisarv muutuja suudavad hoida üleval, viimati lisatud element korstnat. Nii ühe virna, mida me lihtsalt määratletud näeb välja selline. See on karbis massiivi 10, mida on täisarvud sel juhul ja teine ​​täisarv muutuja seal roheline näidata riidale. 

Kui soovite, et tippu stack me lihtsalt öelda s.top. See, kuidas me pääse valdkonnas struktuuri tagasivõtmist. s.top võrdub 0 tõhusalt teeb seda meie stack. Nii jälle on meil kaks operatsiooni et suudame täita nüüd. Me ei lükka ja me saame pop. Alustame push. Jällegi, surudes lisab uue element riidale. 

Niisiis, mida me peame tegema Selle massiivi põhinev rakendamine? Noh üldiselt push funktsioon läheb et pead vastu võtma kursor pinu. Nüüd mõtle hetk ja mõelda. Miks me tahame vastu kursor stack? Meenuta eelmise videod Muutuja ulatust ja viiteid, Mis juhtuks, kui me just saatis stack, s pigem parameeter? Mida tegelikult läbinud seal? Pea meeles, me luua koopia kui võtame seda funktsiooni Kui me kasutame suunanäitajaks. Ja nii see funktsioon suruda vajadustele aktsepteerima viit virna nii et me oleme tegelikult muutmata virna me kavatseme muuta. 

Teine asi, push ilmselt tahab nõus on andmete element tüüpi väärtuse. Sel juhul jällegi täisarv, et me ei kavatse lisada tippu pinu. Nii on meil meie kaks parameetrit. Mida me saame nüüd teha sees push? Noh, lihtsalt, me lihtsalt läheb lisada et element riidale ja siis muutuvad kus peal stack on, et s dot top väärtus. Nii et see on see, mida funktsioon deklaratsiooni push tunduda mõnes massiivi põhinev rakendamine. 

Jälle see ei ole raske ja kiire reegel et võid muuta ja on see on väga erinevad. Ehk s kuulutatakse kogu maailmas. Ja nii sa ei pea isegi läbida see parameeter. See on jällegi vaid Üldjuhul push. Ja seal on erinevad kuidas seda rakendada. Aga sel juhul meie push see aega võtab kaks argumenti, kursor virna ja andmeelemendis tüüpi väärtust, täisarv sel juhul. 

Nii me kuulutasime s, me ütles s.top võrdub 0. Nüüd suruge number 28 peale virna. Noh mida see tähendab? Noh praegu Pinu on 0. Ja mis on põhimõtteliselt juhtub on me ei kavatse jääda arv 28 arvesse massiivi 0. Päris lihtne, eks, et oli üleval ja nüüd oled hea minna. Ja siis on meil vaja muuta seda, mis tippu stack on. Nii et järgmine kord, me push element, me ei kavatse seda säilitada massiivi asukohta, ilmselt mitte 0. Me ei taha kirjutada mida me just sinna pannakse. Ja nii me lihtsalt liikuda ülevalt 1. See ilmselt mõtet. 

Nüüd, kui me tahame panna teise elemendi peale virna, ütleme, et me tahame, et lükata 33, Noh nüüd me lihtsalt aega võtab 33 ja pane see on massiivi asukoha number 1 ja siis muutus tippu meie Kestab olla massiivi asukoha number kaks. Nii et kui järgmine kord tahame push element peale virna, see saab panna massiivi asukohta 2. Ja teeme, et veel üks kord. Me suruda 19 välja korstnad. Me paneme 19 massiiv asukohta 2 ja muuta top meie stack olema massiiv asukohast 3 nii et kui järgmine kord, kui me on vaja teha push meil oled hea minna. 

OK, nii et on surudes lühikokkuvõte. Aga popping? Nii popping on omamoodi ametivenna surudes. See, kuidas me kustutada andmeid virna. Ja üldiselt pop vajadustele teha järgmist. See peab aktsepteerima kursor Kestab jälle üldises puhul. Mõnel teisel juhul võite on deklareerinud virna maailmas, mille puhul ei ole vaja edastada see aastal, sest see on juba juurdepääs kui globaalne muutuja. Aga siis mida muud me peame tegema? Noh olime incrementing top virna push, nii me ilmselt läheb taha ainult kahandab riidale pop, eks? Ja siis muidugi me ka läheb taha tagasi väärtust, mida me eemaldada. Kui me lisame elemente, me tahame saada elemendid välja hiljem, me ilmselt tegelikult tahad salvestada neid nii me ei ole lihtsalt nende kustutamiseks Kestab ja tehke midagi koos nendega. Üldiselt, kui me oleme surudes ja popping siin Me tahame hoida seda informatsiooni mõtestatult ja nii see ei tee mõtet lihtsalt loobuda. Nii et see ülesanne peaks ilmselt tagastama väärtuse meile. 

Nii et see on see, mida deklaratsiooni pop tunduda seal üleval vasakul. See funktsioon tagastab andmete tüüpi väärtuse. Jällegi oleme kasutanud täisarvud kogu. Ja ta võtab kursor virna nagu selle ainus argument või füüsilisest parameeter. Mis on pop tegema hakkad? Oletame, et me tahame nüüd pop element off s. Seega pidage meeles, ma ütlesin, et korstnad on viimase aastal, esimene välja, LIFO andmestruktuurid. Milline element läheb saab eemaldada korstna? Kas sa vist 19? Sest sa tahaks olla õige. 19 oli viimane element lisasime Kestab kui olime surudes elemendid, ja nii see läheb esimene element, mis saab eemaldada. See on sama, kui me ütlesime 28, ja siis paneme 33 peal, ja paneme 19 peal, et. Ainus element saame startida on 19. 

Nüüd diagrammil siin, mida ma olen teinud on omamoodi kustutatakse 19 massiivist. See ei ole tegelikult mida me teeme. Me lihtsalt läheb selline on teeselda seda seal ei ole. See on ikka seal et mälu asukoht, aga me lihtsalt läheb seda ignoreerida muutes top meie stack alates on 3-2. Nii kui me nüüd lükata teise elemendi peale virna, see üle kirjutada 19. 

Aga ärme lähe läbi häda kustutada 19 korstnat. Me ei teeskleme seda seal ei ole. Eesmärgil virna see on läinud, kui muudame top olema 2 asemel 3. Olgu, nii et oli päris palju see. See on kõik, mida me peame tegema pop element välja. Teeme seda uuesti. Nii et ma olen rõhutanud seda punast siin näitavad me teeme teise kõne. Me teeme sama asja. 

Mis siis juhtub? Noh, me ei kavatse hoida 33 x ja me läheme muuta riidale 1. Nii et kui me nüüd tõugata element virna, mis me oleme kavatseb teha just nüüd, Mis juhtub on meil läheb ülekirjutamise massiivi asukoha number 1. Nii et 33, mis oli omamoodi vasakule taga, et me lihtsalt teeskles ei ole seal enam, me lihtsalt läheb to Tellida ja panna 40 seal asemel. Ja siis muidugi sest tegime push, me ei kavatse juurdekasvu Pinu 1-2 nii et kui nüüd lisada teise elemendi siis see minema massiivi asukoha number kaks. 

Nüüd seotud nimekirjad on teise kuidas rakendada korstnad. Ja kui see määratlus on ekraan siin tundub tuttav, see on, sest see näeb välja peaaegu täpselt sama, tegelikult see päris palju on täpselt Sama kui üksikult seotud nimekirja, Kui te mäletate meie arutelu üksikult ahelloendid teise video. Ainus piirang siin on meie jaoks nagu programmeerijad, me ei lubata sisestada või kustutada juhuslikult alates üksikult seotud nimekirja mida me võiksime varem teha. Me saame alles nüüd lisada ja kustutada esi- või ülaosa seotud nimekirja. See on tõesti ainus Erinevus küll. See on muidu üksikult seotud nimekirja. See on ainult piirang asendades meist endist nagu programmeerijad, et muudab see virna. 

Reegel on siin alati säilitada kursor juht ahelloend. See on muidugi üldiselt Oluline reegel esimene. Juba üksi seotud nimekirja niikuinii vaja ainult viit juht selleks on, et kett olema võimalik viidata iga teine ​​element on seotud nimekirja. Aga see on eriti oluline virna. Ja nii üldiselt oled läheb tegelikult tahavad osuti olla globaalne muutuja. See on ilmselt läheb olla isegi lihtsam nii. Millised on analoogid push ja pop? Õigus. Nii lükates uuesti suurendab uus element korstnat. In ahelloend et tähendab, et me lähed on luua uus sõlm, et me oleme läheb lisada arvesse seotud nimekirja, ja järgige hoolikalt samme et me oleme kirjeldatud varem in üksikult ahelloendid lisamiseks kett lõhkumata kett ja kaotada või orvustumine tahes elemendid seotud nimekirja. Ja see on põhimõtteliselt mida see väike kämp teksti seal kokkuvõtlikult. Ja olgem vaatleme seda kui diagramm. 

Nii et siin on meie ahelloendid. See samaaegselt sisaldab nelja elemendi. Ja täiuslikumalt siin on meie Kestab sisaldab nelja elementi. Ja oletame, et me nüüd tahame push uus kirje peale virna. Ja me tahame, et lükata uue esemed, mille andmed väärtus on 12. Noh, mida me saame teha? Noh esiteks me ei kavatse malloc ruumi, dünaamiliselt eraldada ruumi uue sõlme. Ja muidugi kohe pärast me helistada malloc me alati veenduge, et kontrollida null, sest kui me saime null tagasi seal oli mingi probleem. Me ei taha apparent et null osuti ehk siis kannatavad seg süü. See ei ole hea. Nii oleme malloced sõlme. Eeldame oleme olnud edukas siin. Me läheme panna 12 sisse andmeväljale et sõlme. Nüüd sa meenutada, mida meie suunanäitajaks liigub järgmise nii et me ei riku kett? Meil on paar võimalust siin aga ainus, mis saab olema ohutu on seatud uudis järgmine viit punkti ja vana juht nimekirja või mida saab varsti vana juht nimekirja. Ja nüüd, et kõik meie elemendid on aheldatud koos, meil võimalik liigutada nimekirja punkti samas kohas, et uus teeb. Ja meil on nüüd tõhusalt surutakse uus element peale ees virn. 

Pop me tahame kustutada Esimene element. Ja nii põhimõtteliselt mida me peame tegema siin, ka meil leida teine ​​element. Lõpuks, mis muutub uus pea pärast me kustutame esimene. Nii et me lihtsalt vaja alustada Alguses liikuda ühe edasi. Kui meil kätte ühel ettepoole, kus me praegu me ei kustuta esimene ohutult ja siis saame lihtsalt liikuda juht käsk, mis oli Teisel ametiajal siis nüüd Esmakordne pärast seda sõlm on kustutatud. 

Nii uuesti, võttes pilk seda kui diagramm me tahad nüüd pop element off virna. Mida me siis teeme? Noh me esimest kavatse luua uus osuti, mis läheb osutada sama kohapeal juhina. Me läheme liigutada ühe positsiooni edasi, öeldes trav võrdsete trav kõrval näiteks mis edendaks trav kursorit ühe asendis edasi. Nüüd, kui meil on hoidke esimene element läbi pointer nimetatakse nimekirja ja Teine element läbi pointer nimetatakse trav, saame julgelt kustutada Esimene element korstnat kaotamata ülejäänud keti sest me on võimalus viidata teise elemendi edastada teel pointer nimega matk. 

Nüüd saame tasuta, mis sõlme. Meil saab tasuta nimekirja. Ja siis kõik me peame tegema, on praegu liikuda nimekirja viitavad samale kohale et matk teeb, ja me oleme justkui tagasi kust me alustasime, enne kui me tõugata 12 kohta esiteks, eks. See on täpselt, kus me olime. Meil oli see neli elementi pinu. Lisasime viiendiku. Me nõudsime viiendiku element, ja siis me hüppasid, et viimati lisada element tagasi maha. 

See on tõesti päris palju kõik on korstnad. Võite rakendada neid massiive. Võite rakendada neid ahelloendid. On muidugi muud kuidas rakendada neid samuti. Põhimõtteliselt põhjus, miks me ei kasuta virnade on säilitada andmetega sellisel viisil et viimati lisatud element on esimene asi, mida me oleme tahame seda tagasi saada. Ma olen Doug Lloyd, see on CS50.