DOUG LLOYD: Okay, så ved dette punkt, du er sandsynligvis temmelig bekendt med arrays og hægtede lister som er de to primære datastrukturer vi har talte om for at holde sæt data af tilsvarende datatyper organiseret. Nu vil vi tale om et par variationer på arrays og hægtede lister. I denne video vil vi at tale om stakke. Konkret vil vi tale om en datastruktur kaldes en stabel. Recall fra tidligere diskussioner om pointere og hukommelse, at stakken er også navn for et segment af hukommelse hvor statisk erklæret memory-- hukommelse, som du navn, variabler, som du nævne, et cetera og funktion rammer, som vi også findes call stack rammer. Så dette er en stak datastruktur ikke en stabel segment af hukommelse. OK. 

Men hvad er en stak? Så det er temmelig meget bare en særlig form for struktur der vedligeholder data på en organiseret måde. Og der er to meget almindelige måder at implementere stakke ved hjælp af data to strukturer at vi er allerede er bekendt med, arrays og hægtede lister. Hvad gør en stak særlige er måde, hvorpå vi lægge oplysninger ind i stakken, og den måde, vi fjerne oplysninger fra stakken. Navnlig med stakke reglen er kun de mest nylig tilføjet element kan fjernes. 

Så tænk over det, som om det er en stak. Vi hober oplysninger oven på sig selv, og kun de ting i toppen af bunken kan fjernes. Vi kan ikke fjerne ting nedenunder fordi alt andet ville sammenbrud og vælter. Så vi virkelig er ved at opbygge en stak, der vi så nødt til at fjerne stykke for stykke. På grund af dette, vi almindeligvis henvise til en stak som LIFO struktur, sidste ind, først ud. LIFO, sidste ind, først ud. 

Så på grund af denne begrænsning på hvordan information kan føjes til og fjernet fra en stak, er der virkelig kun to ting, vi kan gøre med en stak. Vi kan skubbe, som er Udtrykket vi bruger til at tilføje et nyt element til toppen af stak, eller hvis stakken ikke findes og vi er ved at oprette det fra bunden, skabe stablen i første omgang ville være at skubbe. Og derefter pop, det er den slags CS sigt, vi bruger til at fjerne den senest yderligere element fra toppen af ​​stakken. 

Så vi kommer til at se på både implementeringer, både matrix baseret og knyttet liste baseret på. Og vi kommer til at starte med matrix baseret. Så her er den grundlæggende idé om, hvad array baseret stabel datastruktur ville se ud. Vi har en indtastet definition her. Inde i at vi har to medlemmer eller felter af strukturen. Vi har et array. Og igen Jeg bruger vilkårlig datatype værdi. 

Så dette kunne være en hvilken som helst datatype, int char eller anden data type du tidligere har oprettet. Så vi har en bred vifte af størrelse kapacitet. Kapacitet, der er et pund defineret konstant, måske et andet sted i vores fil. Så mærke allerede med denne særlige gennemførelse vi afgrænser os selv som var typisk tilfældet med arrays, som vi ikke kan dynamisk ændre størrelse, hvor der er et vist antal af den maksimale elementer, vi kan sætte i vores stak. I dette tilfælde er det kapacitet elementer. 

Vi holder også styr på toppen af ​​stakken. Hvilket element er den mest for nylig tilføjet til stakken? Og så vi holde styr på det i en variabel kaldet toppen. Og alt dette bliver pakket op sammen i en ny datatype kaldes en stabel. Og når vi er skabt denne nye datatype vi kan behandle det som enhver anden datatype. Vi kan erklære stak s, ligesom vi kunne gøre int x, eller char y. Og når vi siger stable s, godt, hvad der sker er vi får et sæt hukommelse afsat til os. 

I dette tilfælde kapacitet Jeg har åbenbart besluttet er 10, fordi jeg har en enkelt variabel af typen stack som indeholder to felter huske. Et array, i dette tilfælde vil at være et array af heltal som det er tilfældet i de fleste af mine eksempler. Og en anden heltalsvariabel stand til at lagre toppen, den senest tilføjede element til stakken. Så en enkelt stak af det, vi netop definerede ligner dette. Det er en boks, der indeholder et array af 10 hvad vil være heltal i denne sag, og anden heltalsvariabel der i grøn at angive toppen af ​​stakken. 

