DOUG LLOYD: Molt bé, així que en aquest punt estàs probablement bastant familiaritzat amb matrius i llistes enllaçades que és el de dos primària estructures de dades que hem parlat de mantenir conjunts de dades de tipus de dades similars organitzada. Ara anem a parlar voltant d'un parell de variacions en matrius i llistes enllaçades. En aquest vídeo anem per parlar de les piles. En concret parlarem sobre una estructura de dades anomenada una pila. Recordeu que en els debats anteriors sobre els punters i memòria, que la pila és també el nomenar per a un segment de la memòria on declara estàticament memòria memory-- que nom, variables que vostè nom, et marcs cetera i funció que també existeixen marcs de pila de trucades. Així que aquesta és una estructura de dades de la pila no és un segment de pila de la memòria. D'ACORD. 

Però, ¿què és una pila? Així que és pràcticament només una tipus especial d'estructura que manté les dades d'una manera organitzada. I hi ha dues molt formes comunes d'implementar piles utilitzant dues estructures de dades que ja estem familiaritzats, matrius i llistes enllaçades. Què fa un especial de pila és el manera en què posem la informació a la pila, i la forma en què eliminar la informació de la pila. En particular amb les piles la regla és només el més recentment element afegit es pot treure. 

Així que pensar-hi com si fos una pila. Estem acumulant informació a la part superior de la mateixa, i només la cosa a la part superior de la pila es pot treure. No podem treure la cosa sota perquè tota la resta ho faria col·lapsar i caure. Així que realment estem construint una pila que llavors hem d'eliminar peça per peça. A causa d'això ens referim comunament a una pila com una estructura LIFO, últim en entrar, primer en sortir. LIFO, últim en entrar, primer a sortir. 

Així que a causa d'aquesta restricció en com la informació pot ser afegit a i retirat d'una pila, no hi ha realment només dues coses que poden fer amb una pila. Podem empènyer, que és el terme que fem servir per afegir un nou element a la part superior de la pila, o si la pila no existeix i estem creant des de zero, la creació de la pila en el primer lloc seria empènyer. I a continuació, el pop, que és el tipus de CS terme que fem servir per treure el més recent element afegit des de la part superior de la pila. 

Així que anem a mirar a tots dos implementacions, basat tant array i llista enllaçada amb base. I anem a començar amb matriu basada. Així que aquí està la idea bàsica del que l'estructura de dades basada en pila de conjunts es veuria així. Tenim una definició mecanografiada aquí. A l'interior de la qual tenim dos membres o camps de l'estructura. Tenim una matriu. I una altra vegada estic fent servir el valor de tipus de dades arbitraris. 

Així que aquest podria ser qualsevol tipus de dades, int carbó o alguna altra dada escriu que ha creat anteriorment. Així que tenim una gran varietat de capacitat de mida. Capacitat de ser una lliura defineix constant, potser en un altre lloc al nostre arxiu. Així que ja compta amb aquest particular aplicació estem delimitador nosaltres mateixos com era normalment en el cas d'arrays, que no podem canviar la mida de forma dinàmica, on hi ha un cert nombre d'elements màxima que podem posar a la nostra pila. En aquest cas es tracta d'elements de capacitat. 

També mantenim un registre de la part superior de la pila. Quin element és el més en data recent a la pila? I així fem un seguiment que en una variable anomenada superior. I tot això s'embolica junts en un nou tipus de dades anomenat una pila. I una vegada que vam ser creats aquest nou tipus de dades podem tractar-ho com qualsevol altre tipus de dades. Podem declarar pila s, igual que podríem fer int x, o de carbó i. I quan diem apilem s, així el que succeeix està obtenim un conjunt de de memòria reservat per a nosaltres. 

En aquest cas, la capacitat Pel que sembla, he decidit és 10 perquè tinc un única variable de tipus pila que conté dos camps recorden. Una matriu, en aquest cas va ser una matriu d'enters com és el cas en la majoria dels meus exemples. I una altra variable sencera capaç d'emmagatzemar la part superior, més recentment afegit element a la pila. Així que una sola pila del que només s'assembla a aquesta definit. És una caixa que conté una sèrie de 10 ho seran nombres enters en aquest cas, i una altra variable sencera allà en verd per indicar la part superior de la pila. 

