Даг LLOYD: Добро, па од тој момент ти си прилично веројатно запознаени со низи и поврзани листи кој е на два примарни структури на податоци кои ги имаме зборуваше за чување комплети податоците на слични типови на податоци организирани. Сега ние се случува да се зборува за неколку варијации на низи и поврзани листи. Во ова видео, ние си оди да се зборува за Купишта. Конкретно ние се случува да се зборува за податочна структура наречена оџак. Потсетиме од претходните дискусии за покажувачи и меморијата, дека магацинот е, исто така, име за еден сегмент на меморија која статично прогласи memory-- меморија, која ви именува, променливи што ќе го именува, ет натаму и функцијата рамки кои ние, исто така, постои повик магацинот рамки. Значи ова е структура магацинот на податоци Не магацинот сегмент од меморијата. ВО РЕД. 

Но, она што е оџакот? Така, тоа е доста само една посебен вид на структура која го одржува на податоци на организиран начин. И има две многу заеднички начини да се имплементира Купишта користење две структури на податоци дека ние сме веќе запознаени со тоа, низи поврзани листи. Она што го прави посебен е оџакот начинот на кој ние се стави информации во магацинот, а ние начин отстрани информации од оџакот. Особено со Купишта правило е само повеќето неодамна додаде елемент може да се отстрани. 

Па се размислува за тоа како да е оџак. Ние сме натрупување информации на врвот на себе, и само работа на врвот на купот може да се отстрани. Ние не може да се отстрани нешто одоздола бидејќи се друго би да пропадне и да се преврти. Па ние навистина сме изградба на конзола која тогаш ние треба да се отстрани парче по парче. Поради ова, ние најчесто се однесуваат до магацинот како структура LIFO, трае, а прв. LIFO, трае, а прв. 

Па поради ова ограничување на колку информации може да се додаде и отстранети од магацинот, има навистина има само две работи можеме да направиме со оџак. Можеме да им помогнам, што е Терминот се користи за додавање нов елемент на врвот на магацинот, или ако оџакот не постои и ние сме создавање на тоа од нула, создавањето на магацинот на прво место ќе се врши притисок. А потоа поп, тоа е вид на CS термин што го користат за отстранување на неодамна додаде елемент од врвот на магацинот. 

Па ние ќе се погледне во двете имплементации, врз двата низа и поврзани листа базирана. И ние ќе треба да започне со низа базирани. Значи тука е основната идеја на она што структура магацинот на податоци врз основа на низа ќе изгледа. Имаме дефиниција исчука тука. Внатре во тоа имаме два члена или полиња на структурата. Имаме низа. И повторно јас сум со користење на произволна вредност тип на податок. 

Па тоа би можело да биде било кој тип на податоци, int знак или некои други податоци напишете го креиравте претходно. Па ние имаме низа на капацитетот големина. Капацитет да биде една фунта дефинирана константа, можеби некаде на друго место во нашата датотека. Значи забележите веќе со овој имплементација сме одблеснува себеси како беше типично случајот со низи, кои не можеме да се динамички промени големината, каде што има одреден број на елементи максимум што може да се стави во нашите оџак. Во овој случај тоа е елементи капацитет. 

Ние, исто така, да ги пратите на на врвот на магацинот. Она што е на повеќето елементи Неодамна додадени на оџакот? И така ние ги пратите на тоа дека во променлива наречена врвот. И сето ова добива завиткани заедно во нов вид на податоци се нарекува оџак. И еднаш сме создадени овој нов тип на податок можеме да го третираат како било кој друг вид на податоци. Ние да се прогласиме магацинот s, исто како и можеме да направиме int x, или да се усвити y. И кога велиме магацинот ОК, и она што се случува е да добиеме збир на меморија резервирани за нас. 

Во овој случај капацитет Сум очигледно одлучи е 10, бидејќи јас имам една променлива од тип магацинот кој содржи две полиња се потсетиме. Низа, и во овој случај се случува за да се низа од цели броеви како што е случај во повеќето од моите примери. И уште една целобројна променлива способен за чување на врвот, неодамна додадени елемент на магацинот. Па еден единствен магацинот на она што го само што е дефинирано изгледа вака. Тоа е кутија низа од 10 што ќе бидат цели броеви во овој случај и друг целобројни променливи постојат во зелено да се укаже на врвот на магацинот. 

За да го поставите на врвот на магацинот ние само велат s.top. Тоа е како ние да пристапите до поле на една структура на повлекување. s.top изнесува 0 ефикасно го прави ова за нашите оџак. Значи, повторно имаме две операции дека ние може да се изврши веднаш. Можеме да им помогнам и ние може да се појави. Да почнеме со притискање. Повторно, туркајќи се додава нов елемент на врвот на магацинот. 

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

