DOUG LLOYD: Alle reg, so by hierdie punt is jy waarskynlik redelik vertroud met skikkings en geskakelde lyste wat is die twee primêre data strukture wat ons het gepraat oor vir die behoud van stelle data van soortgelyke tipes data georganiseer. Nou gaan ons praat oor 'n paar variasies op skikkings en geskakelde lyste. In hierdie video wat ons gaan om te praat oor stapels. Spesifiek ons ​​gaan praat ongeveer 'n data struktuur genaamd 'n stapel. Onthou van die vorige besprekings oor wysers en geheue, dat die stapel is ook die naam vir 'n segment van die geheue waar staties verklaar memory-- geheue dat jy noem, veranderlikes wat jy noem, et ens en funksie rame wat ons ook oproep stapel rame bestaan ​​nie. So, dit is 'n stapel data struktuur nie 'n stapel segment van die geheue. OK. 

Maar wat is 'n stapel? So dit is pretty much net 'n spesiale soort struktuur dat die data handhaaf in 'n georganiseerde manier. En daar is twee baie algemene maniere om te implementeer stapels met behulp van twee data strukture dat ons reeds vertroud is met, skikkings en geskakelde lyste. Wat maak 'n stapel spesiaal maak, is die manier waarop ons sit inligting in die stapel, en die manier waarop ons verwyder inligting van die stapel. In die besonder met stapels die reël is net die mees onlangs bygevoeg element kan verwyder word. 

So dink oor dit asof dit 'n stapel. Ons hei inligting op die top van die self, en net die ding op die top van die paal verwyder kan word. Ons kan nie die ding onder want anders sou alles ineenstorting en val oor. So ons werklik die bou van 'n stapel dat ons dan 'n stuk te verwyder stuk. As gevolg van hierdie ons gewoonlik verwys om 'n stapel as 'n LIFO struktuur, laaste in, eerste uit. LIFO, laaste in, eerste uit. 

So as gevolg van hierdie beperking op hoe inligting kan bygevoeg word om en verwyder van 'n stapel, daar is regtig net twee dinge wat ons kan doen met 'n stapel. Ons kan stoot, wat is die term wat ons gebruik vir die toevoeging 'n nuwe element na die top van die stapel, of as die stapel bestaan ​​nie en ons is dit skep van nuuts af, die skep van die stapel in die eerste plek sou wees stoot. En pop dan, dis die soort van CS term wat ons gebruik om die mees onlangs verwyder bygevoeg element van die top van die stapel. 

So ons gaan by albei kyk implementering, sowel verskeidenheid gebaseer en gekoppel lys gebasseer. En ons gaan begin met array gebaseer is. So hier is die basiese idee van wat die skikking gebaseer stapel data struktuur sou lyk. Ons het 'n getikte definisie hier. Binnekant van dat ons twee lede of velde van die struktuur. Ons het 'n skikking. En weer die gebruik van die ek arbitrêre data tipe waarde. 

So dit enige tipe data kan wees, int char of 'n ander data tik jy voorheen geskep. So ons het 'n verskeidenheid van grootte kapasiteit. Kapasiteit om 'n pond gedefinieer konstante, dalk iewers anders in ons lêer. So sien reeds met hierdie implementering ons jaag onsself as tipies was die geval met die skikkings, wat ons nie kan dinamies verander, waar daar 'n sekere aantal maksimum elemente wat ons kan in ons stapel. In hierdie geval is dit kapasiteit elemente. 

Ons hou ook rekord van die top van die stapel. Wat is die mees element onlangs by die stapel? En so hou ons op hoogte van wat in 'n top veranderlike genoem. En dit alles kry saam toegedraai in 'n nuwe soort data genoem 'n stapel. En sodra ons geskep hierdie nuwe tipe data ons kan dit behandel soos enige ander tipe data. Ons kan verklaar stapel s, net soos ons kon int x, of char y te doen. En wanneer ons sê stapel s, goed wat gebeur is ons kry 'n stel van geheue opsy gesit vir ons. 

In hierdie geval kapasiteit Ek het blykbaar besluit 10 want ek het enkele veranderlike van tipe stapel wat bestaan ​​uit twee velde te onthou. 'N skikking, in hierdie geval gaan om 'n verskeidenheid van heelgetalle wees soos die geval is in die meeste van my voorbeelde. En 'n ander heelgetalveranderlike kan stoor die top, die mees onlangs bygevoeg element van die stapel. So 'n enkele stapel van wat ons net gedefinieer lyk. Dit is 'n boks met 'n verskeidenheid van 10 wat sal wees heelgetalle in hierdie geval en 'n ander heelgetalveranderlike daar in die groen na die top van die stapel te dui. 