Per establir la part superior de la pila només diem s.top. Aquesta és la forma en què accedim a una camp d'una estructura de retir. s.top és igual a 0 eficaçment Fa això a la nostra pila. Així que de nou tenim dues operacions que podem dur a terme ara. Podem empènyer i podem pop. Anem a començar amb empenta. Un cop més, empenyent és l'addició d'un nou element a la part superior de la pila. 

Llavors, què fem el que necessitem fer en aquesta matriu d'implementació basada? Bé en general la funció d'empenta es va a haver de acceptar una punter a la pila. Ara pren-te un segon i pensar-hi. Per què voldríem acceptar un punter a la pila? Recordeu que en els vídeos anteriors sobre abast i punters variables, ¿Què passaria si ens enviem pila, s en lloc de com un paràmetre? El que en realitat es va passar aquí? Recordeu que estem creant una còpia quan es passa a una funció llevat que utilitzem punters. I així aquesta funció empènyer necessitats per acceptar un punter a la pila pel que en realitat estem canviant la pila tenim la intenció de canviar. 

L'altra cosa empenta probablement vol acceptar és un element de dades de valor de tipus. En aquest cas, de nou, un nombre enter que anem a afegir a la part superior de la pila. Així que tenim els nostres dos paràmetres. Què farem ara fer dins d'empenta? Bé, simplement, només anem a afegir aquest element a la part superior de la pila i després canviar a la part superior de la pila és, que s dot valor superior. Així que això és el que una funció declaració d'empenta podria semblar en un basada en arranjaments d'implementació. 

De nou, això no és una regla dura i ràpida que podria canviar això i tenir que varien en diferents maneres. Potser s es declara globalment. I pel que ni tan sols cal passar és com un paràmetre. Això és de nou només una cas general per empènyer. I hi ha diferents maneres de posar-ho en pràctica. Però en aquest cas la nostra empenta va a prendre dos arguments, un punter a una pila i un element de dades de valor de tipus, nombre enter en aquest cas. 

Així que vam declarar s, ens va dir s.top és igual a 0. Ara anem a empènyer el el número 28 a la pila. Bé, què vol dir això? Bé actualment la part superior de la pila és 0. I així, el que és, bàsicament, passarà és anem a enganxar el nombre 28 en la ubicació array 0. Bastant senzill, correcte, que era la part superior i ara som bons per anar. I llavors hem de canviar el que la part superior de la pila ha de ser. Així que la propera vegada empenyem un element, anem a guardar-lo en ubicació array, probablement no 0. No volem sobreescriure el que acabem de posar allà. I així només haurem de moure la part superior a 1. Això probablement té sentit. 

Ara bé, si volem posar un altre element a la pila, diem que volem empènyer 33, Bé, ara només anem a prendre 33 i el va posar al nombre d'ubicació de matriu 1, i després canviar la part superior de la nostra apilar ser ubicació matriu número dos. Així que si la propera vegada que volem empènyer un element a la pila, que va ser posat en un lloc matriu 2. I farem això un cop més. Ens empenyem 19 fora de les piles. Anem a posar 19 a la localització matriu 2 i canviar la part superior de la nostra pila ser ubicació matriu 3 per la qual cosa si la propera vegada que anem de que hagi de fer un esforç que estem bé per anar. 

