Даг Lloyd: Добра, так да гэтага моманту вы знаходзіцеся верагодна, даволі добра знаёмыя з масівамі і сувязнымі спісамі які з'яўляецца два асноўных структуры дадзеных мы казалі аб для падтрымання набораў Дадзеныя падобных тыпаў дадзеных арганізаваны. Цяпер мы збіраемся казаць аб некалькіх варыяцый масіваў і звязаных спісаў. У гэтым відэа мы збіраемся казаць пра стэкаў. У прыватнасці, мы збіраемся казаць аб структуры дадзеных, названай стос. Нагадаем, ад папярэдніх абмеркаванняў аб паказальніках і памяці, што стэк таксама Назва для сегмента памяці дзе статычна аб'яўлена memory-- памяці, што вы імя, зменныя, якія вы называеце, і інш Cetera і функцыянальныя кадры, якія мы таксама існуюць кадры стэка выклікаў. Так што гэта структура дадзеных, стэка ня сегмент стэка памяці. ДОБРА. 

Але тое, што стэк? Так што гэта ў значнай ступені проста адмысловы выгляд мадэлі які падтрымлівае дадзеныя ў арганізаваным парадку. І ёсць два вельмі агульныя спосабы для рэалізацыі стэкі з дапамогай двух структур дадзеных што мы ўжо знаёмыя, Масівы і звязаныя спісы. Што робіць стэк спецыяльныя з'яўляецца спосаб, у якім мы ставім інфармацыі ў стэк, і, як мы выдаліць інфармацыю з стэка. У прыватнасці, у штабелях гэтае правіла толькі найбольш нядаўна дадалі элемент можа быць выдалены. 

Так што падумайце аб гэтым, як быццам гэта стэк. Мы кладка інфармацыю на вяршыні сабе, і толькі рэч, на вяршыні палі могуць быць выдаленыя. Мы не можам выдаліць рэч пад таму што ўсё астатняе будзе калапс і зваліцца. Так што мы сапраўды будуем стэк, мы тады павінны выдаліць па частках. З-за гэтага мы звычайна называем да стэку ў якасці мадэлі LIFO, апошні прыйшоў, першы. ЛИФО, апошні прыйшоў, першым сышоў. 

Так з-за гэтага абмежаванні на як можна дадаць інфармацыю і выдаляецца з стэка, там сапраўды толькі дзве рэчы мы можам зрабіць са стэкам. Мы можам націснуць, які з'яўляецца тэрмін, які выкарыстоўваецца для дадання новы элемент у верхняй частцы стэк, або калі стэк не існуе і мы ствараем яго з нуля, стварэнне стэка, у першую чаргу будзе настойваць. А потым поп, гэта свайго роду CS тэрмін, які выкарыстоўваецца для выдалення найбольш нядаўна дададзены элемент з вяршыні стэка. 

Такім чынам, мы будзем глядзець на абедзве рэалізацыі, заснаваныя як масіў і звязаныя спіс, заснаваны. І мы збіраемся пачаць з масівам аснове. Дык вось асноўная ідэя аб тым, што структура дадзеных стэка масіў на аснове будзе выглядаць. У нас ёсць вызначэнне набранага тут. Унутры што ў нас ёсць два члены або поля структуры. У нас ёсць масіў. І зноў я з дапамогай адвольнае тып дадзеных Значэнне. 

Такім чынам, гэта можа быць любы тып дадзеных, INT знак ці некаторыя іншыя дадзеныя увядзіце створанае раней. Таму ў нас ёсць масіў ёмістасцю памеру. Ёмістасць быўшы фунт вызначаецца сталай, магчыма, дзе-то ў нашым файле. Так ужо заўважыць з гэтым прыватнасці Рэалізацыя мы якая абмяжоўвае самі, як правіла, быў у выпадку з масівамі, якія мы не можам змяніць памер дынамічна, дзе ёсць пэўная колькасць максімуму элементы, якія мы можам паставіць у нашым стэку. У дадзеным выпадку гэта элементы ёмістасці. 