Na die top van die stel stapel ons net s.top sê. Dit is hoe ons toegang tot 'n gebied van 'n struktuur herroep. s.top gelyk 0 effektief doen dit om ons stapel. So weer het ons twee operasies dat ons nou kan doen. Ons kan stoot en ons kan pop. Kom ons begin met die druk. Weer, stoot is die toevoeging van 'n nuwe element na die top van die stapel. 

So, wat moet ons doen om te doen in hierdie verskeidenheid gebaseer implementering? Wel, in die algemeen is die druk funksie gaan nodig om 'n te aanvaar wyser na die stapel. Neem nou 'n tweede en daaroor dink. Hoekom sal ons wil aanvaar 'n verwysing na die stapel? Onthou van die vorige video's op veranderlike omvang en wysers, wat sou gebeur as ons net gestuur stapel, is eerder as 'n parameter? Wat sou eintlik geslaag word daar? Onthou ons is die skep van 'n afskrif wanneer ons dit slaag om 'n funksie tensy ons gebruik wenke. En so hierdie funksie te stoot behoeftes om 'n wyser na die stapel te aanvaar sodat ons eintlik verander die stapel ons beoog om te verander. 

Die ander ding druk waarskynlik wil aanvaar is 'n data element van die tipe waarde. In hierdie geval, weer, 'n heelgetal wat ons gaan om te voeg by die top van stapel. So ons het ons twee parameters. Wat gaan ons nou binnekant van druk? Wel, eenvoudig, ons gaan net om by te voeg daardie element na die top van die stapel en dan verander waar die top van die stapel is, dat is dot top waarde. So dit is wat 'n funksie verklaring vir druk kan lyk in 'n skikking gebaseer implementering. 

Weereens is dit nie 'n vaste reël dat jy dit kan verander en dit wissel in verskillende maniere. Miskien s is globaal verklaar. En so het jy nie eens nodig om te slaag is dit as 'n parameter. Dit is weer net 'n algemene geval vir stoot. En daar is verskillende maniere om dit te implementeer. Maar in hierdie geval ons druk gaan neem twee argumente, 'n verwysing na 'n stapel en 'n data element van die tipe waarde heelgetal in hierdie geval. 

Sodat ons verklaar s, ons gesê s.top gelyk 0. Nou laat druk die getal 28 op die stapel. Wel, wat beteken dit? Wel tans die top van die stapel is 0. En so wat is basies gaan gebeur is ons gaan die aantal vashou 28 in verskeidenheid ligging 0. Redelik eenvoudig, reg, wat was die top en nou is ons goed om te gaan. En dan moet ons wat verander die top van die stapel sal wees. Sodat die volgende keer Ons stoot 'n element in, ons gaan om dit te stoor in array plek, waarskynlik nie 0. Ons wil nie oorskryf wat ons daar sit net. En so sal ons net beweeg die top 1. Dit maak waarskynlik sin. 

Nou as ons wil 'n ander element sit op die stapel, sê ons wil stoot 33, nou goed ons net gaan neem 33 en sit dit op array plek getal 1, en dan verander die top van ons stapel te array plek nommer twee wees. So as die volgende keer wat ons wil stoot 'n element op die stapel, dit sal opgestel ligging 2 word. En laat ons doen wat 'n mens meer tyd. Ons sal stoot 19 af van die stapels. Ons sal 19 opgestel ligging 2 sit en verander die top van ons stapel om array plek 3 wees so as die volgende keer wat ons nodig om 'n druk ons ​​goed om te gaan maak. 