For at indstille toppen af stak vi bare sige s.top. Det er, hvordan vi adgang til en inden for en struktur tilbagekaldelse. s.top lig 0 effektivt gør dette til vores stack. Så igen har vi to operationer at vi kan udføre nu. Vi kan skubbe, og vi kan pop. Lad os starte med push. Igen, skubber tilføjer en ny element til toppen af ​​stakken. 

Så hvad skal vi gøre i dette array baseret implementering? Tja generelt push-funktion går få brug for at acceptere en pointer til stakken. Nu tager en anden og tænke over det. Hvorfor skulle vi vil acceptere en pointer til stakken? Recall fra tidligere videoer på variabel rækkevidde og pointere, hvad der ville ske, hvis vi lige har sendt stakken, s snarere som en parameter? Hvad ville der egentlig være bestået derinde? Husk at vi er ved at oprette en kopi når vi videregive det til en funktion medmindre vi bruger pointere. Og så denne funktion skubbe behov at acceptere en pegepind til stakken så at vi faktisk ændrer stakken vi agter at ændre. 

Den anden ting skub sandsynligvis vil acceptere, er en dataelement af typen værdi. I dette tilfælde igen, et heltal, der vi kommer til at føje til toppen af ​​stakken. Så vi har fået vores to parametre. Hvad skal vi nu gøre inde push? Nå, simpelthen, vi bare kommer til at tilføje dette element til toppen af ​​stablen og derefter ændre hvor toppen af stakken er, at s dot top værdi. Så dette er, hvad en funktion angivelse til tryk kan se ud i en matrix-baseret implementering. 

Igen dette er ikke en ufravigelig regel at du kunne ændre dette og har Det varierer på forskellige måder. Måske s erklæres globalt. Og så du behøver ikke engang at passere det er som en parameter. Dette er igen blot en generel tilfældet for push. Og der er forskellige måder at gennemføre den. Men i dette tilfælde vores skub kommer til at tage to argumenter, en pointer til en stak og en dataelement af typen værdi, heltal I dette tilfælde. 

Så vi erklærede s, vi nævnte s.top lig 0. Lad os nu skubbe nummer 28 på stablen. Nå hvad betyder det? Godt øjeblikket toppen af ​​stakken er 0. Og så hvad er dybest set kommer til at ske, er vi kommer til at holde antallet 28 ind matrix placering 0. Temmelig ligetil, højre, at var den øverste, og nu vi er gode til at gå. Og så er vi nødt til at ændre, hvad toppen af ​​stakken bliver. Således at næste gang vi skubber et element i, vi kommer til at gemme det i matrix placering, sandsynligvis ikke 0. Vi ønsker ikke at overskrive hvad vi bare sætte der. Og så vi vil bare flytte toppen til 1. Det sandsynligvis giver mening. 

Nu, hvis vi ønsker at sætte et andet element på stakken, siger vi ønsker at presse 33, godt nu vi bare kommer til at tage 33 og sætte det på matrix placering nummer 1, og derefter ændre øverst på vores stable at være matrix placering nummer to. Så hvis næste gang vi ønsker at skubbe et element på stakken, det vil blive sat i matrix placering 2. Og lad os gøre det en gang mere. Vi vil skubbe 19 ud af stakkene. Vi vil sætte 19 i matrix placering 2 og ændre øverst på vores stack at være matrix Sted 3 så hvis næste gang vi nødt til at gøre en push vi er gode til at gå. 