Мы таксама адсочваць верхняя частка стэка. Што элементам з'яўляецца самым нядаўна дадаў у стэк? І так мы адсочваем, што ў зменнай называецца верхняй. І ўсё гэта атрымлівае загорнуты разам у новы тып дадзеных, званай стэк. І як толькі вы стварылі мы гэта новы тып дадзеных мы можам разглядаць яго як любы іншы тып дадзеных. Мы можам аб'явіць стэка S, гэтак жа, як мы маглі б зрабіць Int х, або сЬаг у. І калі мы кажам, стэк з, а тое, што адбываецца што мы атрымаем набор ўсталяваць памяць у бок для нас. 

У гэтым выпадку магутнасць Я, мабыць, вырашыў 10, таму што я атрымаў адна пераменная тыпу стэка які змяшчае два полі памятаю. Масіў, у дадзеным выпадку адбываецца быць масівам цэлых лікаў як у выпадку ў большасці маіх прыкладаў. І яшчэ цэлая пераменная здольны захоўваць вяршыні, найбольш нядаўна дадаў элемент стэка. Так адна чарка, што мы проста вызначаецца як выглядае гэта. Гэта акно, якое змяшчае масіў з 10, што будзе цэлыя лікі ў гэтым выпадку і іншы цэлая пераменная існуе ў зялёны для ўказанні вяршыні стэка. 

Каб ўсталяваць у верхняй частцы Стэк мы проста кажам s.top. Вось як мы доступ да поля структуры водгуку. s.top роўны 0 эфектыўна робіць гэта на наш стэк. Такім чынам, яшчэ раз мы маем дзве аперацыі што мы можам выканаць у цяперашні час. Мы можам націснуць, і мы можам поп-музыкі. Давайце пачнем з штуршка. Зноў жа, націснуўшы дадае новы Элемент да вяршыні стэка. 

Так што мы павінны зрабіць у гэты масіў рэалізацыя на аснове? Ну ў агульным, функцыя проталківанія збіраецца мець патрэбу, каб прыняць паказальнік на стэк. Зараз вазьміце другі і думаць пра гэта. Чаму мы хацелі б прыняць паказальнік на стэк? Нагадаем, ад папярэдніх відэа на Пераменная маштабы і паказальнікі, што адбудзецца, калі мы толькі што адправіў стэк, S, а ў якасці параметру? Што будзе на самой справе прайшло там? Памятаеце мы ствараем копію калі мы перадаць яго ў функцыю калі мы не выкарыстоўваць паказальнікі. І таму гэтая функцыя штурхаць патрэбы прымаць паказальнік на стэк так што мы на самай справе змены стэк мы маем намер змяніць. 

Іншая справа, штуршок, верагодна, хоча, каб прыняць гэта элемент дадзеных значэнне тыпу. У гэтым выпадку, зноў жа, цэлы лік, мы збіраемся дадаць да вяршыні стэка. Такім чынам, мы атрымалі нашы два параметру. Што мы збіраемся Цяпер зрабіць ўнутры штуршок? Ну, проста, мы проста збіраемся дадаць гэты элемент у верхняй частцы стэка а затым змяніць дзе верх стэк, што S кропка верхняе значэнне. Так што гэта тое, што функцыя дэкларацыя штуршок можа выглядаць у на аснове масіва рэалізацыя. 

Зноў жа, гэта не жорсткі і хуткі правіла што вы маглі б змяніць гэта, і ёсць гэта вар'іраваць рознымі спосабамі. Магчыма, ёй аб'яўлена на глабальным узроўні. І таму вы нават не трэба прайсці гэта ў якасці параметру. Гэта зноў толькі агульны выпадак штуршок. І ёсць розныя спосабы яго рэалізацыі. Але ў гэтым выпадку наша штуршок збіраецца прыняць два аргументу, паказальнік на стэк і элемент дадзеных тыпу значэння, цэлага у гэтым выпадку. 