OK, so dit is stoot in 'n neutedop. Wat van die knal? So knal is die soort van eweknie stoot. Dit is hoe ons die data van die stapel te verwyder. En in die algemeen pop behoeftes om die volgende te doen. Dit moet 'n verwysing na die aanvaar stapel weer in die algemene geval. In 'n ander geval jy dalk het die stapel globaal verklaar, in welke geval jy nie nodig het om dit te slaag in, want dit het reeds toegang tot dit as 'n globale veranderlike. Maar wat anders om te doen wat ons moet doen? Wel, ons is die verhoog die top van die stapel in stoot, so ons is waarskynlik gaan om te wil na die top van die stapel decrement in pop, reg? En dan natuurlik Ons gaan ook om te wil om die waarde wat ons verwyder terugkeer. As ons die toevoeging van elemente, ons wil elemente uit later te kry, ons waarskynlik eintlik hulle wil, sodat ons stoor nie net hulle verwyder uit die stapel en dan niks doen nie met hulle. Algemeen as ons stoot en hier knal Ons wil hierdie berg inligting in 'n sinvolle manier en so is dit nie maak sin om net weggooi nie. So Hierdie funksie moet waarskynlik 'n waarde terug te keer na ons. 

So dit is wat 'n verklaring vir die pop kan lyk asof daar by die top links. Hierdie funksie opbrengste data van die tipe waarde. Weereens het ons met behulp van al heelgetalle regdeur. En dit 'n verwysing na 'n stapel soos aanvaar sy uitsluitlike argument of enigste parameter. So, wat is pop gaan doen? Kom ons sê ons wil nou pop 'n element af van s. So onthou ek het gesê dat stapels is verlede in, eerste uit, LIEU data strukture. Watter element gaan uit die stapel verwyder? Het jy dink 19? Omdat jy reg sou wees. 19 was die laaste element wat ons by die stapel toe ons stoot elemente, en so gaan dit die eerste element wat kry verwyder. Dit is asof ons sê 28, en dan sit ons 33 op die top van dit, en ons het 19 op die top van dit. Die enigste element kan ons af te neem is 19. 

Nou in die diagram hier wat ek gedoen het is 'n soort van geskrap 19 van die skikking. Dit is nie eintlik wat ons gaan doen. Ons is net gaan om te soort van voorgee dit is nie daar nie. Dit is nog steeds daar in dat die geheue plek, maar ons gaan net om dit te ignoreer deur die verandering van die top van ons stapel uit om 3-2. So as ons nou stoot 'n ander element op die stapel, dit sou oor skryf 19. 

Maar laat ons nie te gaan deur die moeite van die verwydering van 19 uit die stapel. Ons kan net voorgee dit is nie daar nie. Vir die doeleindes van die stapel dit is weg as ons verander die top te wees in plaas van 2 3. Alle reg, so dit was pretty much dit. Dit is al wat ons nodig het om te doen om 'n element pop af. Kom ons doen dit weer. So ek het dit in rooi uitgelig hier om dui ons nog 'n oproep maak. Ons gaan na dieselfde ding te doen. 

So, wat gaan gebeur? Wel, ons gaan om te slaan 33 in x en ons gaan na die top van die stapel te verander na 1. Sodat as ons nou 'n stoot element in die stapel wat ons gaan nou te doen, wat gaan gebeur is ons gaan oorskryf verskeidenheid ligging nommer 1. Sodat 33 dat die soort van gelaat agter dat ons net voorgegee nie daar is nie, is ons net gaan om dit afranselen en sit 40 daar plaas. En dan natuurlik, aangesien ons het 'n stoot, ons gaan die inkrementeer top van die stapel 1-2 sodat as ons nou voeg 'n ander element Dit sal gaan in verskeidenheid ligging nommer twee. 

Nou gekoppel lyste is 'n ander manier om stapels implementeer. En as hierdie definisie op die skerm hier lyk bekend vir julle, dit is omdat dit lyk amper presies dieselfde, in werklikheid, dit pretty much presies dieselfde as 'n enkel gekoppel lys As jy onthou van ons bespreking van enkel geskakelde lyste in 'n ander video. Die enigste beperking hier is vir ons as programmeerders, ons is nie toegelaat om voeg of te verwyder lukraak uit die enkel geskakelde lys wat ons voorheen kon doen nie. Ons kan nou eers in te voeg en te verwyder van die voorkant of die top van die gekoppelde lys. Dit is regtig die enigste verskil egter. Dit is andersins 'n enkel geskakelde lys. Dit is net die beperking vervang op onsself as programmeerders wat verander dit in 'n stapel. 

