DOUG LLOYD: Greit, så ved dette punktet du er sannsynligvis ganske kjent med arrays og koblede lister som er det to primære datastrukturer vi har snakket om for å holde sett data av tilsvarende datatyper organisert. Nå skal vi snakke om et par varianter på arrays og koblede lister. I denne videoen skal vi å snakke om stabler. Spesielt vi kommer til å snakke om en datastruktur kalt en stabel. Recall fra tidligere diskusjoner om pekere og hukommelse, at bunken er også nevne for et segment av minne hvor statisk erklært memory-- minne som du navn, variabler som du navn, et cetera og funksjonsrammer som vi også kallstakken rammer eksisterer. Så dette er en stabel datastruktur ikke en stabel segment av hukommelse. OK. 

Men hva er en stabel? Så det er ganske mye bare en spesiell type struktur som opprettholder data på en organisert måte. Og det er to svært vanlige måter å implementere stabler med to datastrukturer at vi allerede er kjent med, arrays og koblede lister. Hva gjør en stabel spesielt er Måten vi legger informasjon i bunken, og måten vi fjerne informasjon fra bunken. Spesielt med stabler regelen er bare de mest nylig lagt element kan fjernes. 

Så tenk på det som om det er en stabel. Vi pæling informasjon på toppen av seg selv, og bare ting på toppen av pelen kan fjernes. Vi kan ikke fjerne noe under fordi alt annet ville kollapse og falle over. Så vi virkelig bygger en stabel som vi deretter må fjerne bit for bit. På grunn av dette vi vanligvis omtaler til en stabel som en LIFO struktur, sist inn, først ut. LIFO, sist inn, først ut. 

Det på grunn av denne begrensning på Slik informasjon kan legges til og fjernet fra en stabel, det er egentlig bare to ting vi kan gjøre med en stack. Vi kan presse, som er begrep vi bruker for å legge til et nytt element til toppen av stabel, eller dersom stabelen ikke eksisterer og vi skaper det fra bunnen av, skape stabelen i første omgang ville være å skyve. Og så pop, det er den slags CS Uttrykket vi bruker til å fjerne den sist lagt element fra toppen av bunken. 

Så vi kommer til å se på både implementeringer, både gruppe basert og lenket liste basert. Og vi kommer til å starte med gruppe basert. Så her er den grunnleggende idé om hva array basert stabelen datastruktur ville se ut. Vi har et maskinskrevet definisjon her. Innsiden av at vi har to medlemmer eller felter av strukturen. Vi har en matrise. Og igjen jeg bruker vilkårlig datatype verdi. 

Så dette kan være en hvilken som helst datatype, int røye eller annen data skriver du opprettet tidligere. Så vi har en rekke størrelse kapasitet. Kapasitet blir et pund definert konstant, kanskje et annet sted i vår fil. Så merker allerede med denne implementering vi byks oss som var typisk tilfelle med matriser som vi ikke kan dynamisk endre størrelse, hvor det er et visst antall av elementer maksimale som vi kan sette i stacken. I dette tilfellet er det kapasitets elementer. 

Vi holder også styr på toppen av bunken. Hva element er den mest nylig lagt til stakken? Og så vi holde styr på at i en variabel kalt toppen. Og alt dette blir pakket sammen inn i en ny datatype som kalles en stabel. Og når vi er skapt denne nye datatype vi kan behandle det som hvilken som helst annen datatype. Vi kan erklære stabelen s, akkurat som vi kunne gjøre int x, eller røye y. Og når vi sier stable s, vel hva som skjer er vi får et sett med minne satt til side for oss. 

I dette tilfelle kapasiteten Jeg har tydeligvis bestemt seg er 10 fordi jeg har en enkelt variabel av type stack som inneholder to felt huske. En matrise, i dette tilfellet går å være en oppstilling av heltall slik tilfellet er i de fleste av mine eksempler. Og en annen heltallsvariabelen som kan lagre den øverste, den mest nylig lagt element av stabelen. Så en enkelt stakk av hva vi bare definert ser ut som dette. Det er en boks som inneholder en rekke 10 hva vil være heltall i denne saken, og annen heltallsvariabelen det i grønt å indikere toppen av bunken. 