Од друга работа притисни Сигурно сака да го прифати е елемент на податок од типот вредност. Во овој случај, пак, цел број кој ние ќе треба да додадете на врвот на магацинот. Значи имаме нашите два параметри. Што ќе се дојде до сега се направи во внатрешноста на притисни? Па, едноставно, ние сме само ќе додадете тој елемент на врвот на магацинот и потоа да се промени, каде што на врвот на магацинот е, тоа е точка врвот вредност. Значи ова е она функција декларација за притискање Можеби изгледа како во низа-базирана имплементација. 

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

Па ние прогласи, ние рече s.top изнесува 0. Сега ајде да им помогнам на број 28 врз оџакот. Па што значи тоа? И во моментов врвот на магацинот е 0. И така што е во основа ќе се случи е ние ќе треба да се држиме на бројот 28 во низа локација 0. Прилично јасна, во право, дека беше на врвот и сега сме добро да отидевме. И тогаш ние треба да се промени она што на врвот на магацинот ќе биде. Така што следниот пат ние им помогнам на елемент во, ние ќе треба да се чува во Низа локација, веројатно не е 0. Ние не сакаме да ја пребришете она што ние едноставно се стави таму. И така ние само ќе се движат на врвот на 1. Која веројатно има смисла. 

Сега, ако сакаме да се стави уште еден елемент врз оџакот, велат дека ние сакаме да им помогнам на 33, и сега ние сме само ќе земе 33 и го стави во број локација низа 1, а потоа да се промени на врвот на нашата магацинот да биде низа локација број два. Па ако следниот пат кога ние сакаме да притисни елемент врз оџакот, тоа ќе биде ставен во низа локација 2. И ајде да го направи тоа уште еднаш. Ние ќе им помогнам на 19 исклучување на купчиња. Ние ќе ги ставам 19 во низа локација 2 и промена на врвот на нашата магацинот да биде локација низа 3 па ако следниот пат кога треба да се направи притисни ние сме добро да отидевме. 

Добро, така што е туркање во мало. Што е со пукање? Па пукање е вид на договорната страна да врши притисок. Тоа е како ние отстраните податоци од оџакот. И воопшто поп потреби да го направите следново. Тоа треба да го прифати покажувач на магацинот, повторно во општиот случај. Во некој друг случај можеби ќе објавија магацинот на глобално ниво, во кој случај, вие не треба да го помине во затоа што веќе има пристап до него како глобална променлива. Но, тогаш што друго не ни треба да направите? Па бевме ја зголемува на врвот на магацинот во бута, па ние сме веројатно нема да сакате да опаѓа на врвот на магацинот во поп, нели? А потоа се разбира ние сме, исто така, се случува да сакаме да се врати на вредност, која ги отстраниме. Ако ние сме додавање на елементи, сакаме да се добие елементи надвор подоцна, ние веројатно всушност сакате да ги чувате за да можеме не само да ги избришете од магацинот, а потоа да направи ништо со нив. Општо земено, ако ние сме туркање и пукање тука сакаме да го зачувате овој информации во смислен начин и така тоа не се направи смисла само фрлете го. Па оваа функција треба да веројатно се врати на вредност за нас. 

Значи ова е она декларација за поп може да изгледа како таму во горниот лев агол. Оваа функција се враќа податоци од типот вредност. Повторно ние сме биле користење цели броеви во текот на. И прими покажувач кон магацинот како неговиот единствен аргумент или единствен параметар. Значи она што е поп случува да направам? Да речеме дека сакате да го сега pop елемент надвор од ОК. Па се сеќавам, реков дека Купишта се последна , а прв, LIFO структури на податоци. Елемент кој ќе да се отстрани од магацинот? Ми го погоди 19? Затоа што ќе бидете во право. 19 е последниот елемент ние додадена на магацинот кога бевме туркање елементи, и така тоа се случува да на првата елемент кој добива отстранети. Тоа е како што рековме 28, и тогаш ќе стави 33 на врвот на тоа, и ќе стави 19 на врвот на тоа. Единствениот елемент можеме да тргнеме е 19. 

Сега во дијаграмот тука она што го направив е вид на избришани 19 од низата. Тоа не е, всушност, она што се случува да се направи. Ние сме само ќе вид на преправаме дека не е таму. Тоа е уште таму во која локација во меморијата, но ние сме само ќе го игнорираат со промена на врвот на нашата магацинот од тоа да биде 3 на 2. Значи, ако веќе треба да им помогнам сега уште еден елемент врз оџакот, над неа ќе напише 19. 

Но, да не одат низ проблеми на бришење 19 од оџакот. Ние само можеме да се преправаме дека не е таму. За целите на магацинот тоа го нема, ако ние промена на врвот да биде 2, наместо 3. Добро, така што беше доста тоа. Тоа е се што треба да направите да pop-елемент надвор. Да го направиме тоа повторно. Па јас го осветлени во црвено тука за да се укажуваат правиме уште еден повик. Ние ќе треба да го прават истото. 