OK, així que això és empènyer en poques paraules. Què hi ha d'esclatar? Així que fa esclatar és el tipus de contrapartida a empènyer. És la forma en què ens vam treure les dades de la pila. I en pop necessitats generals a fer el següent. Es necessita acceptar un punter a la apilar, de nou en el cas general. En un altre cas, vostè pot ser han declarat la pila a nivell mundial, en aquest cas no és necessari per passar-ho a perquè ja té accés a la mateixa com una variable global. Però llavors què més hem de fer? Bé ens incrementant la part superior de la pila en empenta, així que estem probablement voldrà per disminuir la part superior de la pila en el pop, no? I després, per descomptat, també anem a voler per tornar el valor que eliminem. Si estem afegint elements, volem per obtenir elements a terme més endavant, és probable que en realitat voler guardar així que no simplement eliminar-los de la apilar i després no fer res amb ells. Generalment si som empenyent i fent esclatar aquí volem emmagatzemar aquesta la informació d'una manera significativa i pel que no fa sentit simplement descartar-ho. Així que aquesta funció ha de probablement retornar un valor per a nosaltres. 

Així que això és el que una declaració de pop podria semblar que hi ha a la part superior esquerra. Aquesta funció retorna les dades de valor de tipus. Una vegada que hem estat utilitzant sencers llarg. I accepta un punter a una pila com el seu únic argument o paràmetre únic. Llavors, què és el pop va a fer? Diguem que volem ara pop un element fora de s. Llavors recordo que vaig dir que les piles estan última In, First Out, estructures de dades LIFO. Quin element es va a ser retirat de la pila? Sabia vostè endevina 19? Perquè estaríem en la veritat. 19 va ser l'últim element que afegim a la apilar quan estàvem empenyent elements en, i pel que va a la primera element que aconsegueix tret. És com si diguéssim 28, i a continuació, posem 33 a la part superior de la mateixa, i vam posar 19 per sobre d'això. L'únic element que podem treure és 19. 

Ara al diagrama aquí el que he fet és una espècie d'esborrat 19 de la matriu. Això no és realitat el que farem. Només anem a classe de pretendre que no hi és. És encara allà a aquesta ubicació de memòria, però només anem a ignorar canviant la part superior de la nostra pila de ser 3 a 2. Així que si haguéssim de ara empènyer un altre element a la pila, seria més d'escriure 19. 

Però no cal passar per la molèstia 19 de eliminar-lo de la pila. Només podem pretendre que no hi és. A l'efecte de la pila que s'ha anat si canviem la part superior per ser 2 en lloc de 3. Molt bé, així que això va ser més o menys la mateixa. Això és tot el que necessitem fer perquè aparegui un element fora. Anem a fer-ho de nou. Així que he destacat en vermell per indiquem que estem fent una altra trucada. Anem a fer el mateix. 

Llavors, què passarà? Bé, anem a emmagatzemar 33 en x i anem per canviar la part superior de la pila a 1. Així que si fóssim ara per empènyer un element a la pila que estem farem en aquest moment, el que va a succeir Som nosaltres anem sobreescriptura ubicació matriu número 1. Així que el 33 que va ser una espècie d'esquerra darrere que acabem fingim ¿No hi ha més, només estem anant per donar-li una pallissa i posar 40 al seu lloc. I després, per descomptat, des que vam fer una empenta, incrementarem el superior de la pila 1-2 de manera que si ara afegim un altre element que va a anar a la ubicació matriu número dos. 

Ara llistes enllaçades són una altra manera d'implementar les piles. I si aquesta definició al pantalla d'aquí sembla familiar a vostè, és perquè es veu gairebé exactament de la mateixa, de fet, que pràcticament és exactament el mateix que una llista enllaçada, si vostè recorda de la nostra discussió de simplement enllaçada llistes en un altre vídeo. L'única restricció aquí és per a nosaltres com a programadors, que no se'ns permet inserir o eliminar atzar de la llista simplement enllaçada que podríem fer amb anterioritat. Podem només ara inserir i eliminar de el front o la part superior de l'vinculats llista. Això és realment l'única diferència però. Això és el contrari d'una llista enllaçada. No és més que la restricció reemplaçant en nosaltres mateixos com programadors que canvia en una pila. 

