Doug Lloyd: Tout dwa, sa pa pwen sa a ou se pwobableman bèl yo konnen yo ak ranje e li bay lis lye ki se prensipal la de estrikti done nou te te pale osijè de pou kenbe kouche nan done nan kalite done ki sanble òganize. Koulye a, nou ap ale nan pale sou yon koup la varyasyon sou ranje e li bay lis lye. Nan videyo sa a nou ap ale pale sou pil. Espesyalman nou ap ale nan pale sou yon estrikti done yo te rele yon chemine. Rapèl soti nan diskisyon anvan sou pwent ak memwa, ki chemine a tou a se non pou yon segman nan memwa kote statics deklare memory-- memwa ke ou non, varyab ke ou non, ak setra ak fonksyon ankadreman ki nou menm tou nou ankadreman chemine apèl egziste. Se konsa, sa a se yon estrikti done chemine pa yon segman pil nan memwa. OK. 

Men, sa ki se yon chemine? Se konsa, li bèl anpil jis yon kalite espesyal nan estrikti ki konsève done nan yon fason òganize. Apre sa, nan de trè fason komen nan aplike pil lè l sèvi avèk de estrikti done ke nou ap deja abitye ak, ranje e li bay lis lye. Ki sa ki fè yon espesyal pil se nan fason nan ki nou mete enfòmasyon nan chemine a, ak fason nou retire enfòmasyon ki soti nan pil la. An patikilye ak pil règ la se sèlman pi plis nan dènyèman te ajoute eleman ka dwe retire li. 

Se konsa, panse osijè de li kòm si li nan yon pil. Nou ap anpile enfòmasyon sou tèt tèt li, epi sèlman bagay la nan tèt la nan pil la, ou ka wete. Nou pa ka retire bagay la anba paske tout lòt bagay ta tonbe ak tonbe sou. Se konsa, nou vrèman ap bati yon pil ki nou Lè sa a gen yo retire moso pa moso. Paske nan sa a nou souvan, al gade nan yon chemine kòm yon estrikti LIFO, dire nan, premye deyò. LIFO, dire an, premye deyò. 

Se konsa, paske nan restriksyon sa a sou ki jan yo kapab enfòmasyon dwe ajoute nan ak yo retire nan yon pil, gen nan reyèlman sèlman de bagay nou kapab fè avèk yon pil. Nou ka pouse, ki se nan tèm nou itilize pou ajoute yon eleman nouvo nan tèt la nan la pile, oswa si chemine a pa egziste epi nou ap kreye li nan grate, kreye chemine a an plas an premye ta dwe pouse. Lè sa a, pòp, sa se sòt nan nan CS tèm nou itilize yo retire pi resamman an te ajoute eleman soti nan tèt la nan chemine a. 

Se konsa, nou ap ale nan gade nan tou de en, tou de etalaj ki baze ak lis lye baze sou. Epi nou ap ale nan kòmanse ak etalaj ki baze sou. Se konsa, isit la nan lide a debaz nan sa ki etalaj ki baze estrikti nan done chemine ta sanble. Nou gen yon definisyon tape isit la. Anndan nan ke nou gen de manm oswa jaden nan estrikti an. Nou gen yon etalaj. Epi ankò m ap lè l sèvi avèk la abitrè kalite done valè. 

Se konsa, sa a ta ka nenpòt ki kalite done, Char int oswa kèk lòt done tape deja ou te kreye. Se konsa, nou gen yon etalaj de kapasite gwosè. Kapasite yo te yon liv defini konstan, petèt yon lòt kote nan dosye nou yo. Se konsa, remake deja ak sa a an patikilye aplikasyon nou ap espasyal tèt nou jan sa te tipikman ka a ak ranje, ki nou pa ka dynamique rdimansyonman, kote gen nan yon nimewo sèten nan eleman maksimòm ki nou ka mete nan chemine nou an. Nan ka sa a li nan eleman kapasite. 

