ДАГ 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.