Дъг LLOYD: Добре, така от този момент вие сте Вероятно доста запознат с масиви и свързани списъци която е два основни структури от данни с които сме се Говорихме за за поддържане на комплекта данни от подобни типове данни, организирана. Сега ние ще говорим за няколко вариации на масиви и свързани списъци. В това видео отиваме да се говори за стакове. Конкретно, ние ще говорим за структурата на данните, наречена стек. Спомнете си от предишни дискусии за указатели и паметта, че топчето е и име за един сегмент на паметта където статично декларирани memory-- памет, която ви назове, променливи, които ви име, et и така нататък функция рамки които също съществуват кол стека рамки. Така че това е структура комин данни Не комин сегмент на паметта. ДОБРЕ. 

Но това, което е комин? Така че това е доста много просто специален вид структура която поддържа данни по организиран начин. И има две много общи начини за изпълнение стекове използват две структури от данни че вече сте запознати с, масиви и свързани списъци. Какво прави един стек специален, е начин, по който ще се постави информация в стека, а ние пътя премахване на информация от комина. По-специално със стекове правилото е само най- наскоро добавя елемент може да бъде отстранен. 

Така че мисля за това като че ли е комин. Ние сме трупат информация на върха на себе си, и само нещо в горната на купчината могат да бъдат отстранени. Ние не можем да се премахне нещо отдолу защото всичко останало би срине и да падне. Така че ние наистина са изграждането на стека, че тогава ние трябва да се отстранят парче по парче. Поради това ние обикновено наричаме да комин като структура LIFO, издържи, първа изходяща. LIFO, издържи, първа изходяща. 

Така че, тъй като на това ограничение върху как информацията може да се добави и отстранен от комин, там наистина само две неща които можем да направим със стак. Ние можем да бута, която е най- Терминът ние използваме за добавяне нов елемент към върха на стека, или ако топчето не съществува и ние сме го създаде от нулата, създаване на стека на първо място Би било бутане. И тогава се появи, това е нещо като CS Терминът ние използваме, за да се отстрани най-скоро добавен елемент от върха на стека. 

Така че ние ще разгледаме и двете реализации, въз основа както масив и свързан списък на базата. И ние ще се започнем с масив на базата. Така че тук е основната идея на това, което Структурата стека данни на масива основава ще изглежда така. Ние се даде определение на въведените от тук. Вътре на които имаме двама членове или области на структурата. Ние имаме масив. И пак аз съм с помощта на произволна стойност тип данни. 

Така че това би могло да бъде всеки тип данни, инт Чар или някои други данни написали сте създали преди това. Така че ние имаме масив от капацитета размер. Капацитет бъде един паунд дефинирана константа, може би някъде другаде в нашата файл. Така че забележите вече с този конкретен прилагане ние очертаващ себе си като е типично случаят с масиви, които не можем динамично преоразмеряване, където има определен брой Елементи максимална че можем да сложим в нашия стак. В този случай това е елементи капацитет. 

Ние също така да следите на върха на купчината. Какво елемент е най- Наскоро беше добавен в стека? И така, ние следим, че в променлива наречена отгоре. И всичко това бъде пренесена заедно в нов тип данни, наречена стек. И след като сме създали този нов тип данни можем да го третират като всеки друг тип информация. Ние може да обяви стека ите, точно като бихме могли да направим инт х или у Чар. И когато казваме, стека ите, и какво се случва, е да стигнем набор от памет, заделена за нас. 

В този случай капацитет Аз бях очевидно реши е 10, защото аз имам една променлива от тип стак който съдържа две полета изземване. Масивът, в този случай ще да бъде масив от числа какъвто е случаят в повечето от моите примери. И още една целочислена променлива възможност за съхраняване на върха, най Последно добавени елемент към стека. Така че един-единствен пакет от това, което ние Просто определено изглежда по този начин. Това е кутия, съдържаща масив от 10, което ще бъде числа в този случай и в друго число променлива има в зелено за обозначаване на върха на купчината. 

