DOUG Lloyd: Hyvä, joten tässä kohdassa olet luultavasti tuttuja jossa paneelit ja liittyvät luettelot joka on kaksi pääasiallista tietorakenteita olemme puhui pitää sarjaa tiedot samankaltaisten tietotyyppejä järjestetty. Nyt aiomme puhua noin pari muunnelmia koskevat taulukot ja linkitettyjen listojen. Tässä videossa olemme menossa puhua pinot. Erityisesti aiomme puhua noin datarakenne kutsutaan pino. Recall aiempiin keskusteluihin noin viitteitä ja muisti, että pino on myös nimenne segmentin muistia jossa staattisesti ilmoitettu memory-- muisti, että olet nimi, muuttujat annat nimeksi, et niin edelleen ja toiminta kehyksiä, jotka olemme myös kutsupino kehyksiä olemassa. Joten tämä on pino tietorakenne ei pino segmentti muistia. OK. 

Mutta mikä on pino? Joten se on aika paljon vain erikoinen rakenne joka ylläpitää tietoja järjestäytyneesti. Ja siellä on kaksi hyvin yhteinen tapoja toteuttaa pinot kahdella tietorakenteita että olemme jo tuttuja, taulukot ja linkitettyjen listojen. Mikä tekee pino erityinen on miten laitamme tiedot pinoon, ja tapaamme poistaa tietoja pinosta. Erityisesti pinot sääntö on vain kaikkein viimeksi lisätyt elementti voidaan poistaa. 

Joten ajattele sitä niin kuin se on pino. Olemme paalutus tiedot itsensä päälle, ja vain asia yläreunassa paalun voidaan poistaa. Emme voi poistaa asia alla koska kaikki muu olisi romahtaa ja kaatua. Joten me todella olemme rakentamassa pinon Sitten täytyy poistaa pala palalta. Tämän vuoksi me yleensä viitataan pinoon niin LIFO rakenne, last in, first out. LIFO, last in, first out. 

Joten koska tämä rajoitus miten tieto voidaan lisätä ja poistetaan pinosta, siellä oikeastaan vain kaksi asiaa voimme tehdä pino. Voimme työntää, joka on termi käytämme lisäämiseen uusi elementti alkuun pino, tai jos pino ei ole olemassa ja Luomme sitä tyhjästä, luodaan pino ensinnäkin olisi ajaa. Ja sitten pop, että on sellainen CS termi käytämme poistaa viimeksi lisätään elementti ylhäältä pinon. 

Joten olemme menossa katsomaan molemmat toteutukset, molemmat array perustuu ja linkitetty lista perustuu. Ja aiomme aloittaa array perustuu. Joten tässä on perusajatus, mitä array perustuu pino tietorakennetta näyttäisi. Meillä kirjoitetut määritelmä täällä. Sisältä että meillä on kaksi jäsentä tai kenttiä rakenteen. Meillä jono. Ja taas olen käyttäen mielivaltaista tietotyyppi arvo. 

Joten tämä voisi olla mikä tahansa tietotyyppi, int char tai eräitä muita tietoja Kirjoita olet aiemmin luonut. Joten meillä on taulukon koko kapasiteetin. Kapasiteetti punta määritelty vakio, ehkä jossain muualla meidän tiedostoon. Niin huomaa jo tämän tietyn täytäntöönpano olemme rajaava itsemme oli tyypillisesti tapauksessa paneelit, joita emme voi dynaamisesti muuttaa, missä on joitakin elementtien maksimi että voimme laittaa meidän pinon. Tässä tapauksessa se on kapasiteettia elementtejä. 

Olemme myös seurata pinon. Mikä elementti on kaikkein äskettäin lisätä pinoon? Ja niin me seurata, että muuttujaan nimeltä alkuun. Ja kaikki tämä saa käärittynä yhteen uuteen tietotyyppi nimeltään pino. Ja kun me luoneet tämä uusi tietotyyppi voimme käsitellä sitä kuin muita tietoja tyyppi. Voimme julistaa pino s, kuten voisimme tehdä int x, tai char y. Ja kun me sanomme pino s, hyvin, mitä tapahtuu on saamme joukko muisti varattu meille. 

Tässä tapauksessa kapasiteettia Olen ilmeisesti päättänyt on 10 koska minulla yhden muuttujan tyypin pinon joka sisältää kaksi kenttää muistaa. Array, tässä tapauksessa on menossa olla joukko kokonaislukuja kuten on laita suurimman osan esimerkeistä. Ja toinen kokonaisluku muuttuja kykenee tallentamaan alkuun, viimeksi lisätyt elementti pino. Joten yksi pino mitä me aivan määritelty näyttää seuraavalta. Se on laatikko sisältää joukko 10 mitä on kokonaislukuja tässä tapauksessa ja toinen kokonaisluku muuttuja siellä vihreä osoittamaan pinon päälle. 

