DOUG LLOYD: Okej, så genom denna punkt är du förmodligen ganska bekant med arrayer och länkade listor vilket är de två primära datastrukturer vi ve talade om för att hålla uppsättningar uppgifter av liknande datatyper organiserad. Nu ska vi prata om ett par varianter på matriser och länkade listor. I den här videon vi ska att prata om stackar. Specifikt vi ska prata om en datastruktur som kallas en stapel. Minns från tidigare diskussioner om pekare och minne, att bunten är också namn för ett segment av minnet där statiskt deklarerade memory-- minne som du namn, variabler som du namnger et cetera och funktionsramar som vi också samtals stack ramar finns. Så det här är en stack datastruktur inte en stapel segment av minnet. OK. 

Men vad är en bunt? Så det är ganska mycket bara en speciell typ av struktur som upprätthåller uppgifter på ett organiserat sätt. Och det finns två mycket vanligaste sätten att genomföra staplar med två datastrukturer att vi redan är bekant med, arrayer och länkade listor. Vad gör en stapel speciell är sätt på vilket vi lägga in information i stacken, och hur vi ta bort information från stapeln. I synnerhet med staplar regeln är bara den mest nyligen tillagda elementet kan avlägsnas. 

Så tänk på det som om det är en stapel. Vi pålning uppgifter ovanpå sig själv, och endast sak på toppen i högen kan avlägsnas. Vi kan inte ta bort saken under eftersom allt annat skulle kollapsa och välta. Så vi verkligen håller på att bygga en stapel som vi sedan måste ta bort bit för bit. På grund av detta har vi ofta hänvisar på en stapel som LIFO struktur, sist in, först ut. LIFO, sist in, först ut. 

Så på grund av denna begränsning av hur information kan läggas till och tas bort från en stapel, det finns verkligen bara två saker vi kan göra med en skorsten. Vi kan skjuta, som är den term vi använder för att lägga till ett nytt element i början av stack, eller om stapeln inte existerar och vi skapar det från början, skapa stapeln i första hand skulle trycka. Och sedan pop, det är den typ av CS term vi använder för att ta bort den senast tillsatt elementet från toppen av stacken. 

Så vi kommer att titta på både implementeringar, både array baserad och länkad lista baserad. Och vi kommer att börja med array baserad. Så här är den grundläggande uppfattning om vad arrayen baserad stapeln datastruktur skulle se ut. Vi har en definition typbestämd här. Insidan av att vi har två medlemmar eller fält av strukturen. Vi har en matris. Och återigen jag använder godtycklig datatyp värde. 

Så det kan vara någon datatyp int char eller något annat uppgifter skriver du tidigare skapat. Så vi har en matris med storlek kapacitet. Kapacitet som ett pund definierad konstant, kanske någon annanstans i vår fil. Så märker redan med just denna genomförande vi avgränsar oss som var typiskt fallet med matriser, som vi kan inte dynamiskt ändra storlek, där det finns ett visst antal maximal element som vi kan sätta i vår stack. I detta fall är det kapacitetselement. 

Vi håller också koll på överst i stacken. Vilken del är det mest nyligen lagts till stacken? Och så håller vi koll på det i en variabel som kallas topp. Och allt detta blir insvept tillsammans in i en ny datatyp som kallas en stapel. Och när vi är skapade denna nya datatypen vi kan behandla det som andra datatyper. Vi kan deklarera stack s, precis som vi kunde göra int x, eller röding y. Och när vi säger stack s, och vad som händer är vi en uppsättning av minne avsatt för oss. 

I detta fall är kapaciteten Jag har tydligen bestämt är 10, eftersom jag har en enda variabel av typen stack som innehåller två fält minns. En array, i detta fall kommer att vara en array av heltal vilket är fallet i de flesta av mina exempel. Och en annan heltalsvariabel kan lagra toppen, senast tillagda elementet till stapeln. Så en enda stack med vad vi bara definierade ser ut så här. Det är en låda som innehåller en uppsättning av 10 vad kommer vara heltal i detta fall och annan heltalsvariabel där i grönt att indikera överst i stacken. 