Die reël hier is om altyd handhaaf 'n wyser na die hoof van 'n geskakelde lys. Dit is natuurlik 'n algemeen belangrike reël eerste. Vir enkel geskakelde lys in elk geval wat jy net 'n wyser na die hoof om daardie ketting in staat wees om te verwys elke ander element in die geskakelde lys. Maar dit is veral belangrik om met 'n stapel. En so algemeen is jy gaan eintlik wil hierdie wyser na 'n globale veranderlike. Dit is waarskynlik gaan om selfs makliker manier. So, wat is die analoë van druk en pop? Reg. So weer stoot is die toevoeging 'n nuwe element tot die stapel. In 'n geskakelde lys wat beteken dat ons gaan hê om 'n nuwe node dat ons skep gaan voeg in die geskakelde lys, en dan volg die stappe versigtig dat ons voorheen uiteengesit in enkel geskakelde lyste te voeg tot die ketting sonder om te breek die ketting en verloor of enige orphaning elemente van die geskakelde lys. En dit is basies wat dit bietjie blob van die teks is daar 'n opsomming. En laat ons 'n blik dit as 'n diagram. 

So hier is ons geskakelde lys. Dit bevat gelyktydig vier elemente. En meer perfek hier is ons stapel met vier elemente. En laat ons sê ons wil nou druk 'n nuwe item op die stapel. En ons wil 'n nuwe druk item wie data waarde is 12. Wel, wat gaan ons doen? Wel in die eerste gaan ons malloc ruimte, dinamiese toeken ruimte vir 'n nuwe knoop. En natuurlik onmiddellik na Ons maak 'n oproep om altyd malloc ons maak seker dat jy check for null, want as ons het null terug daar was 'n soort van probleem. Ons wil nie dereference dat null wyser, of jy sal 'n seg skuld ly. Dit is nie goed nie. Dus het ons malloced van die knoop. Ons sal ons aanvaar het sukses hier gehad het. Ons gaan sit in 12 die veld data van daardie knoop. Nou onthou jy wat van ons wenke beweeg langs sodat ons nie breek die ketting? Ons het 'n paar van die opsies hier, maar die enigste een wat gaan om veilig te wees is om die nuus volgende wyser te stel punt na die ou hoof van die lys of wat sal binnekort die ou hoof van die lys. En nou dat almal van ons elemente saam vasgeketting, kan ons net beweeg lys te wys na dieselfde plek dat die nuwe werk. En ons het nou effektief gestoot n nuwe element op die voorkant van die stapel. 

Pop ons wil net verwyder die eerste element. En so basies wat ons het hier te doen, Wel, ons het na die tweede element te vind. Uiteindelik sal die nuut geword kop nadat ons die eerste een te verwyder. So ons moet net om te begin van die begin, skuif een vorentoe. Sodra ons het 'n houvas op die een vorentoe van waar ons tans is ons die eerste een veilig verwyder en dan kan ons net beweeg die hoof om te verwys na wat was die tweede kwartaal en dan nou is die eerste daarna node is verwyder. 

So weer, neem 'n blik dit as 'n diagram ons nou wil pop 'n element af van hierdie stapel. So, wat doen ons? Wel ons eerste gaan skep 'n nuwe wyser wat gaan om te verwys na dieselfde plek as die hoof. Ons gaan dit een posisie beweeg vorentoe deur te sê trav gelykes Trav volgende byvoorbeeld, wat sou die trav wyser een bevorder posisie vorentoe. Nou dat ons het 'n hou op die eerste element deur die wyser genoem lys en die tweede element deur 'n wyser genoem trav, kan ons veilig verwyder wat eerste element van die stapel sonder dat die res van die ketting, want ons het 'n manier om te verwys na die tweede element stuur deur middel van die wyser genoem trav. 

So nou kan ons daardie knoop. Ons kan bevry lys. En dan sal al ons nou moet doen, is om lys te skuif na punt na dieselfde plek wat trav doen, en ons is soort van terug waar ons begin het voordat ons gestoot 12 in die eerste plek, reg. Dit is presies waar ons was. Ons het hierdie vier element stapel. Ons het 'n vyfde plek. Ons gestoot 'n vyfde element op, en dan sal ons inloer wat mees onlangs back off bygevoeg element. 

Dit is regtig baie mooi al wat daar is om stapels. Jy kan dit te implementeer as skikkings. Jy kan dit te implementeer as geskakelde lyste. Daar is natuurlik ander maniere om dit te implementeer as well. Basies die rede waarom ons sou gebruik stapels is om data in so 'n manier te handhaaf dat die mees onlangs bygevoeg element is die eerste ding wat ons gaan wil terug te kry. Ek is Doug Lloyd, dit is cs50.