Даг Ллоид: У реду, тако да у овом тренутку си вероватно прилично познат са низовима и повезаних листи која је дво примарна структуре података које смо говорио о за одржавање скупова података сличних типова података у организацији. Сада ћемо да разговарамо о неколико варијација о низовима и повезаних листи. У овом видеу ћемо да разговарамо о гомиле. Конкретно ћемо да причамо о структури података под називом гомилу. Подсетимо из претходних дискусија о тројкама и меморије, да стек је такође наме фор сегмент меморије где статички проглашен мемори-- меморија која вас наме, варијабле које си, и тако даље и функција оквири који смо такође Цалл Стацк оквири постоје. Дакле, ово је структура података стог не стек сегмент меморије. ОК. 

Али шта је гомила? Дакле, то је прилично само посебна врста структуре која одржава податке на организован начин. А ту је и два веома најчешћа начина за имплементацију стацкс користећи два структуре података да смо већ упознати са, низови и повезане листе. Оно што чини посебним је гомила Начин на који смо ставили информације у стек, и ве начин уклонили информације из стека. Посебно са книгохранилисе правило је само највише недавно додали елемент се може уклонити. 

Дакле, размислите о томе као да је то гомила. Ми смо пилинг информације на врху себе, и само је ствар на врх шипа може бити уклоњена. Ми не можете да уклоните ствар испод јер све остало би колапс и падне. Тако да заиста градимо стек који онда морамо да уклонимо комад по комад. Због тога смо обично односи на гомили као ЛИФО структуре, ласт ин, фирст оут. ЛИФО, траје у, први напоље. 

Дакле, због овог ограничења како се информација може дода у и уклоњени из стека, ту стварно само две ствари које можемо да урадимо са стека. Можемо пусх, што је термин који користимо за додавање нови елемент врху стацк, или ако стек не постоји а ми га ствара од нуле, стварање стек на првом месту било би гурање. А онда поп, то је врста ЦС термин који користимо за уклањање недавно додаје елемент са врха стека. 

Дакле, идемо да погледамо како имплементације, како низ заснива и повезана листа заснива. И идемо у почети са низом заснован. Дакле, овде је основна идеја о томе шта структура стек подаци низ заснива би изгледала. Овде имамо дефиницију откуцани. Унутар тога имамо два члана или поља конструкције. Имамо низ. И опет сам користећи произвољно тип података вредности. 

Дакле, ово може бити било која врста података, инт цхар или неки други подаци типе сте претходно створили. Дакле, имамо читав низ величине капацитета. Капацитет се фунта дефинисана константа, можда негде другде у нашем досијеу. Тако приметити већ са овим Имплементација смо скакутати сами као што је типично случај са низовима, што не можемо динамички величину, где има одређени број елемената максимално да можемо ставити у нашим стек. У овом случају то је елементе капацитета. 

Такође пратити врх стека. Шта елемент је највише Недавно је додао да стека? И тако смо пратити да у варијабилном зове врху. И све то бива умотана заједно у нови тип података се зове стек. А када смо створили Овај нови тип података можемо да га третирају као било који други тип података. Можемо да прогласи стека а, као и можемо да урадимо инт к, и или цхар. А када кажемо стацк а, и шта се дешава је добијамо скуп меморија издвојено за нас. 

У овом случају својству Ја очигледно одлучио сам је 10 јер имам једна променљива типа стека који садржи два поља се сетим. Низ, у овом случају иде да се низ целих бројева као што је случај у већини мојих примера. И још једна цео променљива способан за складиштење врх, најскорије додао елемент стека. Дакле, једна гомила оно што смо Само дефинисан изгледа овако. То је кутија низ од 10 ста ће бити цели бројеви у овом случају и још један цео променљива постоји у зелено да укаже на врх стека. 

Да бисте подесили врху стек смо управо рекли с.топ. Тако смо приступили поље структуре опозива. с.топ једнако ефикасно 0 да ли то наше стека. Дакле, опет имамо двије операције да можемо сада обавља. Можемо да гура и можемо поп. Почнимо са притиском. Опет, гурајући се додаје нова елеменат на врх стека. 

Дакле, шта треба да радимо у Овај низ примена заснована? Па у Генералном Пусх функција ће да треба да прихвате поинтер на стек. Сада одвојите пар секунди и размислите о томе. Зашто бисмо желели да прихвате показивач на стек? Подсетимо из претходних видеа на променљива обим и показивачи, шта би се десило ако бисмо послали стек, с прилично се као параметар? Шта би заправо бити донет тамо? Не заборавите да правите копије када смо га прећи на функцији осим ако користимо савете. И тако ова функција пусх потребе да прихвати показивач на стек тако да смо у ствари мењамо стек намеравамо да се мења. 

Друга ствар Пусх вероватно жели да прихвати је елемент података типа вредности. У овом случају, опет, један цео број који ћемо додати на врх стека. Дакле, имамо наша два параметра. Шта ћемо сада унутар пусх? Па, једноставно, ми ћемо само да додам тај елемент на врх стека а затим промените при ему је врх стацк је, да с дот топ вредност. Дакле, ово је оно функција декларација за пусх може изгледати као у Арраи-басед спровођење. 