Nou menm tou nou kenbe tras nan tèt la nan chemine a. Ki sa ki eleman ki pi an dènyèman te ajoute nan chemine a? Se konsa, nou kenbe tras nan ki nan yon varyab rele tèt. Apre sa, tout bagay sa yo vin vlope moute ansanm nan yon nouvo kalite done yo rele yon pil. Ak yon lòt fwa nou ap kreye sa a nouvo kalite done nou ka trete li tankou nenpòt lòt done kalite. Nou ka deklare chemine a, jis tankou nou ta ka fè int x, oswa Char y. Lè nou di pile a, byen sa k ap pase se nou jwenn yon seri memwa mete sou kote pou nou. 

Nan ka sa a kapasite Mwen te aparamman deside se 10 paske mwen te gen yon sèl varyab nan kalite chemine ki gen de jaden sonje. Yon etalaj, nan ka sa a ki pral yo dwe yon etalaj de nonm antye relatif kòm se ka a nan pi fò nan egzanp mwen. Ak yon lòt varyab nonb antye relatif ki kapab estoke tèt la, pi resamman te ajoute nan eleman pil la. Se konsa, yon sèl pil nan sa nou jis defini sanble tankou sa a. Li se yon ti bwat ki gen yon etalaj de 10 sa yo pral nonm antye relatif nan ka sa a ak yon lòt varyab nonb antye relatif gen la nan vèt ki endike tèt la nan chemine a. 

Yo mete tèt yo nan la chemine nou jis di s.top. Sa a ki jan nou gen aksè a yon jaden nan yon estrikti rapèl. s.top egal 0 efektivman fè sa a chemine nou an. Se konsa, ankò nou gen de operasyon ke nou ka fè kounye a. Nou ka pouse epi nou ka pòp. Ann kòmanse ak pouse. Yon fwa ankò, pouse se ajoute yon nouvo eleman nan tèt la nan chemine a. 

Se konsa, sa nou bezwen fè nan sa a etalaj ki baze aplikasyon? Byen nan an jeneral fonksyon ki pral pouse nan bezwen aksepte yon konsèy nan pil la. Koulye a, pran yon dezyèm epi reflechi sou li. Poukisa nou ta vle aksepte yon konsèy nan chemine a? Rapèl soti nan videyo anvan sou varyab dimansyon ak endikasyon, sa ki ta rive si nou jis voye chemine, s olye nan kòm yon paramèt? Ki sa ki ta aktyèlman ap pase nan genyen? Sonje nou ap kreye yon kopi lè nou pase l bay yon fonksyon sof si nou itilize endikasyon. Se konsa, fonksyon sa a pouse bezwen aksepte yon konsèy nan chemine a pou nou ap aktyèlman chanje chemine a nou gen entansyon chanje. 

Lòt pouse nan bagay pwobableman vle aksepte se yon eleman done ki gen valè kalite. Nan ka sa a, ankò, yon nonb antye relatif ki nou ap ale nan ajoute nan tèt la nan chemine. Se konsa, nou te gen de paramèt nou an. Ki sa yo nou pral kounye a fè andedan nan pouse? Oke, tou senpleman, nou ap jis ale nan ajoute ki eleman nan tèt la nan chemine a ak Lè sa a chanje kote tèt la nan chemine a se, ki s dot tèt valè. Se konsa, sa a se sa yon fonksyon deklarasyon pou pouse ta ka sanble nan yon etalaj ki baze sou aplikasyon. 

Yon lòt fwa ankò sa a se pa yon règ fò e rapid ke ou ta ka chanje sa a epi yo gen li varye nan diferan fason. Petèt a se te deklare globalman. Se konsa, ou pa menm bezwen yo pase li se kòm yon paramèt. Sa a se ankò jis yon ka jeneral pou pouse. E genyen anpil diferan fason yo aplike li. Men, nan ka sa a nou an pouse se pral pran de agiman, yon konsèy nan yon pil ak yon eleman done ki gen valè kalite, nonb antye ki pè nan ka sa. 