Asettaa alkuun pino me vain sanoa s.top. Näin saimme pääsyn alan rakenne muistuttaa. s.top ollessa 0 tehokkaasti ei tämä meidän pinoon. Joten jälleen meillä on kaksi toimintaa että voimme tehdä nyt. Emme voi työntää ja voimme pop. Aloitetaan push. Jälleen työntää lisää uuden elementti päällimmäinen. 

Joten mitä me tarvitsemme tehdä tämän taulukon toteutuksesta? Hyvin yleisesti push-toiminnon on menossa tarvitse hyväksyä osoitin pino. Nyt ottaa toisen ja miettiä sitä. Miksi haluamme hyväksyä osoitin pino? Recall edellinen videoita kiikaritähtäimellä ja osoittimia, mitä tapahtuisi, jos me vain lähetetään pino, s pikemminkin kuin parametri? Mitä todella välitetään siellä? Muista Luomme kopio kun välitämme sen funktio ellemme käytä osoittimia. Ja niin tämä toiminto työntää tarpeisiin hyväksyä osoitin pinoon niin että olemme todella muuttuu pino aiomme muuttaa. 

Toinen asia push varmaan haluaa hyväksyä on tieto tyypin arvo. Tässä tapauksessa, jälleen, kokonaisluku, joka aiomme lisätä huipulle pinon. Joten meillä meidän kahden parametrit. Mitä aiomme nyt tehdä sisällä push? No, yksinkertaisesti, me vain aio lisätä että elementti huipulle pinon ja sitten muuttaa, jos alkuun pino on, että s piste alkuun arvo. Joten tämä on mitä funktio ilmoitus push voisi näyttää vuonna array-pohjainen toteuttamista. 

Tämäkään ei ole kova ja nopea sääntö että voisit muuttaa tätä ja on se vaihtelee eri tavoin. Ehkä s julistetaan maailmanlaajuisesti. Ja niin sinun ei tarvitse edes siirtää se on parametrina. Tämä on jälleen vain Yleinen tapaus push. Ja on olemassa erilaisia tapoja toteuttaa se. Mutta tässä tapauksessa meidän push vie kaksi argumenttia, osoitin pino ja tieto tyypin arvo, kokonaisluku tässä tapauksessa. 

Joten me julisti s, me sanoi s.top ollessa 0. Nyt työnnä numero 28 pinoon. No mitä se tarkoittaa? No tällä hetkellä pinon on 0. Ja niin mitä pohjimmiltaan tulee tapahtumaan on aiomme pysyä numero 28 osaksi array sijainti 0. Melko yksinkertainen, oikea, että oli alkuun ja nyt olemme hyvä mennä. Ja sitten meidän täytyy muuttaa mitä päällimmäinen on. Niin että seuraavan kerran me push elementti, aiomme tallentaa sen array sijainti, luultavasti ei 0. Emme halua korvata mitä me vain laittaa sinne. Ja niin me vain siirtyä ylhäältä 1. Että luultavasti järkevää. 

Nyt jos haluamme laittaa toinen elementti pinoon, että haluamme ajaa 33, No nyt me vain vie 33 ja laita se array sijainti numero 1, ja sitten muuttaa kärkeen pino olla valikoimaan Sijainti numero kaksi. Joten jos seuraavan kerran haluamme push elementti pinoon, se tulee laittaa array sijainti 2. Ja tehdään se vielä kerran. Me ajaa 19 pois pinot. Laitamme 19 array sijainti 2 ja muuttaa kärkeen pinon olla array sijainti 3 joten jos seuraavan kerran täytyy tehdä push olemme hyvä mennä. 

OK, niin se työntää pähkinänkuoressa. Entä popping? Joten popping on eräänlainen vastine työntää. Se miten me poistaa tietoja pino. Ja yleensä pop tarpeisiin tehdä seuraavaa. Se tarvitsee hyväksyä osoitin pino, jälleen yleisessä tapauksessa. Joissakin muissa tapauksessa saatat ovat ilmoittaneet pino maailmanlaajuisesti, jolloin sinun ei tarvitse siirtää sitä koska siihen on jo pääsy siihen kuten globaali muuttuja. Mutta sitten mitä muuta meidän täytyy tehdä? No olimme monesko pinon push, joten olemme luultavasti menossa haluavat dekrementoidaan pinon päälle pop, eikö? Ja sitten tietenkin olemme myös menossa haluavat palauttaa arvon että poistamme. Jos lisäämme elementtejä, haluamme päästä elementit ulos myöhemmin, me luultavasti todella haluat tallentaa niitä niin me älä vain poista ne pino ja sitten tehdä mitään heidän kanssaan. Yleensä jos olemme työntämällä ja popping täällä haluamme säilyttää tämän tiedot tarkoituksenmukaisella tavalla ja niin se ei tee järkeä vain hävittää sen. Joten tämä toiminto olisi luultavasti palata arvo meille. 

