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.