Se konsa, nou te deklare a, nou di s.top egal 0. Koulye a, kite a pouse nan Nimewo 28 sou pil la. Oke ki sa sa vle di? Oke kounye a nan tèt nan chemine a se 0. Se konsa, sa ki nan fondamantalman pral rive se nou ap ale nan bwa nimewo a 28 nan etalaj kote 0. Trè dwat, dwa, ki te tèt la e kounye a, nou ap bon yo ale. Lè sa a, nou bezwen chanje sa tèt la nan chemine a yo pral. Se konsa, tan sa a nan pwochen te nou pouse yon eleman an, nou ap ale nan magazen li nan etalaj kote, pwobableman pa 0. Nou pa vle recouvrir ki sa nou jis mete ladan l '. Se konsa, nou pral jis deplase tèt la nan 1. Sa pwobableman fè sans. 

Koulye a, si nou vle mete yon lòt eleman sou chemine a, di nou vle pouse 33, byen kounye a nou ap jis pral pran 33 li mete l 'nan nimewo kote etalaj 1, ak Lè sa a chanje tèt la nan nou an pile yo dwe nimewo kote etalaj de. Se konsa, si lè a pwochen nou vle pouse yon eleman sou chemine a, li pral dwe mete nan etalaj kote 2. Li kite yo fè sa yon lòt fwa ankò. Nou pral pouse 19 koupe nan pil yo. Nou pral mete 19 nan etalaj kote 2 ak chanje tèt la nan chemine nou an yo dwe etalaj kote 3 Se konsa, si pwochen nou nan tan bezwen fè yon pouse nou ap bon yo ale. 

OK, se konsa ki nan pouse nan yon Nutshell. Ki sa ki sou eklate? Se konsa, eklate se sòt nan nan kontrepati pouse. Li nan ki jan nou retire done ki sòti nan chemine a. Ak nan bezwen pòp jeneral fè sa ki annapre yo. Li bezwen yo aksepte yon konsèy nan la pile, ankò nan ka la an jeneral. Nan kèk lòt ka ou ta ka yo te deklare chemine a globalman, nan ka sa a ou pa bezwen pase l nan paske li deja gen aksè a li kòm yon varyab mondyal la. Men, Lè sa ki lòt bagay nou bezwen fè? Oke nou te incrementing tèt la nan chemine a nan pouse, se konsa nou ap pwobableman ale nan vle dekrwasans tèt la nan chemine a nan pòp, dwa? Lè sa a, nan kou nou ap tou ale nan vle retounen valè a ke nou retire. Si nou ap ajoute eleman, nou vle yo ka resevwa eleman soti pita sou li a, nou pwobableman aktyèlman vle nan magazen yo se konsa nou pa sèlman efase yo soti nan la pile ak Lè sa a pa fè anyen ak yo. Anjeneral si nou ap pouse ak eklate isit la nou vle nan magazen sa a enfòmasyon ki nan yon fason siyifikatif e konsa li pa fè sans nan jis jete li. Se konsa, sa a ta dwe fonksyon pwobableman retounen yon valè yo ban nou. 

Se konsa, sa a se sa yon deklarasyon pou pòp ta ka sanble gen nan bò gòch an tèt la. Sa a retounen fonksyon done ki gen valè kalite. Yon fwa ankò nou te te lè l sèvi avèk nonm antye relatif nan tout. Epi, se aksepte yon konsèy nan yon pil kòm agiman sèl li yo oswa sèl paramèt. Se konsa, sa se pòp pral fè? Se pou nou di nou vle kounye a pòp yon eleman koupe nan la. Se konsa, sonje mwen te di ke pil yo dènye nan, premye soti, LIFO done estrikti. Ki eleman ki pral ka retire yo nan chemine a? Èske w te devine 19? Paske ou ta dwe gen dwa. 19 te eleman ki sot pase a nou ajoute nan nan pile lè nou te pouse eleman sou li a, Se konsa, li k ap pase yo premye a eleman ki vin retire li. Li nan kòm si nou te di 28, ak Lè sa a, nou mete 33 sou tèt li, epi nou mete 19 sou tèt sa. Eleman la sèlman nou ka pran an se 19. 