OK, så der er skubber i en nøddeskal. Hvad med popping? Så popping er den slags modstykke til at skubbe. Det er, hvordan vi fjerne data fra stakken. Og generelt pop behov at gøre følgende. Det har brug for at acceptere en pointer til den stak, igen i det generelle tilfælde. I visse andre tilfælde du måske har erklæret stakken globalt, i hvilket tilfælde du ikke behøver at passere det i, fordi det allerede har adgang til det som en global variabel. Men hvad skal vi gøre? Nå vi forøgelse toppen af ​​stakken i tryk, så vi sandsynligvis vil ønsker for at mindske toppen af ​​stablen i pop, ikke? Og så selvfølgelig vi også vil ønsker at returnere værdien at vi fjerner. Hvis vi tilføjer elementer, vi ønsker at få elementer ud senere, vi sandsynligvis faktisk ønsker at gemme dem, så vi ikke bare slette dem fra stable og derefter gøre noget med dem. Generelt hvis vi er skubber og knaldende her vi ønsker at gemme denne oplysninger på en meningsfuld måde og så betyder det ikke gør mening at bare kassere det. Så denne funktion bør sandsynligvis vende tilbage en værdi for os. 

Så dette er, hvad en angivelse til pop kan se ud der øverst til venstre. Denne funktion returnerer data af typen værdi. Igen vi har været ved hjælp af heltal overalt. Og det accepterer en pointer til en stak som dens eneste argument eller tunge parameter. Så hvad der pop kommer til at gøre? Lad os sige, at vi ønsker at nu pop et element ud af s. Så husk jeg sagde, at stakke er sidste ind, først ud, LIFO datastrukturer. Hvilket element vil fjernes fra stablen? Vidste du gætte 19? Fordi du ville være rigtigt. 19 var den sidste element, vi føjet til stable da vi skubber elementer, og så det kommer til den første element, der bliver fjernet. Det er, som om vi sagde 28, og så vi sætter 33 på toppen af ​​det, og vi sætter 19 oven i købet. 19. Det eneste element, vi kan tage off er 

Nu i diagrammet her hvad jeg har gjort er slags slettet 19 fra arrayet. Det er faktisk ikke hvad vi skal gøre. Vi bare at slags af lade som om det ikke er der. Det er stadig der i at hukommelsen placering, men vi bare at ignorere det ved at ændre øverst på vores stack fra at være 3 til 2. Så hvis vi skulle nu skubbe et andet element på stakken, det ville i løbet skrive 19. 

Men lad os ikke gå gennem den ulejlighed at slette 19 fra stablen. Vi kan bare lade som om det ikke er der. Med henblik på stakken det er gået, hvis vi ændre toppen til 2 i stedet for 3. Okay, så det var temmelig meget det. Det er alt, vi skal gøre til pop et element fra. Lad os gøre det igen. Så jeg har fremhævet det i rødt her til angiver vi gør et andet opkald. Vi kommer til at gøre det samme. 

Så hvad der vil ske? Nå, vi kommer til at gemme 33 i x- og vi vil at ændre toppen af ​​stakken til 1. Så hvis vi nu til at skubbe en element i stakken, som vi er kommer til at gøre lige nu, hvad der kommer til at ske er vi vil overskrive vifte placering nummer 1. Således at 33 der var slags venstre bag at vi bare lod ikke er der længere, vi bare at tæske det og sætte 40 der i stedet. Og så selvfølgelig, da vi gjorde et skub, vi kommer til at øge den toppen af ​​stakken fra 1 til 2 så hvis vi nu føje et andet element det vil gå ind matrix placering nummer to. 

Nu hægtede lister er en anden måde at gennemføre stakke. Og hvis denne definition på skærmen her ser bekendt for dig, det er fordi det ser næsten nøjagtigt det samme, i virkeligheden, det temmelig meget er præcis den samme som en enkelt bundet liste, hvis du husker fra vores diskussion af enkeltvis forbundet lister i en anden video. Den eneste begrænsning her er for os som programmører, vi ikke lov til at indsætte eller slette tilfældigt fra enkelt bundet liste som vi tidligere kunne gøre. Vi kan kun nu indsætte og slette fra forsiden eller toppen af ​​den linkede listen. Det er virkelig den eneste forskel selv. Dette er ellers et enkelt bundet listen. Det er kun den begrænsning udskiftning på os selv som programmører, der ændrer det til en stabel. 