Такім чынам, мы заявілі з, мы сказаў s.top роўная 0. Зараз давайце штурхаць № 28 у стэк. Ну што гэта значыць? Ну ў цяперашні час Вяршыня стэка 0. І так, што ў асноўным адбудзецца гэта мы збіраемся прытрымлівацца колькасць 28 у масіў размяшчэння 0. Даволі проста, ці не так, што быў галоўным, і зараз мы добра ісці. І тады мы павінны змяніць тое, што верхняя частка стэка будзе. Так што ў наступны раз мы націскаем элемент у, мы збіраемся захоўваць яго ў Размяшчэнне масіў, верагодна, не 0. Мы не хочам, каб перапісаць што мы проста паставіць там. І таму мы будзем проста перанесьці зверху 1. Гэта, верагодна, мае сэнс. 

Цяпер, калі мы хочам, каб паставіць яшчэ адзін элемент стэк, што мы хочам, каб падштурхнуць 33, а зараз мы проста зойме 33 і паклаў яго на масіў колькасці месцазнаходжання 1, а затым змяніць у верхняй частцы нашага стэк, каб быць масіў размяшчэнне нумар два. Так што, калі ў наступны раз мы хочам, каб націснуць элемент у стэк, ён будзе пакласці ў вочка масіва 2. І давайце зробім гэта яшчэ раз. Мы штурхаць 19 ад стэкаў. Мы пакладзем 19 ў месцы масіва 2 і змяніць у верхняй частцы нашага стэка быць месца масіў 3 так што калі ў наступны раз мы трэба зрабіць штуршок, мы добра ісці. 

ОК, так што штурхае ў двух словах. Што пра выскокваюць? Так поппинг з'яўляецца свайго роду аналаг націску. Гэта тое, як мы выдаліць дадзеныя з стэка. І наогул патрэбаў поп зрабіць наступнае. Ён павінен прыняць паказальнік на стэк, зноў у агульным выпадку. У некаторых іншых выпадках вы маглі заявілі стэк ў глабальным маштабе, У гэтым выпадку вам не трэба, каб перадаць яго У таму што ён ужо мае доступ да яго як глабальная пераменная. Але тады, што яшчэ трэба зрабіць? Ну, мы былі павялічваючы верхняя частка стэка ў штуршок, так што мы, верагодна, захочуць для памяншэння верхняй частцы стэка ў поп-музыкі, ці не так? І тады, вядома, мы таксама збіраемся хацець каб вярнуць значэнне, што мы выдаліць. Калі мы дадаем элементы, мы хочам каб атрымаць элементы з пазней, мы, верагодна, на самай справе хочаце захаваць іх, каб мы не проста выдаляць іх з стэк, а затым нічога не рабіць з імі. Наогул, калі мы штурхаючыся і з'яўляюцца тут мы хочам, каб захаваць гэта Інфармацыя асэнсавана і так не робіць сэнс толькі выкінуць яго. Так гэтая функцыя павінна верагодна, вяртаць значэнне для нас. 

Так што гэта тое, што дэкларацыю для поп можа выглядаць там у верхнім левым куце. Гэтая функцыя вяртае Дадзеныя значэння тыпу. Зноў мы выкарыстоўвалі цэлыя ўсім. І ён прымае паказальнік на стэк, як яго адзінага аргументу або адзіным параметрам. Так што поп збіраецеся рабіць? Скажам, мы хочам, каб у цяперашні час поп элемент прэч с. Так што памятаеце, я сказаў, што стэкі ў мінулым у, першыя з ЛИФО, структур дадзеных. Які элемент будзе быць выдаленыя з стэка? Вы здагадаліся 19? Таму што вы былі б правы. 19 быў апошні элемент, мы дадалі да стэк, калі мы штурхалі элементы на, і так што гэта на першы элемент, які атрымлівае выдаленыя. Гэта як калі б мы сказалі, 28, і Затым пакласці 33 на ім, і пакласці 19 на вяршыні, што. Адзіны элемент, мы можам зняць гэта 19. 

Зараз у дыяграме тут, што я зрабіў з'яўляецца свайго роду выдаленыя 19 з масіва. Гэта на самай справе не тое, што мы збіраемся зрабіць. Мы проста збіраемся роду з прыкінуцца, што гэта не існуе. Ён па-ранейшаму там, у што вочка памяці, але мы толькі збіраемся ігнараваць шляхам змены верхняй частцы стэка нашай ад таго, з 3 па 2. Так што, калі мы павінны былі падштурхнуць Цяпер іншы элемент у стэк, было б больш пісаць 19. 