Joten tämä on mitä ilmoitus pop voisi näyttää siellä ylhäällä vasemmalla. Tämä toiminto palauttaa data tyypin arvo. Jälleen olemme olleet käyttäen kokonaislukuja kaikkialla. Ja se hyväksyy osoittimen pinon sen ainoa argumentti tai ainoa parametri. Joten mitä on pop aikoo tehdä? Sanotaan haluamme nyt pop elementti pois s. Joten muistakaa Sanoin, että pinot ovat viime in, first out, LIFO tietorakenteita. Joka elementti on menossa poistetaan pinosta? Arvasit 19? Koska olisit oikeassa. 19 oli viimeinen elementti lisäsimme pino kun olimme työntää elementtejä, ja niin se tulee ensimmäinen elementti, joka saa poistaa. Aivan kuin sanoimme 28, ja sitten laittaa 33 sen päälle, ja laitamme 19 päälle, että. Ainoa elementti voimme ottaa pois on 19. 

Nyt kaavion täällä, mitä olen tehnyt on eräänlainen poistetaan 19 jono. Se ei ole oikeastaan mitä aiomme tehdä. Olemme juuri menossa eräänlainen ja teeskennellä se ei ole siellä. Se on edelleen siellä että muistipaikka, mutta me vain aio sivuuttaa sitä muuttamalla alkuun meidän pinon olemasta 3-2. Joten jos me nyt työntää toinen elementti pinoon, se yli kirjoittaa 19. 

Mutta älkäämme käydä läpi ongelmia poistamisen 19 pinosta. Voimme vain teeskennellä se ei ole siellä. Varten pinon se on mennyt, jos muutamme alkuun olevan 2 sijasta 3. Selvä, joten se oli aika paljon se. Siinä kaikki meidän täytyy tehdä pop elementti pois. Tehdään se uudestaan. Joten olen korostanut sen punaisella täällä osoittavat Teemme toisen puhelun. Aiomme tehdä sama asia. 

Joten mitä tulee tapahtumaan? No, me aiomme säilyttää 33 x ja olemme menossa muuttaa päällimmäinen 1. Niin että jos me nyt työntää elementin pinon johon olemme aikoo tehdä juuri nyt, mitä tulee tapahtumaan on aiomme päälleäänittävän array Sijainti numero 1. Jotta 33 joka oli tavallaan jäljellä takana me vain teeskenteli jota ei enää ole, me vain menossa jotta hakata sitä ja laittaa 40 siellä sijaan. Ja sitten tietenkin, koska teimme push, aiomme kasvattaa pinon 1-2 niin että jos me nyt lisätä toinen elementti se tulee mennä array Sijainti numero kaksi. 

Nyt liittyvät luettelot ovat toinen tapa toteuttaa pinot. Ja jos tämän määritelmän screen täällä näyttää tutulta, se johtuu se näyttää melkein täsmälleen sama, itse asiassa, se aika paljon on täsmälleen sama kuin yksinään linkitetty lista, Jos muistatte meidän keskustelua yksittäin sidoksissa luetteloita toinen video. Ainoa rajoitus tässä on meille ohjelmoijille, emme saa lisätä tai poistaa satunnaisesti alkaen yksittäin linkitetyn listan jota voisimme aiemmin tehdä. Voimme vain nyt lisätä ja poistaa etu- tai yläosan linkitetyn lista. Se on todella ainoa ero kuitenkin. Tämä on muuten yksittäin linkitetyn listan. Se on vain rajoitus korvaa itsellemme kuten ohjelmoijille, että muuttuu sen pinoon. 