Koulye a, nan dyagram nan isit la ki sa mwen te fè se sòt de efase 19 soti nan etalaj la. Sa a pa aktyèlman ki sa nou ap ale nan fè. Nou ap jis ale nan kalite a pretann li se pa la. Li nan toujou gen la nan ki kote memwa, men nou ap jis ale nan inyore li pa chanje tèt la nan chemine nou an nan men yo te 3 a 2. Se konsa, si nou te kounye a pouse yon lòt eleman sou chemine a, li ta sou ekri 19. 

Men, kite a pa ale nan pwoblèm nan a efase 19 soti nan pil la. Nou ka jis pretann li se pa la. Pou rezon nan chemine a li nan ale si nou chanje tèt la yo dwe 2 olye pou yo 3. Tout dwa, se konsa ke te bèl anpil li. Sa a tout nou bezwen fè nan pòp yon eleman nan. Se pou yo fè l 'ankò. Se konsa, mwen te make l 'nan wouj la a yo endike nou ap fè yon lòt apèl. Nou pral fè menm bagay la. 

Se konsa, sa ki pwal pase? Oke, nou ap ale nan magazen 33 nan x e nou pral chanje tèt la nan chemine a nan 1. Se konsa, ki si nou te kounye a pouse yon eleman an chemine a ki nou ap pral fè kounye a, sa k ap pase rive se nou ap ale recouvrir Nimewo kote etalaj 1. Se konsa, ki 33 ki te sòt de kite dèyè ke nou jis pran pòz se pa la ankò, nou ap jis pral batr l ', li mete 40 gen pito. Lè sa a, nan kou, depi nou te fè yon pouse, nou ap ale nan kantite a tèt nan chemine a nan 1 rive nan 2 se konsa ke si nou kounye a ajoute yon lòt eleman li 'tout ale nan nimewo kote etalaj de. 

Koulye a, lis lye yo se yon lòt fason yo aplike pil. Men, si definisyon sa a sou mòn lan ekran isit la sanble yo konnen yo nou la a, li nan paske li sanble prèske ekzakteman menm bagay, an reyalite, nan li bèl anpil se egzakteman nan menm jan ak yon lis separeman lye, si ou sonje soti nan diskisyon nou an nan separeman lye lis nan yon lòt videyo. Sèlman restriksyon a isit la se pou nou kòm pwogramasyon, nou pa ap pèmèt yo Insert ou efase owaza nan lis ki separeman lye ki nou te ka deja fè. Nou kapab sèlman kounye a Insert ak efase soti nan devan an oswa tèt la nan lye a lis. Sa ki nan vrèman sèlman nan diferans menm si. Sa a se otreman yon lis separeman lye. Li nan sèlman restriksyon nan ranplase sou tèt nou kòm pwogramasyon ki chanje l 'nan yon pil. 

Règ la isit la se yo toujou kenbe yon konsèy nan tèt la nan yon lis lye. Sa a se nan kou yon jeneralman règ enpòtan an premye. Pou separeman lye lis de tout fason ou sèlman bezwen yon konsèy nan tèt la yo nan lòd yo gen sa chèn kapab, al gade bay chak eleman lòt nan lis la lye. Men, li la patikilyèman enpòtan ak yon pil. Se konsa, jeneralman ou se ale nan aktyèlman vle konsèy sa a yo dwe yon varyab mondyal la. Li nan pwobableman ale nan gen menm vin pi fasil ki fason. Se konsa, sa yo se analogue yo nan pouse ak pòp? Dwa. Se konsa, pouse ankò se ajoute yon eleman nouvo nan chemine a. Nan yon lis lye ki vle di nou ap ale nan gen yo kreye yon ne nouvo ke nou ap pral ajoute nan lis la lye, ak Lè sa a swiv etap sa yo atansyon ke nou te dekri deja nan lis separeman lye nan ajoute li nan chèn nan san yo pa kraze chèn lan ak pèdi oswa orphaning nenpòt eleman nan lis la lye. Epi sa a, fondamantalman ki sa sa ti kras pate nan tèks gen rezime. Li kite yo pran yon gade nan li kòm yon dyagram. 