Але давайце не будзем прайсці праз цяжкасці выдалення 19 з чаркі. Мы можам толькі рабіць выгляд, што не існуе. Для мэт стэка яго няма, калі Мы змяніць верхнюю быць 2 замест 3. Добра, так што гэта было даволі шмат яго. Гэта ўсё, што нам трэба зрабіць, поп элемент выключаны. Давайце зробім гэта зноў. Так я вылучыў яго чырвоным тут, каб паказваюць, што мы робім яшчэ адзін званок. Мы збіраемся зрабіць тое ж самае. 

Так што ж адбываецца далей? Ну, мы збіраемся захоўваць 33 х, і мы збіраемся змяніць вяршыні стэка 1. Так што, калі мы былі цяпер выпхнуць элемент у стэк, які мы знаходзімся збіраецца зрабіць прама цяпер, што адбудзецца з'яўляецца мы збіраемся перазапісу Масіў месца № 1. Так што 33, што было свайго роду пакінулі за што мы толькі рабілі выгляд, не існуе больш, мы толькі збіраемся калашмаціць яго і пакласці 40 там замест. І тады, вядома, Так як мы зрабілі штуршок, мы збіраемся, каб павялічыць Вяршыня стэка ад 1 да 2 так што калі мы цяпер дадаць іншы элемент гэта будзе перайсці ў масіў месцазнаходжання нумар два. 

Цяпер, звязаныя спісы іншы спосаб рэалізацыі стэкаў. І калі гэта вызначэнне на Экран тут выглядае знаёмым для вас, гэта таму, што ён выглядае амаль сапраўды гэтак жа, па сутнасці, гэта ў значнай ступені з'яўляецца менавіта гэтак жа, як аднаразова звязанага спісу, калі вы памятаеце з нашага абмеркавання односвязанны спісы ў іншым відэа. Адзінае абмежаванне тут для нас, як праграмістаў, мы не дазволілі ўставіць або выдаліць выпадкова ад аднакратна звязанага спісу якія мы маглі б зрабіць раней. Толькі цяпер мы можам ўстаўляць і выдаляць з пярэдняя або верхняя звязаны Спіс. Гэта сапраўды толькі Розніца ж. Гэта ў адваротным выпадку аднакратна звязаны спіс. Гэта толькі абмежаванне замена на сябе як праграмісты, што змяняе яго ў чарку. 

Правіла тут заўсёды падтрымліваць паказальнік на галаву звязанага спісу. Гэта, вядома, у агульным важнае правіла ў першую чаргу. Для односвязанны спіс у любым выпадку вам трэба толькі паказальнік на галаву для таго, каб мець, што ланцужок павінна быць у стане звярнуцца да кожнага іншага элемента у звязаным спісе. Але гэта прыватнасці, Важна са стэкам. І так наогул вы адбываецца на самай справе хочуць гэты паказальнік, каб быць глабальнай зменнай. Гэта, верагодна, будзе яшчэ прасцей. Так якія аналагі штуршок і поп? Права. Так штурхае зноў дадае новы элемент у стэк. У звязаным спісе азначае, што мы будзем мець каб стварыць новы вузел, што мы збіраемся дадаць у звязаным спісе, і вынікайце асцярожныя крокі што мы прыводзім раней паасобку, звязаных спісаў, каб дадаць яго ў ланцуг без разрыву ланцугу і страты або сіротамі любы элементы звязанага спісу. І гэта ў асноўным тое, што, што трохі кропля тэксту ёсць абагульняе. І давайце зірнем ў яго ў выглядзе дыяграмы. 