Sääntö täällä on aina säilyttää osoitin johtaja linkitetyn listan. Tämä on tietysti yleisesti tärkeä sääntö ensin. Saat yksittäin linkitetty lista muutenkin sinua tarvitsee vain osoitin päähän jotta on, että ketju voitava siirtää joka toinen elementti vuonna linkitetty lista. Mutta se on erityisen tärkeää pino. Ja niin yleensä olet menossa todella haluavat tämä osoitin on globaali muuttuja. Se luultavasti olla jopa helpompaa näin. Mitkä ovat analogeja push ja pop? Oikea. Joten työntää taas on lisännyt uusi elementti pino. Vuonna linkitetty lista, joka tarkoittaa, että menossa on luoda uusi solmu, että olemme menossa lisätä osaksi linkitetty lista, ja noudata varovaisia ​​askelia että olemme edellä on selostettu vuonna yksittäin linkitettyjen listojen lisätä sen ketju rikkomatta ketjua ja menettämättä tai orpoutumista tahansa elementtejä linkitetyn listan. Ja se on periaatteessa mitä että pikku möykky tekstiä siellä tiivistää. Ja lähdetään katsomaan sitä kuin kaavio. 

Joten tässä on meidän linkitetty lista. Se samanaikaisesti sisältää neljä osatekijää. Ja täydellisemmin tässä meidän pino sisältää neljä elementtejä. Ja sanotaanko haluamme nyt työntää uusi kohde päälle tämä pino. Ja haluamme työntää uusi Tuote, jonka data-arvo on 12. No mitä aiomme tehdä? No ensimmäinen aiomme malloc tila, dynaamisesti jakaa tilaa uusi solmu. Ja tietenkin heti me soittaa malloc me aina varmista tarkistaa null, koska jos meillä null takaisin siellä oli jonkinlainen ongelma. Emme halua dereference että null osoitin tai tulet kärsimään seg vika. Tuo ei ole hyvä. Joten olemme malloced solmun. Oletamme meillä on ollut menestys täällä. Aiomme laittaa 12 otetaan datakentässä, että solmun. Nyt te muistatte joka meidän osoittimia siirtyy ensi joten emme katkaisemiseksi? Meillä on pari vaihtoehtoa täällä, mutta ainoa, joka tulee olemaan turvallinen on asettaa uutinen ensi osoitin kohta vanhaan johtaja luettelon tai mitä pian vanha pää luettelon. Ja nyt, että meidän kaikkien elementit ketjuttaa, voimme vain siirtyä luettelon kohtaan samaan paikkaan, että uudet ei. Ja olemme nyt käytännössä ajanut uusi elementti päälle edessä pinon. 

Pop me vain haluamme poistaa että ensimmäinen elementti. Ja niin periaatteessa mitä meidän on tehtävä täällä, hyvin meidän täytyy löytää toinen elementti. Lopulta että tulee uusi pää kun olemme poistaa ensimmäinen. Joten meidän täytyy vain aloittaa alusta, siirtyä yksi eteenpäin. Kun meillä otteen yksi eteenpäin siitä, missä olemme tällä hetkellä ovat voimme poistaa ensimmäinen turvallisesti ja sitten voimme vain siirtää pään osoittamaan, mikä oli Toinen termi ja sitten nyt on ensimmäinen sen jälkeen solmu on poistettu. 

Joten jälleen, kun tarkastellaan sitä kun kaavio me haluavat nyt pop elementti pois tähän pinoon. Joten mitä me teemme? No me ensin luomassa uusi osoitin, joka menee osoittamaan samaan paikkaan kuin pää. Aiomme siirtää sen yhden paikan eteenpäin sanomalla Trav tasavertaisten trav ensi esimerkiksi, joka edistäisi Trav osoitin yksi asentoon eteenpäin. Nyt kun meillä pitää ensimmäisen elementin kautta osoitin kutsutaan luettelo, ja Toinen elementti läpi osoitin nimeltään trav, voimme turvallisesti poistaa että ensimmäinen elementti pinosta menettämättä loput Ketjun koska me on tapa viitata toiseen osaan välittämään tavalla osoitin kutsutaan trav. 

Joten nyt voimme vapauttaa että solmu. Voimme ilmainen luettelo. Ja sitten kaikki meidän täytyy tehdä nyt on Siirrä lista viittaavat samaan paikkaan että trav tekee, ja olemme tavallaan takaisin jossa aloitimme ennen kuin työnsi 12 on ensimmäinen paikka, oikea. Juuri tässä me olimme. Meillä oli tämän neljän elementin pino. Lisäsimme viidesosa. Työnsimme viidesosa elementin, ja sitten me piipahti että viimeksi lisätty elementti perääntymään. 

Se on oikeastaan ​​aika paljon kaikki on pinot. Voit toteuttaa ne taulukot. Voit toteuttaa ne liittyvät luettelot. On, tietenkin, muiden tapoja toteuttaa niitä. Periaatteessa syystä käyttäisi pinot on ylläpitää dataa siten, että viimeksi lisätyt elementti on ensimmäinen asia olemme menossa halua saada takaisin. Olen Doug Lloyd, tämä on CS50.