DOUG LLOYD: Oké, dus door dit punt bent waarschijnlijk vrij vertrouwd met arrays en gelinkte lijsten dat de twee belangrijkste datastructuren we hebben sprak over voor het houden sets gegevens van soortgelijke data georganiseerd. Nu gaan we praten over een paar variaties arrays en gelinkte lijsten. In deze video gaan we om te praten over stapels. Concreet gaan we praten over een gegevensstructuur genaamd een stapel. Recall van eerdere discussies over pointers en het geheugen, of de stapel ook naam voor een segment van het geheugen waarbij statisch verklaard memory-- geheugen dat u naam, variabelen die u noemt, et cetera en functie frames die ook call-stack frames bestaan. Dit is dus een stapel datastructuur geen stack segment van het geheugen. OK. 

Maar wat is een stapel? Dus het is vrij veel slechts een speciaal soort structuur dat de gegevens handhaaft op een georganiseerde manier. En er zijn twee zeer voorkomende manieren om te implementeren stapels met twee gegevensstructuren dat we al bekend zijn met, arrays en gelinkte lijsten. Wat maakt een stapel speciaal is de manier waarop plaatsen we informatie in de stack, en de manier waarop we Verwijder informatie van de stapel. Vooral met stapels de regel is alleen de meest recent toegevoegde element kan worden verwijderd. 

Dus denk erover alsof het een stapel. We stapelen informatie bovenop zichzelf, en alleen de ding boven van de paal kan worden verwijderd. We kunnen het niet verwijderen van de zaak onder omdat alles anders zou instorten en omvallen. Dus we bouwen een stack die we dan moeten stuk voor stuk te verwijderen. Hierdoor hebben we vaak verwijzen Stapels als LIFO structuur, last in, first out. LIFO, last in, first out. 

Omdat deze beperking hoe informatie kan worden toegevoegd aan en verwijderd uit een stapel, er is echt slechts twee dingen die we kunnen doen met een stack. We kunnen duwen, wat het term die we gebruiken voor het toevoegen een nieuw element aan de bovenkant van de stack of wanneer de stapel niet bestaat en we zijn er creëren vanuit het niets, het creëren van de stapel in de eerste plaats zou duwen. En pop dan, dat is het soort van CS term die we gebruiken om de meest recent verwijderen toegevoegde element van de bovenkant van de stapel. 

Dus we gaan op zowel kijken implementaties, zowel array gebaseerde en gelinkte lijst gebaseerd. En we gaan beginnen met array gebaseerde. Dus hier is het basisidee van wat de array gebaseerde stack datastructuur eruit zou zien. We hebben een getypte definitie hier. Binnenkant van dat we twee leden of gebied van de structuur. We hebben een scala. En nogmaals, ik ben met behulp van de willekeurige data type waarde. 

Dus dit elk gegevenstype kan zijn, int char of een andere data typt u eerder hebt gemaakt. Dus we hebben een scala van grootte capaciteit. Capaciteit wordt een pond gedefinieerd constant, misschien ergens anders in ons bestand. Zo merkt al met deze implementatie wij begrenzende onszelf als typisch was het geval met arrays die we kunnen niet dynamisch vergroten of verkleinen, waar een aantal maximale elementen we kunnen zetten in onze stack. In dit geval is het vermogen elementen. 

We houden ook het bijhouden van de bovenkant van de stapel. Wat element is de onlangs toegevoegd aan de stapel? En zo houden we van die in een top variabele genaamd. En dit alles wordt samen verpakt een nieuw datatype zogenaamde stack. En zodra we zijn geschapen dit nieuwe type data kunnen we het behandelen als andere soorten data. We kunnen verklaren stack s, net als we konden int x, y of klusje doen. En als we zeggen stapelen s, goed wat er gebeurt is krijgen we een set van geheugen gereserveerd voor ons. 

In dit geval wordt de capaciteit Ik heb blijkbaar besloten 10 omdat ik heb enkele variabele van het type stack die bevat twee velden te roepen. Een array, in dit geval gaat een array van gehele getallen zoals in de meeste van mijn voorbeelden. En een andere integer variabele geschikt voor het opslaan boven, De meest recent toegevoegde element om de stapel. Dus één stapel van wat wij net gedefinieerd ziet er als volgt. Het is een doos met een array van 10 wat zal zijn gehele getallen in deze zaak en een andere integer variabele er in het groen naar de top van de stack geven. 