Дык вось наш звязаны спіс. Гэта адначасова змяшчае чатыры элемента. І яшчэ выдатна Вось наш стэк, які змяшчае чатыры элемента. І давайце казаць, што мы цяпер хочам націснуць новы элемент на гэтым стэку. І мы хочам, каб падштурхнуць новае Пункт чые дадзеныя значэнне 12. Ну, што мы будзем рабіць? Ну па-першае, мы збіраемся Таноса прастору, дынамічна вылучыць месца для новага вузла. І, вядома, адразу ж пасля мы зрабіць выклік Таноса мы заўсёды пераканайцеся, што для праверкі нуль, таму што, калі мы атрымалі нулявы таму была нейкая праблема. Мы не хочам, каб разнаймення NULL гэтым паказальнік ці вы будзеце пакутаваць няспраўнасць SEG. Гэта не добра. Такім чынам, мы malloced вузла. Мы будзем лічыць, што мы мелі поспех тут. Мы збіраемся паставіць 12 у поле дадзеных гэтага вузла. Цяпер вы можаце ўспомніць, якія з нашых паказальнікаў рухаецца побач, таму мы не разарваць ланцуг? У нас ёсць некалькі варыянтаў, але тут адзінае, што адбываецца, каб быць бяспечным гэта ўсталяваць навіна наступная паказальнік кропка ў старым чале спісу або тое, што хутка будзе стары галава спісу. І цяпер, калі ўсе нашы элементы злучаныя адзін з адным, мы можам проста перайсці спіс, каб паказаць у тое ж месца, што новы робіць. І мы ў цяперашні час эфектыўна штурхнуў Новы элемент на пярэдняй частцы стэка. 

Каб вылучыць Мы проста хочам выдаліць гэта першы элемент. І так у асноўным тое, што мы павінны зрабіць тут, а мы павінны знайсці другі элемент. У рэшце рэшт, што стане новым галаву пасля таго як мы выдаліць першы. Так што мы проста павінны пачаць з пачатак, рух на адну пазіцыю наперад. Пасля таго, як мы атрымалі правесці на адным наперад, дзе мы ў цяперашні час мы можам выдаліць першы бяспечна і тады мы можам проста перанесьці галаву паказаць на тое, што быў Другі член, а затым у цяперашні час першы пасля гэтага Вузел быў выдалены. 

Такім чынам, яшчэ раз, зірнуць на яго як на дыяграме мы Цяпер хачу, каб поп элемент з гэтага стэка. Дык што ж нам рабіць? Ну вы ў першую чаргу мы збіраемся стварыць новы паказальнік, які збіраецца каб паказаць на тым жа месцы, у галаве. Мы збіраемся, каб перанесьці яго на адну пазіцыю наперад, кажучы TRAV роўных TRAV побач, напрыклад, што будзе прасоўваць паказальнік траву адзін Становішча наперад. Цяпер, калі мы атрымалі правесці на першым элеменце праз паказальнік называецца спісу, а Другі элемент з дапамогай паказальніка называецца Траў, мы можам бяспечна выдаліць, што Першы элемент з стэка без страты астатніх ланцуга, таму што мы ёсць спосаб спаслацца на другі элемент наперад па шляху паказальнік называецца TRAV. 

Так што цяпер мы можам вызваліць гэты вузел. Мы можам вызваліць спіс. І тады ўсё, што мы павінны зрабіць цяпер, гэта рухацца спіс кропкі ў тое ж месца што робіць Trav, і мы накшталт таму дзе мы пачалі, перш чым мы штурхнуў 12 на, у першую чаргу, правільна. Гэта дакладна, дзе мы былі. У нас быў гэты стэк чатырох элементаў. Мы дадалі пяты. Мы штурхнуў пятую элемент на, і затым мы выскачыў, што ў апошні час дадаў элемент адступіць. 

Гэта сапраўды вельмі шмат усё, што ёсць у стэкі. Вы можаце рэалізаваць іх у выглядзе масіваў. Вы можаце рэалізаваць іх у выглядзе звязаных спісаў. Ёсць, вядома, і іншыя спосабы іх рэалізацыі, а таксама. У асноўным па гэтай прычыне мы павінны выкарыстоўваць стэкі з'яўляецца падтрыманне дадзеных такім чынам, што ў апошні час дадаў элемент гэта першае, што мы захочуць вярнуцца. Я Дуг Лойд, гэта CS50.