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.