Slik stiller toppen av stack vi bare si s.top. Det er hvordan vi tilgang til et felt av en struktur tilbakekalling. s.top lik 0 effektivt gjør dette til vår stabelen. Så igjen har vi to operasjoner at vi kan utføre nå. Vi kan presse og vi kan pop. La oss starte med push. Igjen, presser er å legge til en ny element til toppen av stabelen. 

Så hva gjør vi trenger å gjøre i denne matrisen basert implementering? Vel generelt push-funksjonen skal å trenge å akseptere en Peker til bunken. Nå tar en andre og tenke på det. Hvorfor skulle vi ønske å akseptere en peker til stakken? Recall fra tidligere videoer på variabel omfang og pekere, hva som ville skje hvis vi bare sendt stabel, s snarere som en parameter? Hva ville egentlig bli vedtatt i det? Husk at vi oppretter en kopi når vi passerer den til en funksjon med mindre vi bruker pekere. Og så denne funksjonen presse behov å akseptere en peker til stabelen slik at vi faktisk endring bunken vi har til hensikt å endre. 

Den andre tingen presse ønsker sannsynligvis å godta et dataelement av type verdi. I dette tilfellet, igjen, er et helt tall som vi kommer til å legge opp til toppen av bunken. Så vi har fått våre to parametere. Hva skal vi nå gjøre inne av push? Vel, ganske enkelt, vi bare kommer til å legge som element til toppen av stabelen og deretter endre hvor toppen av stabelen er, som er prikk øverste verdi. Så dette er hva en funksjon erklæring for push- kan se ut i en matrise-basert implementering. 

Igjen dette er ikke en fast regel at du kan endre dette og har det varierer på forskjellige måter. Kanskje s er erklært globalt. Og slik at du ikke engang trenger å passere det er som en parameter. Dette er igjen bare en generelle tilfellet for push. Og det er annerledes måter å gjennomføre det. Men i dette tilfellet vår Push kommer til å ta to argumenter, en peker til en stabel og et dataelement av type verdi, heltall i denne saken. 

Så vi erklært s, vi sa s.top lik 0. Nå la oss presse nummer 28 på stakken. Vel hva betyr det? Vel i dag den toppen av stabelen er 0. Og så hva er i utgangspunktet kommer til å skje er vi kommer til å holde fast antall 28 i matrisen plassering 0. Ganske grei, ikke sant, at var toppen, og nå er vi godt å gå. Og da må vi endre hva toppen av bunken vil bli. Slik at neste gang vi presse et element i, vi kommer til å lagre den i matrise beliggenhet, sannsynligvis ikke er 0. Vi ønsker ikke å overskrive hva vi bare satt der. Og så får vi bare flytte toppen til en. Som sannsynligvis er fornuftig. 

Nå hvis vi ønsker å sette et annet element på stakken, si at vi ønsker å presse 33, vel nå er vi bare nødt til å ta 33 og sette den på rekke plasseringsnummer 1, og deretter endre toppen av vår stable å være matrisen plassering nummer to. Så hvis neste gang vi ønsker å presse et element på stakken, det vil bli satt i matrise plassering 2. Og la oss gjøre det en gang til. Vi skal presse 19 ut av stabler. Vi setter 19 i matrisen plassering 2 og endre toppen av stacken å være matrise plassering 3 så hvis neste gang vi trenger for å gjøre en push vi er godt å gå. 