Om du vill ställa upp i stack vi bara säga s.top. Det är så vi åt en fält av en struktur återkallande. s.top lika 0 effektivt gör detta till vår stack. Så återigen har vi två operationer att vi kan utföra nu. Vi kan driva och vi kan dyka. Låt oss börja med push. Återigen, driver är att lägga en ny element till toppen av stacken. 

Så vad gör vi behöver göra denna array baserad genomförande? Väl i allmänhet push-funktion går att behöva acceptera en Pekare till stapeln. Nu tar en andra och tänka på det. Varför skulle vi vilja att acceptera en pekare till stapeln? Minns från tidigare videor på variabel omfattning och pekare, vad skulle hända om vi precis skickat stack, s snarare in som en parameter? Vad skulle faktiskt gått där? Kom ihåg att vi skapar en kopia när vi passerar den till en funktion om vi inte använder pekare. Och så den här funktionen driva behov att acceptera en pekare till stapeln så att vi faktiskt förändras stapeln tänker vi ändra. 

Den andra saken tryck vill förmodligen acceptera är ett dataelement av typen värde. I detta fall, återigen, ett heltal som vi kommer att lägga till toppen av stacken. Så vi har fått våra två parametrar. Vad ska vi Nu gör insidan av tryck? Jo, helt enkelt, vi ska bara lägga detta element till toppen av stacken och sedan ändra var toppen av stapeln är, att s prick toppvärde. Så det här är vad en funktion deklaration för push- kan se ut i ett matrisbaserad implementering. 

Återigen är detta inte en hård och snabb regel att du kan ändra på detta och har det varierar på olika sätt. Kanske s förklaras globalt. Och så att du inte ens behöver att passera den är som en parameter. Detta är återigen bara en generella fallet för push. Och det finns olika sätt att genomföra den. Men i detta fall vår tryck kommer att ta två argument, en pekare till en skorsten och en dataelement av typen värde, heltal I det här fallet. 

Så vi förklarade s, vi nämnda s.top lika 0. Låt oss nu driva nummer 28 på stacken. Och vad betyder det? Väl närvarande den toppen av stapeln är 0. Och så vad är i grund och botten kommer att hända är vi kommer att hålla antalet 28 in array plats 0. Ganska enkelt, rätt att var toppen och nu är vi är bra att gå. Och då måste vi ändra på det överst i stapeln kommer att bli. Så att nästa gång Vi trycker ett led i, vi kommer att lagra den i array plats, förmodligen inte 0. Vi vill inte skriva över vad vi bara sätta dit. Och så vi ska bara flytta upp för att en. Det gör förmodligen vettigt. 

Om vi ​​nu vill sätta ett annat element på stacken, säga att vi vill driva 33, väl nu vi ska bara ta 33 och satte den på array platsnummer 1, och sedan ändra toppen av vår stack vara array plats nummer två. Så om nästa gång vi vill skjuta ett element på stacken, det ska sättas i array plats 2. Och låt oss göra det en gång till. Vi kommer att driva 19 av av staplarna. Vi sätter 19 i array plats 2 och ändra toppen av vår stack att vara array plats 3 så om nästa gång vi måste göra en push vi är bra att gå. 

OK, så det är att trycka i ett nötskal. Vad sägs om popping? Så popping är den sortens motsvarighet till att pressa. Det är hur vi tar bort data från stacken. Och i allmänhet pop behov att göra följande. Det måste acceptera en pekare till stack, återigen i det allmänna fallet. I vissa andra fall du kanske har förklarat stapeln globalt, i vilket fall du behöver inte passera det i eftersom det redan har tillgång till den som en global variabel. Men vad behöver vi göra? Jo vi uppräkning toppen av stapeln i tryck, så vi förmodligen kommer att vilja att dekrementera toppen av stacken pop, eller hur? Och sedan naturligtvis vi också kommer att vilja att returnera värdet att vi tar bort. Om vi ​​lägger till element, vi vill ha att få element ut senare, vi förmodligen faktiskt vill lagra dem så vi inte bara ta bort dem från stapla och sedan inte göra något med dem. Generellt om vi trycka och poppar här vi vill lagra detta information på ett meningsfullt sätt och så att den inte gör vettigt att bara slänga den. Så denna funktion bör förmodligen tillbaka ett värde för oss. 