Se konsa, isit la nan lis lye nou an. Li tann gen kat eleman. Ak plis ankò parfe isit la nan nou an pile ki gen kat eleman. Li kite yo di nou kounye a ou vle pouse yon nouvo atik sou chemine sa a. E nou vle pouse yon nouvo atik ki gen done valè 12. Oke kisa nou pral fè? Oke premye nou ap ale nan espas malok, dynamique asiyen espas pou yon nouvo ne. Ak nan kou imedyatman apre nou fè yon apèl toujou malok nou asire w ke w tcheke pou nil, paske si nou te resevwa tounen nil te gen kèk sòt de pwoblèm. Nou pa vle dèreferans ki nil konsèy oswa ou pral soufri yon fay seg. Sa a pa bon. Se konsa, nou te malloced nan ne an. Nou pral asime nou te gen siksè isit la. Nou pral mete an 12 jaden an done nan ki ne. Koulye a, ou sonje ki nan endikasyon nou an deplase pwochen pou nou pa kraze chèn lan? Nou gen yon koup nan opsyon isit la, men yon sèl la sèlman ki k ap pase yo dwe san danje se yo mete nouvèl pwochen konsèy nan pwen nan tèt la fin vye granmoun nan lis la oswa sa ki pwal byento pwal nan fin vye granmoun ki an tèt lis la. Epi, koulye a ke tout nan nou an eleman yo nan chenn ansanm, nou ka jis deplase lis nan pwen nan plas la menm ke nouvo fè. Apre sa, nou gen kounye a efektivman pouse yon nouvo eleman sou devan an nan chemine a. 

Nan pòp nou jis vle efase ki eleman an premye. Se konsa, fondamantalman sa nou dwe fè isit la, byen nou gen jwenn eleman, dezyèm lan. Evantyèlman ki pral vin nouvo nan tèt apre nou efase yon sèl la an premye. Se konsa, nou jis bezwen kòmanse soti nan nan konmansman an, deplase yon sèl pi devan. Yon fwa nou te gen yon kenbe sou yon sèl pou pi devan nan kote nou kounye a èske nou ka efase youn nan premye san danje ak Lè sa a nou ka jis deplase tèt la nan pwen nan sa ki te nan dezyèm manda ak Lè sa a kounye a se premye a apre sa te ne efase. 

Se konsa, ankò, pran yon gade nan li kòm yon dyagram nou vle kounye a pòp yon eleman koupe nan chemine sa a. Se konsa, sa nou fè? Oke nou ap premye ale nan kreye yon nouvo konsèy ki k ap pase A ak pwen nan plas la menm jan ak tèt la. Nou pwal pou avanse pou li yon sèl pozisyon pou pi devan lè li di egal Trav trav pwochen pou egzanp, ki ta avanse yon sèl la Trav konsèy pozisyon pi devan. Kounye a ke nou te gen yon kenbe fèm nan eleman nan premye a konsèy rele lis la, ak nan dezyèm eleman nan yon konsèy rele Trav, nou ka efase ke san danje premye eleman soti nan chemine a san yo pa pèdi rès la nan chèn lan paske nou gen yon fason, al gade nan eleman nan dezyèm voye pa fason pou nan konsèy rele Trav. 

Se konsa, kounye a nou ka libere ki ne. Nou ka libere lis. Lè sa a, tout sa nou bezwen fè kounye a se deplase lis nan pwen nan plas la menm ki Trav fè, epi nou ap sòt de tounen kote nou te kòmanse anvan nou pouse 12 pase nan plas an premye, dwat. Sa a se egzakteman ki kote nou te. Nou te gen sa a chemine kat eleman. Nou te ajoute yon senkyèm. Nou pouse yon senkyèm eleman sou li a, ak Lè sa a nou déja ki pi resamman te ajoute eleman tounen nan. 

Sa ki nan vrèman bèl anpil tout gen nan pil. Ou ka aplike yo kòm ranje. Ou ka aplike yo kòm lis lye. Gen, nan kou, lòt fason yo aplike yo kòm byen. Fondamantalman rezon ki fè yo nou ta itilize pil se yo kenbe done nan yon fason ki pi resamman te ajoute nan eleman se premye bagay la nou ap ale nan vle jwenn tounen. Mwen se Doug Lloyd, sa a se CS50.