OK, så som presser i et nøtteskall. Hva med dukker? Så popping er den slags motstykke til å skyve. Det er hvordan vi fjerne data fra bunken. Og generelt pop behov å gjøre følgende. Det er behov for å akseptere en peker til stable, igjen i det generelle tilfellet. I enkelte andre tilfeller kan det være har erklært stabelen globalt, I så fall trenger du ikke å passere det i fordi det allerede har tilgang til det som en global variabel. Men så hva annet trenger vi å gjøre? Vel vi ble økes toppen av stabelen i push, slik at vi sannsynligvis kommer til å ønske for å dekrementere toppen av stabelen i pop, ikke sant? Og så selvfølgelig vi også kommer til å ønske returnere verdien at vi fjerner. Hvis vi legger til elementer, vi ønsker å få elementer ut senere, vi sannsynligvis faktisk ønsker å lagre dem, slik at vi ikke bare slette dem fra stable og så gjøre noe med dem. Vanligvis hvis vi er presser og spratt her vi ønsker å lagre denne informasjon på en meningsfull måte og så det gjør ikke fornuftig å bare forkaste det. Så denne funksjonen bør trolig returnere en verdi for oss. 

Så dette er hva en erklæring for pop kan se ut som det øverst til venstre. Denne funksjonen returnerer data av type verdi. Igjen har vi brukt heltall hele. Og den godtar en peker til en stabel som eget argument eller eneste parameter. Så hva er pop kommer til å gjøre? La oss si at vi ønsker å nå pop et element av av s. Så husker jeg sa at stabler er siste inn, først ut, LIFO datastrukturer. Hvilket element skal fjernes fra stabelen? Visste du gjette 19? Fordi du ville være rett. 19 var den siste element vi satt til stable når vi var skyve elementer på, og så det kommer til den første element som blir fjernet. Det er som om vi sa 28, og da vi satt 33 på toppen av det, og vi legger 19 på toppen av det. Den eneste element vi kan ta av er 19. 

Nå i diagrammet her hva jeg har gjort er liksom slettet 19 fra tabellen. Det er faktisk ikke hva vi skal gjøre. Vi skal bare snill av late som om det ikke er der. Det er fortsatt der i at minneposisjon men vi skal bare ignorere det ved å endre toppen av stacken være fra 3 til 2. Så hvis vi skulle nå presse et annet element på stakken, det ville i løpet skrive 19. 

Men la oss ikke gå gjennom problemer av å slette 19 fra stabelen. Vi kan bare late som om det ikke er der. Med henblikk på stabelen er den borte hvis vi endrer toppen for å være to i stedet for tre. All right, så det var ganske mye det. Det er alt vi trenger å gjøre til pop et element av. La oss gjøre det igjen. Så jeg har fremhevet det i rødt her for å indikerer vi gjør en annen samtale. Vi kommer til å gjøre det samme. 

Så hva kommer til å skje? Vel, vi skal lagre 33 i x, og vi kommer å endre øverst i bunken til en. Slik at hvis vi var nå å presse en element i bunken som vi er kommer til å gjøre akkurat nå, hva kommer til å skje er vi kommer skrivings matrise plassering nummer 1. Slik at 33 som ble liksom igjen bak at vi bare lot er ikke der lenger, vi bare går til clobber den og sette 40 der i stedet. Og da selvfølgelig, siden vi gjorde en push, vi kommer til å øke den toppen av stabelen fra 1 til 2 slik at hvis vi nå legger et annet element det vil gå inn i matrisen plassering nummer to. 

Nå lenkede lister er en annen måte å implementere stabler. Og hvis denne definisjonen på skjermen her ser kjent ut for deg, det er fordi det ser nesten nøyaktig det samme, faktisk det ganske mye er akkurat den samme som en enkeltvis lenket liste, hvis du husker fra vår diskusjon av enkeltvis knyttet lister i en annen video. Den eneste begrensningen her er for oss som programmerere, Vi har ikke lov til å sette inn eller slette tilfeldig fra enkeltvis lenket liste som vi tidligere kunne gjøre. Vi kan bare nå sette inn og slette fra forsiden eller toppen av den koblede listen. Det er egentlig den eneste Forskjellen skjønt. Dette er ellers en enkeltvis lenket liste. Det er bare en begrensning erstatter på oss selv som programmerere som endrer den til en stabel. 

