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