Значи она што ќе се случи? Па, ние ќе треба да се сместат 33 во x и ние си оди за промена на врвот на магацинот на 1. Така што ако ние требаше сега да им помогнам на елемент во магацинот кои сме случува да се направи токму сега, она што ќе се случи е ние си оди за презапишување Низа локација број 1. Така што 33 беше вид на лево зад дека ние само се преправаше не постои веќе, ние сме само ќе да го clobber и го стави таму, наместо во 40. А потоа, се разбира, бидејќи ние направивме бута, ние ќе треба да прираст врвот на магацинот 1-2 така што ако ние сега додадете уште еден елемент тоа ќе одат во низа локација број два. 

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

Правило е да секогаш одржува Покажувач на главата на поврзани листа. Ова е, се разбира, генерално, важно правило во прв план. За секој случај одделно поврзани листа можете треба само покажувач на главата со цел да го имаат тоа синџирот биде во можност да се однесуваат за секој друг елемент во поврзаните листа. Но тоа е особено важно со магацинот. Па, генерално, ќе бидете случува да се, всушност, сакаат овој покажувачот да биде глобална променлива. Тоа е веројатно нема да се биде уште полесно на тој начин. Па што се аналози на притисни и поп? Право. Па повторно притискање е додавање нов елемент во магацинот. Во поврзани листа која значи дека ние ќе треба да имаат да се создаде нов јазол, дека ние сме ќе се додаде во поврзани листа, и следете ги соодветните внимателни чекори дека ние сме наведено претходно во поврзани листи одделно да го додадете во синџирот без кршење на синџир и губење или orphaning било елементи на поврзани листа. И тоа е во основа она што малку дупка на текст има резимира. И ајде да ги разгледаме на него како на сликата. 

Значи тука е нашата поврзани листа. Тоа истовремено содржи четири елементи. И повеќе совршено тука е нашата магацинот содржи четири елементи. И да речеме сега сакаме да притисни на нова ствар врз ова оџак. И ние сакаме да им помогнам на нов ставка чии податоци вредност е 12. Па што сме ние ќе правиме? Па прво ние ќе треба да Примерок простор, динамички одвои простор за нов јазол. И, се разбира, веднаш по можеме да се јавам во Примерок ние секогаш бидете сигурни дека за да се провери за ништовни, затоа што ако ние доби null назад имаше некој вид на проблем. Ние не сакаме да дереференцира дека ништовен покажувачот или ќе страдаат грешка секунда. Тоа не е добро. Значи ние сме malloced на јазол. Ќе претпоставиме имавме успех тука. Ние ќе треба да се стави во 12 поле податоците на тој јазол. Сега дали се сеќавате кој од нашите совети следно па ние не се скрши синџирот? Имаме неколку опции тука, но само оној кој се случува да биде безбеден е да го поставите покажувачот на следната вести точка на стариот врвот од листата или она што наскоро ќе биде на стариот шеф на листата. И сега, кога сите наши елементи се оковани заедно, ние само може да се движи до точка листа на истото место таа нова прави. И што сега ефикасно турна нов елемент на предниот дел на магацинот. 

Да ги поп само сакаат да се избришете дека првиот елемент. И така во основа она што ние треба да го направите тука, и ние треба да се најде на вториот елемент. На крајот, кој ќе стане нов главата откако ги избришете првиот. Па ние само треба да почне од на почетокот, се движат еден напред. Откако имаме удел во едно напред за тоа каде сме во моментов се што можеме да ги избришете првиот безбедно а потоа ние само може да се движат на главата да се упати на она што беше втор мандат, а потоа сега е прва по што јазол е избришан. 

Значи, повторно, земајќи изглед во тоа како ние дијаграм сега сакате да се појавуваат на елемент надвор од овој магацинот. Значи она што ќе правиме? Па ние сме првата случува да се создаде нов покажувач кој ќе да се упати на истото место како и на главата. Ние ќе треба да се движи еден позиција понапред велејќи trav еднаквите trav следниот пример, кој би однапред еден на trav покажувачот позиција напред. Сега, кога ние го добивме се одржи на првиот елемент преку листа на покажувачот се нарекува, и Вториот елемент преку покажувач кој се нарекува trav, можеме безбедно да ја избришете оваа Првиот елемент од магацинот без губење на одмор од синџирот, бидејќи ние имаат начин да се однесуваат на вториот елемент проследи по пат на покажувач кој се нарекува trav. 

Па сега ние може да се ослободи тој јазол. Ние може да се ослободи листата. И тогаш сите што треба да направите сега е движат листата на точка на истото место trav што го прави тоа, и ние сме вид на врати каде што започна пред ние турна 12 на, на прво место, во право. Ова е токму каде што бевме. Имавме оваа четири елемент оџак. Додадовме една петтина. Ние се наметнува една петтина елемент, а потоа ние појави кои неодамна додаде елемент назад исклучување. 

Тоа е навистина доста сè што постои на купчиња. Можете да ги имплементира како низи. Можете да ги имплементира како се поврзани листи. Постојат, се разбира, и други начини за нивно спроведување, како и. Во основа причината ние ќе го користи купчињата е да се одржи на податоци на таков начин дека неодамна додадени елемент е првото нешто што ние сме ќе сакаат да се вратат. Јас сум Даг Лојд, ова е CS50.