За задаване на върха на стак можем просто да кажем s.top. Ето как можем достъп до поле на структура изземване. s.top е равна на 0 ефективно прави това в нашия стак. Така че отново имаме две операции че можем да се извърши сега. Ние можем да бутнете и ние можем да поп. Нека да започнем с натискане. Отново, бутане е добавянето на нов елемент на върха на купчината. 

Така че това, което ние трябва да направим в този масив базирани изпълнение? Ами като цяло на тласък функция ще да се наложи да приеме указател към стека. Сега вземете втори и мисля за това. Защо искаме да приемем указател към стека? Спомнете си от предишните клипове на променлива обхват и указатели, какво ще се случи, ако ние просто изпраща стак, е по-скоро в като параметър? Какво всъщност ще бъде приет там? Не забравяйте, че ние създаваме копие когато ние го предаде на функция освен ако не използваме указатели. И така, тази функция натиснете нужди да приеме указател към стека така че ние всъщност се променя стека ние възнамеряваме да се промени. 

Другото нещо, натискането вероятно иска да приемам е елемент от данни от тип стойност. В този случай отново, цяло число, че ние ще добавим към върха на стека. Така че ние имаме нашите два параметъра. Какво ще се Сега правя вътре тласък? Ами, просто, ние просто ще добавите този елемент на върха на купчината и след това се променя, когато горната част на топчето е, че е точка, за върхова стойност. Така че това е, което е функция декларация за бутане може да изглежда така в гама-базирани изпълнение. 

Отново това не е трудно и бързо правило че бихте могли да промените това и да има тя варира по различни начини. Може би и е обявен за световно. И така, вие дори не е необходимо за да премине тя е като параметър. Това отново е просто общ случай за натискане. И там са различни начини за неговото прилагане. Но в този случай ни тласък ще отнеме два аргумента, указател към стека и един елемент от данни от тип стойност, число в такъв случай. 

Така че ние обявена ите, ние каза s.top е равна на 0. Сега нека да буташ номер 28 върху купчината. Ами какво означава това? Е момента най-отгоре е 0. И така, това, което е в основата щеше да се случи, е ние ще се придържаме броя 28 в масив място 0. Доста проста, нали, че беше на върха и сега сме добре да тръгвам. И тогава ние трябва да променим това, което горната част на стека ще бъде. Така че следващия път, ние бутнете елемент в, отиваме да я съхранява в масив място, най-вероятно няма 0. Ние не искаме да презапишете това, което ние просто сложи там. И така, ние просто ще се премести на върха на 1. Това вероятно има смисъл. 

Сега, ако искаме да се сложи още един елемент върху купчината, казват ние искаме да прокара 33, и сега ние просто ще отнеме 33 и го сложи под номер местоположение масив 1, и след това да се промени в началото на нашата стека да бъде масив място номер две. Така че, ако следващия път, ние искаме да бутнете елемент към стека, тя ще бъде пусната в населено място масив 2. И нека да направим това още един път. Ще бутнете 19 на разстояние от купчините. Ние ще сложи 19 в населено място масив 2 и промяна на върха на нашия стак да бъде място масив 3 така че ако следващия път, когато Трябва да се направи лицеви сме добре да тръгвам. 

ОК, така че това е бутане в орехова черупка. Какво ще кажете за мак? Така че мак е нещо колега да натискате. Това е начина, по който изтриете данни от комина. И в общи поп нужди да направите следното. Тя трябва да приеме указател към стека, отново в общия случай. В друг случай може да се са декларирали стека в световен мащаб, като в този случай не е нужно да го давате в защото вече има достъп до него като глобална променлива. Но тогава какво друго трябва да направим? Ами ние бяхме увеличаване на върха на стека в бута, така че ние сме най-вероятно ще искате да намалите върха на стека в поп, нали? И след това, разбира се, ние също ще искате да върне стойност, която ние премахваме. Ако ние сме добавяне на елементи, ние искаме за да получите елементи от по-късно, ние вероятно действително Искам да ги съхранява, така че ние не просто да ги изтриете от стека, а след това не се прави нищо с тях. По принцип, ако сме бутане и пръкват тук ние искаме да съхранявате това информация по смислен начин и така тя не прави смисъл просто да го изхвърли. Така че тази функция трябва да Вероятно връща стойност за нас. 