Naar de top van de termijn stack we gewoon s.top zeggen. Dat is hoe we toegang tot een veld van een structuur recall. s.top gelijk is aan 0 effectief Dit doet ons stack. Dus nogmaals hebben we twee operaties dat we nu kunnen uitvoeren. We kunnen duwen en we kunnen pop. Laten we beginnen met push. Nogmaals, het duwen is het toevoegen van een nieuwe element naar de top van de stack. 

Dus wat moeten we doen deze array gebaseerde implementatie? Welnu, in het algemeen de push-functie gaat nodig hebben om een ​​accepteren Pointer naar de stapel. Neem nu een tweede en denk erover na. Waarom zouden we willen accepteren een pointer naar de stapel? Recall van de vorige video's op variabele reikwijdte en pointers, wat er zou gebeuren als we gewoon gestuurd stack, s plaats in als een parameter? Wat zou eigenlijk worden doorgegeven daar? Vergeet niet dat we het maken van een kopie als we doorgeven aan een functie tenzij we gebruiken pointers. En dus deze functie te duwen behoeften een pointer naar de stapel accepteren zodat we daadwerkelijk te veranderen de stapel willen we veranderen. 

Het andere ding push waarschijnlijk wil aanvaarden is een data-element van het type waarde. In dit geval weer een geheel getal dat we gaan toe te voegen aan de top van de stapel. Dus we hebben onze twee parameters. Wat gaan we nu doen binnenkant van push? Nou, gewoon, we gaan gewoon om toe te voegen dat element aan de bovenkant van de stapel en wijzig waar de top van de stapel, dat S DOT top waarde. Dus dit is wat een functie verklaring voor push eruit zou kunnen zien in een array-gebaseerde implementatie. 

Ook dit is niet een harde en snelle regel dat je dit zou kunnen veranderen en Het variëren op verschillende manieren. Misschien s is wereldwijd uitgeroepen. En dus heb je niet eens nodig pass is als een parameter. Dit is opnieuw slechts een algemene geval voor push. Er zijn verschillende manieren om het uit te voeren. Maar in dit geval onze push gaat nemen twee argumenten, een pointer naar een stapel en een data-element van het type waarde, integer in dit geval. 

Dus we verklaard s, we zei s.top gelijk is aan 0. Laten we nu druk op de nummer 28 op de stapel. Tja, wat betekent dat? Goed moment de bovenkant van de stapel 0. En dus wat is eigenlijk gaat gebeuren is we gaan het aantal steken 28 in de serie locatie 0. Vrij eenvoudig, recht, dat was de top en nu zijn we goed om te gaan. En dan moeten we wat veranderen de top van de stack wordt. Zodat de volgende keer duwen we een element, we gaan het op te slaan in scala locatie, waarschijnlijk niet 0. We willen niet overschrijven wat we daar te zetten gewoon. En dus gaan we gewoon verder de top naar 1. Dat maakt het waarschijnlijk zinvol. 

Nu willen we een ander element te zetten op de stapel, zeggen we willen duwen 33, en nu zijn we gewoon gaan nemen 33 en zet het op scala locatie nummer 1, en wijzig de top van onze stack array plaats nummer twee. Dus als de volgende keer dat we willen duwen een element op de stack, het zal in slagorde locatie 2 worden gezet. En laten we dat nog een keer. We zullen duwen 19 off van de stacks. We zullen 19 toegerust locatie 2 zetten en verander de top van onze stack array locatie 3 zijn dus als we de volgende keer moet een push we goed te gaan maken. 

OK, dus dat is het duwen in een notendop. Hoe zit het met popping? Dus popping is het soort tegenhanger duwen. Het is hoe we gegevens uit de stapel te verwijderen. En in het algemeen pop behoeften het volgende doen. Het moet een verwijzing naar het accepteren stack, opnieuw het algemene geval. In sommige andere geval je misschien hebben de stapel wereldwijd verklaard, in welk geval u niet hoeft door te geven in want het heeft al toegang tot deze als een globale variabele. Maar wat anders doen we moeten doen? Wel waren we verhogen de bovenkant van de stapel duwen, dus we waarschijnlijk zal willen aan de bovenkant van de stapel verlagen in pop, toch? En dan natuurlijk We zijn ook van plan te willen de waarde die we verwijderen terugkeren. Als we elementen toe te voegen, willen we elementen later op te krijgen, we waarschijnlijk eigenlijk willen ze dus we slaan ze niet gewoon verwijderen van de stapelen en vervolgens niets doen met hen. Over het algemeen als we duwen en hier popping We willen dit op te slaan informatie op een zinvolle manier en zo is het niet maken zin om gewoon gooi hem weg. Dus deze functie moet Waarschijnlijk een waarde terug te keren naar ons. 