La regla aquí és mantenir sempre una punter al capdavant d'una llista enllaçada. Això és per suposat un general regla important primer. Per separat llista enllaçada de totes maneres Només cal un punter al capdavant amb la finalitat de tenir aquesta cadena de poder referir- per a tots els altres elements en la llista enllaçada. Però és sobretot important amb una pila. I així, en general, vostè és va a realment vol aquest punter a una variable global. Probablement va serà encara més fàcil d'aquesta manera. Quins són els anàlegs d'empenta i el pop? Dreta. Així empenyent de nou és l'addició de un nou element a la pila. En una llista enllaçada que vol dir que tindrem per crear un nou node que estem va afegir a la llista enllaçada, i després seguiu els passos curosos que hem esbossat anteriorment en les llistes lligades senzilles per afegir-lo a la cadena sense trencar la cadena i perdre o orfes qualsevol elements de la llista enllaçada. I això és bàsicament el que petita bombolla de text allà resumeix. I anem a fer una ullada en ell com un diagrama. 

Així que aquí està la nostra llista enllaçada. És al mateix temps conté quatre elements. I més perfectament aquí està la nostra apilar conté quatre elements. I diguem que ara volem impulsar un nou element en aquesta pila. I volem impulsar una nova element el valor és 12. Bé, què farem? Bé primer que anem a espai malloc, dinàmicament assignar espai per a un nou node. I, per descomptat, immediatament després fem una crida a malloc sempre vos de comprovar nul·la, perquè si arribem nul·la volta hi havia algun tipus de problema. No volem eliminar la referència que nul·la punter o que patiran una fallada seg. Això no és bo. Per a això hem malloced del node. Anem a suposar que hem tingut èxit aquí. Anem a posar 12 a el camp de dades de dit node. Ara Què recordes quin dels nostres punters Mou següent, així que no trenquem la cadena? Tenim un parell d'opcions aquí, però l'únic que va a estar fora de perill és establir notícies proper punter a punt a la vella cap de llista o el que aviat serà el antic cap de la llista. I ara que tot el nostre elements estan encadenats junts, només podem moure la llista d'assenyalar al mateix lloc que el nou fa. I ara hem portat efectivament una nou element en la part frontal de la pila. 

Per aparèixer només volem esborrar aquest primer element. I així que bàsicament el que hem de fer aquí, així que hem de trobar el segon element. Amb el temps que es convertirà en el nou cap després esborrem la primera. Així que només hem de començar des Al principi, moure un avanç. Una vegada que tenim un celler en un endavant d'on estem actualment som podem eliminar la primera d'elles amb seguretat i després ens podem moure el cap per apuntar-se al que va ser el segon mandat i llavors ara és el primer després d'això node ha estat eliminat. 

Així que de nou, fent una ullada en ell com un diagrama que volen ara un element element fora d'aquesta pila. Llavors, què fem? Bé estem primer crearà un nou punter que està passant per assenyalar el mateix lloc que el cap. Anem a moure-una posició cap endavant dient iguals trav trav proper per exemple, que avançaria el punter trav un sol posició avançada. Ara que tenim un mantenir-se en el primer element a través de la llista de punters cridat, i la segon element a través d'un punter anomenat trav, podem eliminar amb seguretat que primer element de la pila sense perdre la resta de la cadena perquè tenir una manera de referir al segon element reenviar a través de la punter anomenat trav. 

Així que ara podem alliberar aquest node. Podem alliberar llista. I llavors tot el que necessitem fer ara és moure la llista a punt al mateix lloc que trav fa, i estem espècie de tornada on vam començar abans empenyem 12 en en el primer lloc, a la dreta. Això és exactament on érem. Hem tingut aquest quatre elements de la pila. Hem afegit un cinquè. Empenyem un cinquè element, i després ens aparegut recentment que la majoria element afegit de marxa enrere. 

Això és realment més o menys tot el que hi ha a piles. Es pot implementar com matrius. Es pot implementar com llistes enllaçades. Hi ha, per descomptat, una altra formes de posar-les en pràctica també. Bàsicament, la raó per la qual usaríem piles és mantenir les dades de tal manera que el més recentment afegit element és el primer que estem voldrà tornar. Sóc Doug Lloyd, això és CS50.