DOUG LLOYD: Bone, tiel per tiu punkto vi estas
verŝajne bela familiara kun tabeloj kaj ligitaj listoj
kiu estas la du primaraj datumstrukturoj ni havas
parolis por konservanta aroj de datumoj de simila datumtipoj organizita.
>> Nun ni iras por paroli pri kelkaj variadoj
sur tabeloj kaj ligitaj listoj.
En ĉi tiu video ni iras paroli pri stakoj.
Specife ni tuj paroli pri datumstrukturo nomata stako.
Revokon de antaŭaj diskutoj pri punteros kaj memoro,
ke la pilo estas ankaŭ la nomo por segmento de memoro
kie statike deklaris memory-- memoro kiun vi
citi, variabloj kiujn vi nomas, et cetera kaj funkcio kadroj kiujn ni ankaux
alvoko pilo kadroj ekzistas.
Do tiu estas pilo datumstrukturo Ne stako segmento de memoro.
BONE.
>> Sed kio estas stako?
Do estas preskaux nur Speciala speco de strukturo
kiu subtenas datumoj en organizita maniero.
Kaj estas du tre komunaj manieroj efektivigi
stakigas uzante du datumstrukturoj ke ni estas jam konata kun,
arrays kaj ligitaj listoj.
Kio faras speciala estas la pilo maniero en kiu ni metas informo
en la pilo, kaj la maniero ni forigi informojn el la stako.
Aparte kun stakoj la regulo estas nur la plej
ĵus aldonita elemento povas esti forigitaj.
>> Do pensu pri ĝi kvazaŭ ĝi estas pilo.
Ni amasiĝas informo aldone mem,
kaj nur la afero ĉe la supro de la stako povas esti forigitaj.
Ni ne povas forigi la aferon sub ĉar ĉio alia volus
kolapsi kaj fali super.
Do ni vere konstruas stako ke ni tiam devas forigi pecon post peco.
Pro tio ni komune raporti al stako kiel LIFO strukturo,
daŭri en, unua el.
LIFO, daŭri en, unua el.
>> Do pro tiu limigo sur kiom informo povas esti aldonita
kaj forigis el stako, estas vere nur du aferoj ni povas fari kun stako.
Ni povas puŝi, kiu estas la terminon ni uzu por aldonanta
nova elemento al la supro de la pilo, aŭ se la pilo ne ekzistas
kaj ni kreas ĝin de nulo, kreante la stako en la unua loko
estus puŝas.
Kaj tiam krevas, jen la speco de CS terminon ni uzu por forigi la plej laste
aldonis elemento de la supro de la stako.
>> Do ni tuj rigardi ambaŭ implementaciones, ambaŭ bazitaj tabelo
kaj ligillisto bazita.
Kaj ni tuj starti kun tabelo bazita.
Do jen la baza ideo de kio la tabelo bazita stako datumstrukturo
aspektus.
Ni havas tajpita difino tie.
Ene de tiu ni havas du membroj aŭ kampoj de la strukturo.
Ni havas tabelo.
Kaj denove mi uzas la arbitra datumtipo valoro.
>> Do tiu povus esti ajna datumtipo, int char aŭ alian datumon
tajpu vi antaŭe kreitaj.
Do ni havas aron de grandeco kapablo.
Kapablo estanta funton difinita konstanto, eble aliloken en nia dosiero.
Do rimarki jam kun tiu aparta efektivigo ni saltadi
nin kiel estis tipe la kazo kun sensilo,
kiun ni ne povas dinamike regrandigi, kie estas tute certa nombro
de elementoj maksimuma ke ni povas meti en nia stako.
En tiu kazo ĝi estas kapablo elementoj.
>> Ni ankaŭ sekvigi la supro de la stako.
Kio elemento estas la plej ĵus aldonita al la pilo?
Kaj tiel ni sekvigi ke en variablo nomata pinto.
Kaj ĉio ĉi gets enpakita kune en novan datumtipo nomata stako.
Kaj unufoje ni kreis tiu nova datumtipo
ni povas trakti ĝin kiel ajna alia datumtipo.
Ni povas deklari pilo j, samkiel ni povus fari int x, aŭ char y.
Kaj kiam ni diras pilo s, bone kio okazas
Estas ni akiras aron de memoro flankenmetis por ni.
>> Tiukaze kapablo Mi ŝajne decidis
Estas 10 ĉar mi havas sola variablo de tipo pilo
kiu enhavas du kampojn memoras.
Tabelo, tiukaze tuj estos tabelo de entjeroj
kiel estas la kazo en la plej multaj el miaj ekzemploj.
Kaj alia entjera variablo kapabla de stoki la supro,
la plej ĵuse aldonita elemento al la stako.
Do unu ununura stako de kion ni nur difinita aspektas kiel ĉi.
Estas skatolo enhavanta tabelo de 10 kion
Estos entjeroj en tiu kazo kaj alia entjera variablo tie en verda
indiki la supro de la stako.
>> Por agordi la supro de la pilo ni nur diru s.top.
Tiel estas kiel ni aliras al kampo de strukturo revokon.
s.top egalas 0 efike faras tion por nia stako.
Do denove ni havas du operacioj ke ni povas elfari nun.
Ni povas puŝi kaj ni povas krevi.
Komencu kun puŝo.
Denove, puŝante estas aldonanta novajn elemento al la supro de la stako.
>> Do kion ni devas fari en tiu tabelo bazita efektivigo?
Nu ĝenerale la puŝo funkcio tuj
bezonas akcepti sagon al la stako.
Nun prenu la duan kaj pensi pri ĝi.
Kial ni volas akcepti montrilo al la pilo?
Revokon de antaŭaj videos en ŝanĝiĝema amplekso kaj punteros,
kio okazus se ni ĵus sendis pilo, s prefere en kiel parametro?
Kio devus reale esti pasis en tie?
Memoru ni kreas kopion kiam ni pasas ŝin al funkcio
krom se ni uzas punteros.
Kaj do ĉi tiu funkcio puŝi bezonoj akcepti puntero al la stako
por ke ni vere ŝanĝi la stako ni intencas ŝanĝi.
>> La alia afero puŝo probable volas akcepti estas datumo elemento de tipo valoro.
En tiu kazo, denove, entjero ke Ni tuj aldonos al la supro de stako.
Do ni havas nian du parametrojn.
Kio estas ni iranta nun fari ene de puŝo?
Nu, simple, ni ĵus tuj aldoni ke elemento al la supro de la stako
kaj tiam ŝanĝu kie la supro de la pilo estas, ke s dot supro valoro.
Do jen kion funkcio deklaro por puŝo
povus rigardi kiel en tabelo-bazita efektivigo.
>> Denove ĉi tiu ne estas malmola kaj rapida regulo ke vi povus ŝanĝi tion kaj havas
ĝi varias en malsamaj manieroj.
Eble s estas deklarita tutmonde.
Kaj tial vi eĉ ne bezonas pasi ĝin kiel parametro.
Jen denove nur ĝenerala kazo por puŝo.
Kaj ekzistas diverseco manierojn por apliki ĝin.
Sed tiukaze nia puŝo tuj prenos
du argumentoj, puntero al stako kaj datuma elemento de tipo valoro, entjero
en tiu kazo.
>> Do ni deklaris s, ni diris s.top egalas 0.
Nun ni puŝi la numero 28 sur la pilo.
Nu kion tio signifas?
Nu nuntempe la pinto de la stako estas 0.
Do kio estas esence okazos estas
ni tuj algluita la nombro 28 en tabelo ĉelo 0.
Bela simpla, justa, ke estis la supro kaj nun ni estas bone iri.
Kaj tiam ni bezonas ŝanĝi kion la supro de la stako estos.
Por ke la venontan fojon ni puŝi ero en,
ni iras por stoki ĝin en tabelo situon, probable ne 0.
Ni ne volas anstataŭigi kion ni ĵus metis tie.
Kaj tiel ni simple movi la supro al 1.
Ke probable havas sencon.
>> Nun se ni volas meti alia elemento sur la pilo, ke ni volas puŝi 33,
bone nun ni nur tuj prenos 33 kaj metis gxin antaux tabelo situon nombro
1, kaj tiam ŝanĝi la supro de nia pilo esti tabelo situon numero du.
Do se la sekva tempo ni volas puŝi ero sur la pilo,
ĝi devos esti metita en tabelo 2 situon.
Kaj ni faru ke unu pli fojon.
Ni puŝas 19 for de la stakoj.
Ni metos 19 en tabelo situon 2 kaj ŝanĝi la supro de nia stako
esti tabelo situon 3 do se la sekva tempo ni
bezonos fari puŝo ni estas bone iri.
>> OK, Do jen puŝante en malmultaj vortoj.
Kio pri krevanta?
Do popping estas la speco de contraparte al puŝanta.
Ĝi estas kiel ni forigi datumojn de la stako.
Kaj ĝenerale popo bezonoj fari la sekvan.
Ĝi bezonas akcepti puntero al la pilo, denove en la ĝenerala kazo.
En iuj aliaj kazo vi povus deklaris la stako tutmonde,
en kiu kazo vi ne bezonas por pasi ĝin en ĉar ĝi jam havas aliron al ĝi
kiel tutmonda variablo.
Sed tiam kion alian ni devas fari?
Nu ni pliigante la supro de la stako en puŝo,
do ni probable tuj volas al dekremento la supro de la stako
en popmuziko, dekstra?
Kaj tiam kompreneble ni ankaŭ tuj volas
redoni la valoron ke ni forigu.
Se ni aldonas elementojn, ni volas akiri elementojn el pli poste,
ni probable reale volas konservi ilin tiel ni
ne nur forigi ilin de la pilo kaj tiam fari nenion kun ili.
Ĝenerale, se ni estos puŝanta kaj krevanta ĉi tie
ni volas konservi tiun informo en signfa vojo
kaj do ĝi ne faros sencon nur forĵeti ŝin.
Do tiu funkcio devas verŝajne resendas valoron por ni.
>> Do jen kion deklaro por popmuziko povus aspekti tie supre maldekstre.
Tiu funkcio redonas datumoj de tipo valoro.
Denove ni estis uzante entjeroj dum.
Kaj ŝi akceptas puntero al stako kiel ĝia sola argumento aŭ soleo parametro.
Do kio estas popmuziko faros?
Supozu ke ni volas nun pop elementon de de s.
Do memoru Mi diris ke stakoj estas lastaj en, unue eksteren, LIFO datumstrukturoj.
Kiu elemento tuj esti forigita de la stako?
Ĉu vi povas diveni 19?
Ĉar vi estus prava.
19 estis la lasta elemento ni aldonis al la pilo kiam ni puŝas elementoj sur,
kaj tiel ĝi tuj la unua elemento kiu akiras forigita.
Estas kvazaŭ ni diris 28, kaj tiam ni metis 33 sur supro,
kaj ni metis 19 Aldonigxis.
La sola elemento ni povas despegar estas 19.
>> Nun en la diagramo ĉi tie kion mi faris estas ia forviŝita 19 de la tabelo.
Tio ne reale kion ni tuj faros.
Ni nur tuj speco de ŝajnigi ke gxi mankas.
Ĝi estas ankoraŭ tie en tiu memoro loko,
sed ni simple tuj ignori ĝin ŝanĝante la supro de nia stako
plu 3 al 2.
Do se ni nun puŝi alia elemento sur la pilo,
estus super skribi 19.
>> Sed ni ne iros tra la problemo forigi 19 de la stako.
Ni povas simple ŝajnigi ke gxi mankas.
Por celoj de la stako ĝi estas irita se ni ŝanĝas la supron esti 2 anstataŭ 3.
Bone, tiel ke estis bele multe ĝi.
Jen ĉio ni devas fari krevi ero de.
Ni faru tion denove.
Do mi reliefigis ĝin en ruĝa tie indiki ni fari alian alvokon.
Ni tuj faros la samon.
>> Do kio okazos?
Nu, ni tuj stoki 33 en x kaj ni tuj
ŝanĝi la supro de la stako al 1.
Tiel ke se ni nun al peli elemento en la stako kiu ni estas
faros nun, kio okazos
Estas ni iras anstataŭigi tabelo situon numero 1.
Tiel ke 33 ke estis speco de maldekstra malantaŭ ni nur ŝajnigis
ne ekzistas plu, ni ĵus tuj al clobber ĝin kaj metis 40 tie anstataŭe.
Kaj tiam kompreneble ĉar ni faris puŝon,
ni tuj pliigo la pinto de la stako de 1 al 2
tiel ke se ni nun aldonu alia elemento ĝi malebligos
iri en tabelo situon numero du.
>> Nun ligitaj listoj estas alia maniero implementar stakoj.
Kaj se tiu difino sur la ekrano tie aspektas familiaraj al vi,
ĝi estas ĉar ĝi aspektas preskaŭ precize samaj, fakte,
ĝi bele multe estas ekzakte la sama kiel unuope ligillisto,
se vi memoras el nia diskuto de unuope ligitaj listoj en alia video.
La sola limigo ĉi tie estas por ni kiel programistoj,
ni ne rajtas enmeti aŭ forigi hazarde
el la unuope ligita listo kion ni povus fari antaŭe.
Ni povas nur nun enmeti kaj forigi el la fronto aŭ la supro de la ligitaj
lerta.
Tio estas vere la sola diferenco tamen.
Tiu estas alia maniero unuope ligita listo.
Ĝi estas nur la limigo anstataŭante sur nin
kiel programistoj kiuj ŝanĝas ĝin en stako.
>> La regulo ĉi tie estas ĉiam subteni sagon al la kapo de ligitaj listo.
Tiu estas kompreneble ĝenerale grava regulo unue.
Por unuope ligita listo ĉiuokaze vi nur bezonos montrilon al la kapo
por havi tiun ĉeno povos rilati
al ĉiu alia elemento en la ligitaj listo.
Sed estas aparte grava kun stako.
Kaj do ĝenerale vi estas tuj reale volas
ĉi puntero esti tutmonda variablo.
Ĝi estas probable tuj estu plifacile tiel.
Do kio estas la analogoj de puŝo kaj popo?
Dekstra.
Do puŝas denove aldonas nova elemento al la stako.
En ligillisto ke Do oni tuj devas
krei novajn nodo ke ni estas tuj aldoni en la ligillisto,
kaj tiam sekvas la zorgema paŝoj ke ni skizis antaŭe
en unuope ligitaj listoj aldoni ĝin al la ĉeno sen rompi la ĉenon
kaj perdante aŭ orphaning ajnan elementoj de la ligitaj listo.
Kaj tio estas esence kion tio iom blob de teksto tie resumas.
Kaj ni rigardu ĉe ĝi kiel diagramo.
>> Do jen nia ligillisto.
Ĝi samtempe enhavas kvar elementoj.
Kaj pli perfekte jen nia pilo enhavanta kvar elementoj.
Kaj diru ni nun volas puŝi novan eron sur tiu stako.
Kaj ni volas puŝi nova elementon kies datumoj valoro estas 12.
Nu kion ni faros?
Nu unuan ni tuj malloc spaco, dinamike
destini spaco por nova nodo.
Kaj kompreneble tuj post ni faras alvokon al malloc ni ĉiam
certigi por kontroli nula, ĉar se ni akiris nula reen
estis ia problemo.
Ni ne volas dereference ke nula montrilo aŭ vi suferos seg kulpo.
Tio ne bona.
Do ni malloced de la nodo.
Ni supozu ni havis sukceson tie.
Ni tuj metos 12 en la datumoj de kampo de tiu nodo.
Nun cxu vi memoras, kiu el niaj punteros movas sekva tial ni ne rompi la ĉenon?
Ni havas paron de ebloj tie sed la sola kiu tuj estos al savas
estas fiksi novaĵoj sekva puntero punkton al la maljuna kapo de la listo
aŭ kio baldaŭ estos la malnova kapo de la listo.
Kaj nun ke ĉiuj niaj elementoj estas ĉenitaj kune,
ni povas nur movi listo atentigi al la sama loko kiu nova faras.
Kaj ni nun efike puŝis nova elemento sur la fronto de la stako.
>> Krevi ni nur volas forviŝi tiun unuan elementon.
Kaj do esence kion ni devas fari ĉi tie,
bone ni devas trovi la dua elemento.
Eventuale kiu igos la novan kapo post ni forviŝi la unua unu.
Do ni nur devas komenci de la komenco, movi unu antaŭen.
Iam ni trafis sur unu antaŭen de kie ni nuntempe
ni povas forviŝi la unua sekure kaj tiam ni povas nur movi la kapon
atentigi al kio estis la dua oficperiodo kaj tiam nun
estas la unua post tiu nodo estis forigita.
>> Do denove, prenante rigardu ĉe ĝi kiel diagramo ni
volas nun pop an elementon de de tiu stako.
Do kion ni faru?
Nu ni unue tuj kreos nova puntero ke tuj
atentigi al la sama loko kiel la kapo.
Ni tuj movi ĝin unu pozicion antaŭen dirante trav egaluloj
Trav sekva ekzemple, kiu antaŭus la trav montrilo unu
pozicio antaŭen.
Nun ke ni havas tenadi la unua elemento
tra la puntero nomis lerta, kaj la dua elemento tra puntero nomita
trav, ni povas sekure forigi ke unua elemento de la stako
sen perdi la reston de la ĉeno ĉar ni
havi manieron rilati al la dua ero
plusendu tra la puntero nomita trav.
>> Do nun ni povas liberigi tiu nodo.
Ni povas liberigi listo.
Kaj tiam ĉiuj ni devas fari nun estas movi listo atentigi al la sama loko
ke trav faras, kaj ni estas speco de reen kie ni komencis antaŭ ni puŝis 12
sur la unua loko, dekstre.
Tiu estas ĝuste kie ni estis.
Ni havis ĉi kvar elemento pilo.
Ni aldonis kvinan.
Ni puŝis kvina elementon, kaj poste ni
krevita ke plej laste aldonita elemento reen for.
>> Tio estas vere bela multe ĉiuj estas al stakoj.
Vi povas apliki ilin kiel arrays.
Vi povas apliki ilin kiel ligitaj listoj.
Ekzistas, kompreneble, aliaj manierojn apliki ilin ankaŭ.
Esence la kialo ni uzus stakoj estas subteni datumojn tiel
ke la plej ĵuse aldonita elemento estas la unua afero ni estas
tuj volas reiri.
Mi Doug Lloyd, tiu estas CS50.