Dus dit is wat een verklaring voor pop eruit zou kunnen zien is er in de linkerbovenhoek. Deze functie geeft gegevens van het type waarde. Opnieuw hebben we het gebruik geweest integers overal. En een pointer naar een stack accepteert zijn enige argument of enige parameter. Dus wat is pop gaat doen? Laten we zeggen dat we willen nu pop een element uit van s. Dus onthoud ik zei dat stapels zijn laatste in, first out, LIFO datastructuren. Welk element gaat van de stapel worden verwijderd? Hebt u raden 19? Omdat je gelijk zou zijn. 19 was het laatste element we toegevoegd stack toen we duwen elementen op, en zo het gaat om de eerste element dat wordt verwijderd. Het is alsof we zeiden 28 en dan zetten we 33 op de top van het, en zetten we 19 op de top van dat. Het enige element kunnen we opstijgen is 19. 

Nu in het diagram hier wat ik heb gedaan is een soort van 19 verwijderd uit de array. Dat is niet echt wat we gaan doen. We gaan gewoon naar soort van te doen alsof het er niet is. Het is er nog steeds in dat het geheugen locatie, maar we gaan gewoon te negeren door het veranderen van de top van onze stack van die 3-2. Dus als we nu te duwen een ander element op de stack, het zou dan te schrijven 19. 

Maar laten we niet gaan door de moeite schrappen 19 van de stapel. We kunnen net doen alsof het er niet is. Voor de toepassing van de stapel het is gegaan als we veranderen boven om 2 in plaats van 3. Oké, dus dat was het wel zo'n beetje. Dat is alles wat we moeten doen een element knallen. Laten we het nog eens doen. Dus ik heb het rood gemarkeerd hier geven we een andere oproep maken. We gaan hetzelfde doen. 

Dus wat gaat er gebeuren? Nou, we gaan slaan 33 in x en we gaan naar de top van de stack veranderen 1. Dus dat als we nu een push element in de stapel die we ga naar rechts nu doen, wat gaat er gebeuren is we gaan overschrijven scala locatie nummer 1. Zodat 33 dat soort werd achtergelaten achter dat we net alsof is er niet meer, we gewoon gaan om het afranselen en zet 40 daar van harte welkom. En dan natuurlijk, omdat we maakten een duw, we gaan naar het verhogen bovenkant van de stapel 1-2 dus dat als we nu toevoegen een ander element het zal ga in serie plaats nummer twee. 

Nu gekoppelde lijsten ander manier om stapels voeren. Als deze definitie op screen hier ziet er bekend uit voor u, het is want het ziet er bijna dezelfde, in feite, het vrij veel is precies hetzelfde als enkelvoudig gekoppelde lijst, Als u zich herinneren van onze bespreking van enkelvoudig gelinkte lijsten in een andere video. De enige beperking hier is voor ons als programmeurs, we zijn niet toegestaan invoegen of verwijderen willekeurig uit de enkelvoudig gelinkte lijst die we eerder konden doen. We kunnen nu alleen invoegen en verwijderen uit de voor- of bovenzijde van de gekoppelde lijst. Dat is echt de enige verschil hoor. Dit is anders een enkelvoudig gelinkte lijst. Het is slechts de beperking vervangen onszelf als programmeurs dat verandert het in een stapel. 