Така че това е, което декларация за поп може да изглежда като там в горния ляв ъгъл. Тази функция връща данни от тип стойност. Отново сме били използване на числа в цялата сграда. И тя приема указател към пакетна свое аргумент или едноличен параметър. И така, какво е поп смяташ да правиш? Да кажем, че искаме да сега поп елемент на разстояние от с. Така че не забравяйте, аз казах, че стакове са последните , първа изходяща, LIFO структури от данни. На кой елемент ще се отделя от стека? Знаете ли, предполагам, 19? Защото ще бъдеш прав. 19 е последният елемент ние добавихме към стека, когато бяхме бутане елементи върху, и така тя ще отиде на първата елемент, който се премахва. Това е като че казахме 28, и След това ще се постави на 33 в началото на това, и ще се постави 19 отгоре на това. Единственият елемент можем да се свали е 19. 

Сега в диаграмата тук, което съм направил е нещо като изтрит 19 от масива. Това не е реално това, което ние ще направим. Ние просто ще натура на преструвам, че не е там. Тя все още е там, в че място в паметта, но ние просто ще го игнорират чрез промяна на върха на купчина ни е от 3-2. Така че, ако ние бяхме досега бутнете още един елемент към стека, тя ще напише над 19. 

Но нека не мине през неприятности на изтриване 19 от комина. Ние можем просто да се преструваме, че не е там. За целите на стека го няма, ако сменяме на върха да бъде 2, вместо 3. Добре, така че е доста много я. Това е всичко, което трябва да направим да поп елемент на разстояние. Да го направим отново. Така че аз съм го маркира в червено тук, за да посочва ние правим друг разговор. Отиваме да направи същото нещо. 

И така, какво ще се случи? Е, ние ще се съхранява 33 в х и отиваме за промяна на върха на купчината 1. Така, че ако бяхме сега, за да прокарат елемент в стека, които сме ще направя точно сега, какво ще се случи се отиваме презаписване масив място номер 1. Така, че на 33, че е нещо като ляво зад които ние просто се престори вече не съществува, ние просто ще да го смажат и постави там, вместо 40. И тогава, разбира се, тъй като ние направихме едно натискане, отиваме и прираста на най-отгоре 1-2 така че, ако ние сега се добавят друг елемент, че ще отидат в масив място номер две. 

Сега свързани списъци са друг начин за осъществяване на купчини. И ако това определение относно екран тук изглежда познато за вас, това е, защото тя изглежда почти точно същото, в действителност, тя почти е точно същата като единично свързан списък, ако си спомняте от нашата дискусия за поединично свързани списъци в друг видеоклип. Единственото ограничение тук е за нас като програмисти, ние не ти е позволено да вмъкнете или изтриете случайно от единично свързан списък които бихме могли да направим по-рано. Само сега можем да вмъкнете и да изтрие от предната или горната част на свързана списък. Това е наистина единствената разлика все пак. Това е друг начин на единично свързан списък. Това е само ограничението подмяна на себе си като програмисти, че той се променя на купчина. 