Så det här är vad en deklaration för pop kan se ut det längst upp till vänster. Den här funktionen returnerar uppgifter av typen värde. Återigen har vi använt heltal hela. Och det accepterar en pekare till en stapel som dess enda argument eller enda parameter. Så vad är pop kommer att göra? Låt oss säga att vi vill nu pop ett element bort av er. Så minns att jag sa att staplar är sista in, först ut, LIFO datastrukturer. Vilket element kommer att avlägsnas från stapeln? Har du gissa 19? Eftersom du skulle vara rätt. 19 var den sista delen vi lagt till stack när vi drev element på, och så det kommer att den första element som får bort. Det är som om vi sade 28, och då sätter vi 33 ovanpå det, och vi sätter 19 på toppen av det. Den enda faktor vi kan ta bort är 19. 

Nu i diagrammet här vad jag har gjort är sorts bort 19 från gruppen. Det är faktiskt inte vad vi ska göra. Vi ska bara typ av låtsas att det inte finns. Det är fortfarande kvar i den minnesplatsen, men vi kommer bara att ignorera det genom att ändra toppen av vår stack från att vara tre till två. Så om vi skulle nu trycka ett annat element på stacken, det skulle skriva över 19. 

Men låt oss inte gå igenom besväret för att ta bort 19 från stapeln. Vi kan bara låtsas som om det inte finns. Vid tillämpningen av stapeln det har gått om vi ändrar toppen att vara två i stället för tre. Okej, så det var ganska mycket det. Det är allt vi behöver göra att smälla en del av. Låt oss göra det igen. Så jag har markerat det i rött här för att anger vi gör ett annat samtal. Vi kommer att göra samma sak. 

Så vad kommer att hända? Tja, vi kommer att lagra 33 i x- och vi kommer att ändra toppen av stapeln till ett. Så att om vi nu att driva en elementet i stapeln som vi är kommer att göra just nu, vad som kommer att hända är vi ska skrivnings array plats nummer ett. Så att 33 som var typ av vänster bakom att vi bara låtsades är inte där längre, vi bara gå att clobber dem och lägg 40 där i stället. Och då naturligtvis, eftersom vi gjorde en push, vi kommer att öka den toppen av stapeln från ett till 2 så att om vi nu lägga till en annan faktor Det kommer gå in array plats nummer två. 

Nu länkade listor är en annan sätt att implementera stackar. Och om denna definition på skärm här ser bekant för dig, det beror på att det ser nästan exakt samma, i själva verket, det ganska mycket är exakt samma som en enskilt länkad lista, Om du minns från vår diskussion om listor enskilt kopplade i en annan video. Den enda begränsningen här är för oss som programmerare, vi är inte tillåtet att infoga eller ta bort slumpmässigt från var för sig länkad lista som vi kunde tidigare göra. Vi kan bara nu infoga och ta bort från den främre eller toppen av länkade listan. Det är egentligen den enda skillnad ändå. Detta är annars ett enskilt länkad lista. Det är bara begränsning byte på oss själva som programmerare som ändras den till en stapel. 