De regel is hier altijd een Pointer naar het hoofd van een gekoppelde lijst. Dit is natuurlijk algemeen belangrijke regel als eerste. Voor afzonderlijk gelinkte lijst toch je alleen een pointer naar de kop om te hebben dat keten kunnen verwijzen elk ander element in de gekoppelde lijst. Maar het is vooral belangrijk bij een stack. En dus over het algemeen je bent gaat eigenlijk willen Deze pointer naar een globale variabele. Het gaat waarschijnlijk zelfs gemakkelijker op die manier. Dus wat zijn de analogen van push en pop? Rechts. Dus nogmaals duwen voegt een nieuw element aan de stapel. In een gekoppelde lijst die betekent dat we gaan moeten naar een nieuw knooppunt dat we creëren ga toe te voegen in de gelinkte lijst, en volg de voorzichtige stappen die we eerder hebben geschetst in afzonderlijk gelinkte lijsten toe te voegen aan de ketting zonder de ketting en het verliezen of orphaning elke elementen van de gekoppelde lijst. En dat is eigenlijk wat dat kleine blob van tekst is er een samenvatting. En laten we eens een kijkje het als een diagram. 

Dus hier is onze gelinkte lijst. Het bevat tegelijk vier elementen. En meer perfect hier onze stack met vier elementen. En laten we zeggen dat we nu willen duwen een nieuw item op deze stapel. En we willen een nieuwe push voorwerp waarvan de gegevens waarde is 12. Nou, wat gaan we doen? Wel eerst gaan we malloc ruimte, dynamisch toewijzen ruimte voor een nieuw knooppunt. En natuurlijk onmiddellijk na maken we een oproep om altijd malloc we zorg ervoor om te controleren op null, want als we nul terug er was een soort van probleem. We willen niet dereferentie dat null aanwijzer of u een seg fout lijden. Dat is niet goed. Dus we hebben malloced van het knooppunt. We gaan ervan uit dat we succes hadden hier. We gaan om te zetten in 12 het dataveld van dat knooppunt. Nu heb je te herinneren welke van onze pointers verhuist komende zodat we niet breken de keten? We hebben een paar opties hier, maar de enige die gaat om veilig te zijn is het nieuws volgende pointer op te zetten punt om de oude hoofd van de lijst of wat zal binnenkort de oude kop van de lijst. En nu dat al onze elementen worden aan elkaar geketend, kunnen we gewoon verhuizen lijst te wijzen op dezelfde plaats die nieuwe doet. En we hebben nu effectief geduwd een nieuw element op de voorkant van de stapel. 

Pop we willen gewoon verwijderen die eerste element. En dus eigenlijk wat we hebben hier te doen, goed we moeten het tweede element te vinden. Uiteindelijk dat zal de nieuwe worden hoofd nadat we de eerste te verwijderen. Dus we hoeven alleen maar uit te gaan van het begin, ga één vooruit. Zodra we hebben een greep op één voorwaarts waar we op dit moment zijn we de eerste veilig verwijderen en dan kunnen we gewoon bewegen het hoofd te wijzen op wat de tweede termijn en nu dan is de eerste daarna knooppunt is verwijderd. 

Dus nogmaals, het nemen van een blik het als een diagram wij wil nu een pop onderdeel uit van deze stapel. Dus wat doen we? Nou we eerst gaat maken een nieuw pointer dat gaat te wijzen op dezelfde plek als het hoofd. We gaan het één positie te verplaatsen voorwaarts door te zeggen trav gelijken trav volgende bijvoorbeeld, die zou het trav wijzer één vooruit positie naar voren. Nu dat we hebben een Houd op het eerste element door de wijzer genaamd lijst en de tweede element door middel van een pointer genaamd trav, kunnen we veilig verwijderen dat eerste element van de stapel zonder dat de overige van de keten omdat we een manier verwijzen met het tweede element doorsturen door middel van de pointer genaamd trav. 

Dus nu kunnen we bevrijden dat knooppunt. We kunnen bevrijden lijst. En dan alles wat we nu moeten doen is lijst te verplaatsen naar naar dezelfde plaats trav dat doet, en we zijn een soort van back waar we begonnen voordat we geduwd 12 op in de eerste plaats, rechts. Dit is precies waar we waren. We hadden deze vier elementen stack. We voegden een vijfde. We geduwd een vijfde element op, en dan hebben we geknald die het meest recent back off toegevoegd element. 

Dat is echt vrij veel alles wat er te stacks. U kunt ze uit te voeren als arrays. U kunt ze uit te voeren zoals gelinkte lijsten. Er zijn natuurlijk andere manieren om ze uit te voeren ook. Eigenlijk de reden dat we zouden gebruiken stacks is gegevens zodanig te handhaven dat de meest recent toegevoegde element is het eerste wat we gaat te willen terug te krijgen. Ik ben Doug Lloyd, dit is CS50.