Правилото тук е да се поддържа винаги указател към главата на свързан списък. Това е, разбира се, а като цяло важно правило първо. За единично свързан списък, така или иначе ви Необходимо е само указател към главата за да има, че веригата да може да отнесе на всеки друг елемент на свързания списък. Но това е особено важната със стак. И така, по принцип сте Ще всъщност искат Този показалец е глобална променлива. Това е най-вероятно ще да бъде още по-лесно по този начин. Така че какви са аналози на бута и поп? Право. Така бутане отново се добавяне нов елемент към стека. В свързан списък, който означава, че ние ще имаме за създаване на нова възлова точка, която сме Ще добавим в списъка свързана, и след това следвайте стъпките внимателни че сме посочили по-рано в поединично свързани списъци, за да го добавите към веригата без да се скъса веригата и загуба или orphaning всеки елементи от свързан списък. И това е в общи линии какво малко петно ​​на текст има обобщава. И нека да разгледаме на него като диаграма. 

Така че тук е нашата свързан списък. Тя едновременно съдържа четири елемента. И по-точно тук е нашата стека, съдържащ четири елемента. И нека да кажем, сега искаме да бутнете нов елемент в този стак. И ние искаме да прокара нов артикул, чиято стойност е 12 данни. Ами какво ще правим? Ами първо отиваме да изчистване пространство, динамично разпредели пространство за нов възел. И разбира се, веднага след ние да осъществите повикване до изчистване ние винаги не забравяйте да проверите за нищожна, защото ако имаме нулев назад Имаше някакъв проблем. Ние не искаме да сочен, че нулевата указател или ще страдат неизправност в сек. Това не е добре. Така че ние сме malloced на възела. Ние ще приемем, че съм имал успех тук. Отиваме да сложи 12 в полето за данни на този възел. Сега искаш да си припомним кои от нашите указатели движи следващата така че ние не се прекъсне веригата? Имаме няколко опции, но тук единственият, който ще бъде в безопасност е да се определят новини, указател към следващия точка до най-стария началото на списъка или това, което скоро ще бъде най- стар шеф на списъка. И сега, че цялата ни елементи са оковани заедно, ние можем просто да се движат списък да посоча на същото място, че нов прави. И ние сега ефективно натисна нов елемент върху предната част на комина. 

За да можем поп просто искам да изтриете, че първият елемент. И така, това, което в общи линии ние трябва да направим тук, и ние трябва да намерим втория елемент. В крайна сметка, която ще се превърне в новия глава, след като изтриете първия. Така че ние просто трябва да се започне от началото, се движат една напред. След като ние имаме дял в една напред от където сме в момента са можем да изтриете първия безопасно и тогава ние можем просто да се движи главата да сочи към това, което беше втори мандат и след това предприятието е първият след това възел е била изтрита. 

Така че отново, като се погледнете при това като диаграма ние Сега искам да се появи на елемент на разстояние от този стак. И така, какво ще правим? Ами ние сме първи ще създадем нова показалка, че ще ходи да сочат към едно и също място като ръководител. Отиваме да го премести с една позиция напред, като казва TRAV равни TRAV следващата например, която ще преминете този, на Trav показалка позиция напред. Сега, ние имаме задръжте върху първия елемент през списъка с показалеца плати и на втори елемент чрез указател, наречен Trav, можем спокойно да изтриете, че първи елемент от стека без да се губи останалата на веригата, защото има начин да се отнесе на втория елемент предаде по пътя на показалка нарича Trav. 

Така че сега можем да освободим този възел. Ние можем да освободим списък. И тогава всичко, което трябва да направя сега е преместите списък с точка на същото място че Trav прави, и ние сме нещо като обратно там, откъдето започнахме преди да избута 12 на първо място, нали. Това е точно там, където бяхме. Имахме този елемент четири стека. Ние добавихме една пета. Ние бутна една пета елемент на, и след това ние показа, че най-скоро добавен елемент обратно на разстояние. 

Това е наистина доста много всичко там е да се комбинира. Можете да ги въведе по масиви. Можете да ги приложи, свързани списъци. Има, разбира се, други начини за тяхното прилагане, както и. Основно причината щяхме да използваме стакове е да поддържа данни по такъв начин, че най-последно добавени елемент е първото нещо, което сме ще искам да се върна. Аз съм Дъг Лойд, това е cs50.