Regelen her er å alltid ha en Peker til hodet på en lenket liste. Dette er selvfølgelig en vanligvis viktig regel først. For enkeltvis lenket liste allikevel du trenger bare en peker til hodet for å få den kjeden kunne henvise til alle andre element i lenket liste. Men det er spesielt viktig med en stabel. Og så generelt du er kommer til å faktisk ønsker denne pekeren til å bli en global variabel. Det er trolig kommer til å bli enda enklere på den måten. Så hva er de analoger av push og pop? Høyre. Så presser igjen er å legge et nytt element i stabelen. I en lenket liste som betyr at vi kommer til å ha å opprette en ny node som vi er kommer til å legge inn i lenket liste, og følg deretter forsiktige skritt at vi har skissert tidligere i enkeltvis lenkede lister å legge det til kjedet uten å bryte kjeden og miste eller orphaning noen elementer av lenket liste. Og det er stort sett hva som liten blob av tekst der oppsummerer. Og la oss ta en titt på det som et diagram. 

Så her er vår lenket liste. Den inneholder fire elementer samtidig. Og mer perfekt her er vår stable inneholder fire elementer. Og la oss si at vi nå ønsker å presse et nytt element på denne bunken. Og vi ønsker å presse en ny element som dataverdi er 12. Vel hva skal vi gjøre? Vel første vi kommer til å malloc plass, dynamisk tildele plass for en ny node. Og selvfølgelig umiddelbart etter vi ringe til malloc vi alltid sørg for å sjekke for null, fordi hvis vi fikk null tilbake det var et slags problem. Vi ønsker ikke å dereference at null pekeren eller du vil lide en SEG feil. Det er ikke bra. Så vi har malloced av noden. Vi vil anta vi har hatt suksess her. Vi kommer til å sette 12 inn datafelt for den noden. Nå husker du hvilke av våre pekere flytter neste slik at vi ikke bryte kjeden? Vi har et par alternativer her, men den eneste som kommer til å være trygge er å sette nyheter neste pekeren til punkt til den gamle hodet av listen eller hva som snart vil være den gamle hodet av listen. Og nå som alle våre Elementene er lenket sammen, vi kan bare flytte listen til å peke til det samme sted som nye gjør. Og vi har nå effektivt skjøvet en nytt element på forsiden av stabelen. 

Til pop vi bare ønsker å slette det første elementet. Og så i utgangspunktet hva vi har å gjøre her, Vel vi må finne det andre elementet. Etter hvert som blir ny hodet etter at vi slette den første. Så vi trenger bare å starte fra begynnelsen, flytte en fremover. Når vi har fått tak på en frem til der vi i dag vi kan slette den første man trygt og da kan vi bare flytte hodet å peke på hva som var den andre periode og deretter nå er den første etter at node har blitt slettet. 

Så igjen, ta en titt på det som et diagram vi vil nå sprette en element av av denne bunken. Så hva gjør vi? Vel vi først kommer til å skape en ny peker som kommer å peke på det samme stedet som hodet. Vi kommer til å flytte den ene stilling frem ved å si trav equals trav neste for eksempel, som ville fremme trav pekeren én posisjon fremover. Nå som vi har fått en hold på det første elementet gjennom pekeren kalt liste, og andre element via en peker som kalles trav, kan vi trygt slette den første element fra stabelen uten å miste resten av kjeden fordi vi har en måte å referere til det andre elementet sende ved hjelp av pekeren kalt trav. 

Så nå kan vi frigjøre den noden. Vi kan frigjøre listen. Og så alt vi trenger å gjøre nå er flytte listen til punkt til samme sted at trav gjør, og vi er liksom tilbake der vi startet før vi presset 12 på i første omgang, ikke sant. Dette er akkurat der vi var. Vi hadde denne fire element stabelen. Vi har lagt til en femte. Vi presset en femte element på, og da er vi popped som sist lagt element tilbake av. 

Det er egentlig ganske mye alt som er å stabler. Du kan implementere dem som arrays. Du kan implementere dem som koblede lister. Det er, selvfølgelig, annen måter å implementere dem også. I utgangspunktet grunnen til at vi ville bruke stabler er å opprettholde data på en slik måte at det mest nylig lagt element er det første vi er kommer til å ønske å komme tilbake. Jeg er Doug Lloyd, dette er CS50.