Regeln är att alltid hålla en pekaren till chefen för en länkad lista. Detta är naturligtvis en allmänt viktig regel först. För lista enskilt kopplade ändå du behöver bara en pekare till huvudet i syfte att ha det kedja kunna hänvisa varje annat element i den länkade listan. Men det är framför allt viktigt med en skorsten. Och så allmänt du ska verkligen vill denna pekare att vara en global variabel. Det är förmodligen kommer att bli ännu enklare på det sättet. Så vad är analoger av tryck och pop? Höger. Så driver igen lägger ett nytt element i stacken. I en länkad lista som innebär att vi kommer att ha att skapa en ny nod som vi är kommer att lägga in den länkade listan, och följ sedan försiktiga steg att vi har beskrivit tidigare i enskilt länkade listor för att lägga till kedjan utan att bryta kedjan och att förlora eller föräldralösa någon delar av den länkade listan. Och det är i princip vad som liten klump av text finns sammanfattar. Och låt oss ta en titt på det som ett diagram. 

Så här är vår länkad lista. Den innehåller samtidigt fyra element. Och mer perfekt här är vår stack innehåller fyra element. Och låt oss säga att vi nu vill driva en ny punkt på denna stack. Och vi vill driva en ny posten vars datavärde är 12. Och vad ska vi göra? Väl först ska vi malloc utrymme, dynamiskt allokera utrymme för en ny nod. Och naturligtvis omedelbart efter Vi gör ett anrop till malloc vi alltid se till att kontrollera för null, eftersom om vi fick null tillbaka Det var någon slags problem. Vi vill inte dereference som null pekare eller du kommer att drabbas av en seg fel. Det är inte bra. Så vi har malloced av noden. Vi kommer att anta att vi har haft framgång här. Vi kommer att sätta 12 i datafältet av den noden. Nu minns du vilka av våra pekare flyttar nästa så att vi inte bryter kedjan? Vi har ett par alternativ här men det enda som kommer att vara säkra är att sätta nyheter nästa pekare till peka på den gamla chefen listan eller vad som kommer snart att vara gamla chef på listan. Och nu när alla våra element kedjas ihop, Vi kan bara flytta listan till punkt till samma plats som nya gör. Och vi har nu i praktiken drivit en nytt element på framsidan av stapeln. 

Pop vi bara vill ta bort det första elementet. Och så i princip vad vi måste göra här, väl vi måste hitta det andra elementet. Till slut som kommer att bli den nya huvudet efter att vi tar bort den första. Så vi behöver bara börja från början, flytta en framåt. När vi har fått tag på ett framför där vi idag är att vi kan ta bort den första på ett säkert sätt och sedan kan vi bara flytta huvudet att peka på vad som var andra terminen och sedan nu är den första efter att nod har raderats. 

Så återigen, ta en titt på det som ett diagram vi vill nu pop en del av av denna stack. Så vad gör vi? Väl vi först kommer att skapa en ny pekare som händer att peka på samma plats som huvudet. Vi kommer att flytta den en position framåt genom att säga trav jämlikar trav nästa till exempel, som skulle föra trav pekaren en läge framåt. Nu när vi har fått en håll på det första elementet genom pekaren kallas listan, och andra elementet genom en pekare som heter trav, kan vi säkert ta bort den första elementet från stapeln utan att förlora resten av kedjan, eftersom vi har ett sätt att hänvisa till det andra elementet framåt med hjälp av pekaren kallade trav. 

Så nu kan vi frigöra den noden. Vi kan frigöra listan. Och sedan allt vi behöver göra nu är flytta listan till punkt till samma plats att trav gör, och vi är typ av tillbaka där vi började innan vi drivit 12 på i första hand, till höger. Det är precis där vi var. Vi hade detta med fyra element stack. Vi har lagt en femtedel. Vi sköt en femtedel element på, och sedan vi poppade som senast tillagda elementet backa. 

Det är egentligen ganska mycket allt som finns att travar. Du kan genomföra dem matriser. Du kan genomföra dem länkade listor. Det finns naturligtvis andra sätt att genomföra dem. I grund och botten anledningen till att vi skulle använda stackar är att underhålla data på ett sådant sätt att det senast tillagda elementet är det första vi är kommer att vilja komma tillbaka. Jag är Doug Lloyd, är detta CS50.