Опет ово није тешко и брзо правило да промените ово и имају он варира на различите начине. Можда ова је проглашен глобално. И тако да ни не треба да прође да је као параметар. Ово је опет само генералан случај за пусх. И постоје различити начина да га спроведе. Али у овом случају наше Пусх ће узети два аргумента, показивач на стек и елемент података типа интегер вредности, у овом случају. 

Тако смо прогласили с, ми рекао је с.топ износи 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 тако да ако сада додати други елемент да ће иду у арраи локацију број два. 

Сада повезане листе су још један начин да се спроведе гомиле. А ако ове дефиниције на Екран овде изгледа познато, то је зато што скоро изгледа исто, у ствари, то прилично је тачно исто као појединачно повезане листе, ако се сећате из наше расправе о појединачно повезана листе у другом видеу. Једино ограничење овде је за нас као програмери, да не смемо да убаците или брисање случајно из појединачно повезане листе које смо раније могли да урадимо. Ми тек сада можемо убацити и брисање из предњи или врха повезан листа. То је заиста једини Разлика ипак. Ово је иначе појединачно повезана листа. То је само ограничење замена на себе као програмери који мења га у стеку. 

Правило је да се увек одржава Поинтер на челу повезане листе. Ово је наравно генерално Први важно правило. За појединачно повезана листу ионако вам Потребно је само показивач у главу да би имате то ланац бити способан да се односи сваком другом елементу У повезане листе. Али посебно је важно са стека. И тако уопштено да си да заправо желим ово показивач да буде глобални променљива. Вероватно ће бити још лакше. Дакле, шта су аналози притиском и поп? Jel tako. Дакле, гурање поново се додаје нови елемент стека. У повезане листе да знаци да цемо имати да креирате нови чвор да смо ће се додати на листу повезане, и пратите пажљиво кораке које смо претходно наведено у појединачно повезаних листи, додајте га у ланац без прекидања ланца и губитак или било орпханинг елементи повезане листе. И то је у суштини оно што мало грудвица текста тамо сумира. И хајде да погледамо на то у облику дијаграма. 

Дакле, овде је наш повезана листа. То истовремено садржи четири елемента. И још савршено Ово је наш стацк садржи четири елемента. И рецимо да сада желе да пусх нову ставку на овом стек. И ми желимо да гура нове ставка чији се подаци вредност је 12. Па шта ћемо да радимо? Па прво идемо у маллоц простор, динамички доделити простор за нови чвор. И наравно одмах након правимо позив да смо увек маллоц уверите се да проверите нулл, јер ако смо се вратили нула било је нека врста проблема. Ми не желимо да дереференце том нулл показивач или ћете претрпети сег грешку. То није добро. Тако смо маллоцед чвора. Ми ћемо претпоставити да смо имали успеха овде. Идемо на пут 12 у поље податак тог чвора. Сада Да ли се сећате који од наших показивача помера следећу тако да не прекинути ланац? Имамо неколико опција, али овде једини који ће бити безбедан је да постави вијести следећу показивач на указују на старом носилац листе или шта ће ускоро бити стара носилац листе. И сад су сви наши елементи окован заједно, можемо да пређемо листу да укаже на истом месту та нова ради. И сада смо успешно је гурнуо Нови елемент на предњем делу стека. 

Да смо поп само желим да обрисати тај први елемент. И тако у основи оно што морамо да урадимо, и морамо да нађемо други елемент. На крају да ће постати нови глава након што смо избрисали први. Дакле, само треба почети од почетак, померите један напред. Када имамо задржавање на једном напријед гдје смо тренутно јесмо ли можете брисати безбедно први и онда смо да идемо на главу да укаже на оно што је био Други термин а сада је прва после тога чвор је избрисан. 

Дакле, опет, узимајући поглед на то као на дијаграму смо Желим да сада поп елеменат са овог стека. Па шта да радимо? Па прво идемо да се створи нови показивач који ће да укаже на истом месту као и главе. Идемо да га померите једно место напред рекавши Трав једнаки трав следећи на пример, који ће унапредити онај Трав поинтер Положај напред. Сада када имамо држите на првом елементу кроз показивачем назива листе, а Други елемент преко показивача зове Трав, са сигурношћу можемо избрисати да први елемент из стека без губљења остатак ланца јер ми имају начин да упути на други елемент проследите путем од показивач зове Трав. 

Тако да сада можемо ослободити тог чвор. Можемо ослободити листу. И онда све што треба да урадите је сад померите списак тачке на исто место да Трав ради, а ми смо врста бацк где смо почели пре него што смо гурнути 12 на на првом месту, зар не. То је тачно тамо где смо били. Имали смо четири елемента стек. Додали смо једну петину. Гурнуо смо петину елемент на, а онда смо поппед да недавно додао елемент одступи. 

То је заиста прилично све што треба да стацкс. Можете их имплементирати као матрице. Можете их имплементирати као повезаних листи. Постоје, наравно, остало начина да их имплементирају као добро. У основи разлог због којег би користили стацкс је да се одржи података у такав начин да је недавно додао елемент је прва ствар коју смо да желим да се вратим. Ја сам Доуг Ллоид, ово је ЦС50.