Reglen her er altid at opretholde en pointer til lederen af ​​en linket liste. Dette er naturligvis en generelt vigtig regel først. For enkeltvis sammenkædet liste alligevel du behøver kun en pointer til hovedet med henblik på at få det kæde kunne henvise til alle andre elementer i den linkede liste. Men det er især vigtigt med en stak. Og så generelt er du vil rent faktisk ønsker denne pegepind til at være en global variabel. Det er nok at gå til være endnu nemmere på den måde. Så hvad er analoger af skub og pop? Højre. Så skubber igen tilføjer et nyt element til stakken. I en sammenkædet liste, betyder, at vi er nødt til at oprette en ny knude, at vi er kommer til at tilføje i linkede liste, og følg derefter forsigtige skridt at vi har skitseret tidligere i enkeltvis hægtede lister at føje den til kæden uden at bryde kæden og miste eller forældreløse enhver elementer i den linkede liste. Og det er dybest set, hvad der lille klat af tekst der opsummerer. Og lad os tage et kig på det som et diagram. 

Så her er vores linkede liste. Det samtidigt indeholder fire elementer. Og mere perfekt her er vores stak indeholder fire elementer. Og lad os sige, at vi nu ønsker at skubbe en ny post på denne stak. Og vi ønsker at skubbe en ny post, hvis data værdi 12. Nå, hvad skal vi gøre? Nå først vil vi malloc plads, dynamisk allokere plads til en ny node. Og selvfølgelig umiddelbart efter Vi foretage et opkald til malloc vi altid Sørg for at tjekke for null, for hvis vi fik nul tilbage der var en slags problem. Vi ønsker ikke at dereference at null pointer eller du vil lide en seg fejl. Det er ikke godt. Så vi har malloced for knuden. Vi vil antage, at vi har haft succes her. Vi kommer til at sætte 12 ind datafeltet for denne node. Nu kan du huske hvilke af vores pejlemærker flytter næste så vi ikke bryder kæden? Vi har et par muligheder her, men den eneste, der kommer til at være sikker er at sætte nyheder næste pointer til punkt til den gamle leder af listen eller hvad vil snart være den gamle leder af listen. Og nu, at alle vores elementer er lænket sammen, Vi kan bare flytte listen til at pege til det samme sted, som nye gør. Og vi har nu effektivt skubbet en nyt element på forsiden af ​​stablen. 

Til pop vi ønsker blot at slette det første element. Og så dybest set, hvad vi har at gøre her, godt vi nødt til at finde det andet element. Til sidst, som vil blive den nye hovedet efter vi sletter den første. Så vi bare nødt til at starte fra begyndelsen, flytte en fremad. Når vi har fået fat på en foran hvor vi i øjeblikket er vi kan slette den første sikkert og så kan vi bare flytte hovedet til at pege på, hvad der var den anden periode og derefter nu er det første, efter at node er blevet slettet. 

Så igen, at tage et kig på det som et diagram, vi vil nu pop en element ud af denne stak. Så hvad gør vi? Nå vi først kommer til at skabe en ny pointer, der kommer til at pege på det samme sted som leder. Vi kommer til at flytte det en position frem ved at sige Trav ligemænd trav næste for eksempel, som ville fremme trav pointer én position fremad. Nu hvor vi har fået en hold på det første element gennem markøren kaldet listen, og andet element gennem en pegepind kaldes trav, kan vi roligt slette det første element fra stakken uden at miste resten af kæden, fordi vi har en måde at henvise til det andet element sende ved hjælp af pointer kaldte trav. 

Så nu kan vi frigøre denne node. Vi kan frigøre listen. Og så alt vi skal gøre nu, er flytte listen til punkt til det samme sted at trav gør, og vi er en slags tilbage hvor vi startede, før vi pressede 12 på i første omgang, højre. Dette er præcis, hvor vi var. Vi havde denne fire element stak. Vi har tilføjet en femtedel. Vi pressede en femtedel element, og så vi dukkede der senest yderligere element tilbage fra. 

Det er virkelig temmelig meget alt hvad der er at stakke. Du kan implementere dem som arrays. Du kan implementere dem som hægtede lister. Der er naturligvis andre måder at gennemføre dem så godt. Dybest set årsagen til at vi ville bruge stakke er at vedligeholde data på en sådan måde at den mest nylig tilføjet element er den første ting, vi er lyst til at komme tilbage. Jeg er Doug Lloyd, det er CS50.