О стеке простыми словами — для студентов и просто начинающих
Привет, я студент второго курса технического университета. После пропуска нескольких пар программирования по состоянию здоровья, я столкнулся с непониманием таких тем, как «Стек» и «Очередь». Путем проб и ошибок, спустя несколько дней, до меня наконец дошло, что это такое и с чем это едят. Чтобы у вас понимание не заняло столько времени, в данной статье я расскажу о том что такое «Стек», каким образом и на каких примерах я понял что это такое. Если вам понравится, я напишу вторую часть, которая будет затрагивать уже такое понятие, как «Очередь»
Теория
На Википедии определение стека звучит так:
Поэтому первое, на чем бы я хотел заострить внимание, это представление стека в виде вещей из жизни. Первой на ум мне пришла интерпретация в виде стопки книг, где верхняя книга — это вершина.
На самом деле стек можно представить в виде стопки любых предметов будь то стопка листов, тетрадей, рубашек и тому подобное, но пример с книгами я думаю будет самым оптимальным.
Итак, из чего же состоит стек.
Стек состоит из ячеек(в примере — это книги), которые представлены в виде структуры, содержащей какие-либо данные и указатель типа данной структуры на следующий элемент.
Сложно? Не беда, давайте разбираться.
На данной картинке схематично изображен стек. Блок вида «Данные/*next» и есть наша ячейка. *next, как мы видим, указывает на следующий элемент, другими словами указатель *next хранит адрес следующей ячейки. Указатель *TOP указывает на вершину стек, то есть хранит её адрес.
С теорией закончили, перейдем к практике.
Практика
Для начала нам нужно создать структуру, которая будет являться нашей «ячейкой»
Новичкам возможно будет не понятно, зачем наш указатель — типа comp, точнее сказать указатель типа структуры comp. Объясню, для того чтобы указатель *next мог хранить структуру comp, ей нужно обозначить тип этой структуры. Другими словами указать, что будет хранить указатель.
После того как у нас задана «Ячейка», перейдем к созданию функций.
Функции
Функция создания «Стека»/добавления элемента в «Стек»
При добавлении элемента у нас возникнет две ситуации:
- Стек пуст, и нужно создать его
- Стек уже есть и нужно лишь добавить в него новый элемент
Разберем чуть чуть по-подробнее.
Во-первых, почему функция принимает **top, то есть указатель на указатель, для того чтобы вам было наиболее понятно, я оставлю рассмотрение этого вопроса на потом. Во-вторых, по-подробнее поговорим о q->next = *top и о том, что же означает ->.
-> означает то, что грубо говоря, мы заходим в нашу структуру и достаем оттуда элемент этой структуры. В строчке q->next = *top мы из нашей ячейки достаем указатель на следующий элемент *next и заменяем его на указатель, который указывает на вершину стека *top. Другими словами мы проводим связь, от нового элемента к вершине стека. Тут ничего сложного, все как с книгами. Новую книгу мы кладем ровно на вершину стопки, то есть проводим связь от новой книги к вершине стопки книг. После этого новая книга автоматически становится вершиной, так как стек не стопка книг, нам нужно указать, что новый элемент — вершина, для этого пишется: *top = q;.
Функция удаления элемента из «Стека» по данным
Данная функция будет удалять элемент из стека, если число Data ячейки(q->Data) будет равна числу, которое мы сами обозначим.
Здесь могут быть такие варианты:
- Ячейка, которую нам нужно удалить является вершиной стека
- Ячейка, которую нам нужно удалить находится в конце, либо между двумя ячейками
Указатель q в данном случае играет такую же роль, что и указатель в блокноте, он бегает по всему стеку, пока не станет равным NULL(while(q != NULL)), другими словами, пока стек не закончится.
Для лучшего понимания удаления элемента проведем аналогии с уже привычной стопкой книг. Если нам нужно убрать книгу сверху, мы её убираем, а книга под ней становится верхней. Тут то же самое, только в начале мы должны определить, что следующий элемент станет вершиной *top = q->next; и только потом удалить элемент free(q);
Если книга, которую нужно убрать находится между двумя книгами или между книгой и столом, предыдущая книга ляжет на следующую или на стол. Как мы уже поняли, книга у нас-это ячейка, а стол получается это NULL, то есть следующего элемента нет. Получается так же как с книгами, мы обозначаем, что предыдущая ячейка будет связана с последующей prev->next = q->next;, стоит отметить что prev->next может равняться как ячейке, так и нулю, в случае если q->next = NULL, то есть ячейки нет(книга ляжет на стол), после этого мы очищаем ячейку free(q).
Так же стоит отметить, что если не провести данную связь, участок ячеек, который лежит после удаленной ячейки станет недоступным, так как потеряется та самая связь, которая соединяет одну ячейку с другой и данный участок просто затеряется в памяти
Функция вывода данных стека на экран
Самая простая функция:
Здесь я думаю все понятно, хочу сказать лишь то, что q нужно воспринимать как бегунок, он бегает по всем ячейкам от вершины, куда мы его установили вначале: *q = top;, до последнего элемента.
Главная функция
Хорошо, основные функции по работе со стеком мы записали, вызываем.
Посмотрим код:
Вернемся к тому, почему же в функцию мы передавали указатель на указатель вершины. Дело в том, что если бы мы ввели в функцию только указатель на вершину, то «Стек» создавался и изменялся только внутри функции, в главной функции вершина бы как была, так и оставалась NULL. Передавая указатель на указатель мы изменяем вершину *top в главной функции. Получается если функция изменяет стек, нужно передавать в нее вершину указателем на указатель, так у нас было в функции s_push,s_delete_key. В функции s_print «Стек» не должен изменяться, поэтому мы передаем просто указатель на вершину.
Вместо цифр 1,2,3,4,5 можно так-же использовать переменные типа int.
Заключение
Полный код программы:
Так как в стек элементы постоянно добавляются на вершину, выводиться элементы будут в обратном порядке
В заключение хотелось бы поблагодарить за уделенное моей статье время, я очень надеюсь что данный материал помог некоторым начинающим программистам понять, что такое «Стек», как им пользоваться и в дальнейшем у них больше не возникнет проблем. Пишите в комментариях свое мнение, а так же о том, как мне улучшить свои статьи в будущем. Спасибо за внимание.
Что такое стек в программировании
Стек — одна из основ организации и хранения данных. При этом она напрямую не взаимодействует ни с одним из языков программирования. Стек — это способ формирования структуры данных, а структура — это вариант хранения информации: списков, «веток», схем, множеств, таблиц.
«IT-специалист с нуля» наш лучший курс для старта в IT
Как работает стек
Главная особенность — в последовательном способе хранения. Элементы необходимо брать и использовать только по очереди. В рамках стека работает линейная связь: данные следуют друг за другом в строгом порядке, и нарушать эту последовательность нельзя. Ключевой принцип — информация, попавшая в стек последней по хронологии, должна использоваться первой по очереди. Элемент данных используется, и стек пропадает. Следующим в очереди к использованию становится более ранний по времени попадания элемент.
Визуально это можно сравнить со стопкой тарелок после мытья: они устанавливаются друг на друга. Первую помытую тарелку или тарелку из середины стопки взять проблематично, а в нашем случае — вовсе нельзя. Обратная стеку модель — очередь. Если стек подразумевает использование более новых элементов, то в очереди преимущество — за более старыми.
Попробуйте 9 профессий за 2 месяца и выберите подходящую вам
Разновидности стеков
Стеки можно разделить на две большие группы: стеки вызовов и стеки данных.
Стеки вызовов. Это отдельная область памяти, в которой хранится информация о точках перехода между элементами кода. Этот вариант активно применяется в программировании, когда компьютеру требуется помнить, где произошел разрыв в коде, чтобы выполнить подпрограмму. Выполнив поиск, он вынужден начинать операцию с самого начала. При возвращении данных программой они запоминаются и передаются в основной код.
Работает это следующим образом: происходит запуск программы, вызывается крайняя функция. После ее выполнения программа будет продолжать с места остановки. Появляется новая функция, вызванная изначальной. Она, в свою очередь, вызывает третью функцию, совершающую свое заданное действие.
Стеки данных. У них очень много схожих со стеками вызовов черт. В их основе — одна переменная значительных размеров, которая похожа на массив или список. Используются они при работе с более массивными и разветвленными данными. Но принцип работы схож с классическим — сначала используется более поздний элемент кода.
Переполнение стека
Стеки точно так же расходуют оперативную память компьютера. При выполнении большого количества запросов и методов глубокой погруженности может произойти:
- безостановочная работа рекурсии;
- добавление новых элементов в стек после очередного витка рекурсии;
- переполнение из-за большого количества новых элементов и отсутствия места для их складирования.
Опасность в том, что данные могут появляться в чужой области памяти и занимать место прежних данных. Компьютеру в такой ситуации грозят сбои в работе и даже выход из строя.
Курс для новичков «IT-специалист
с нуля» – разберемся, какая профессия вам подходит, и поможем вам ее освоить
Реализация стека
Стек можно реализовать на массиве, на динамическом массиве и на списке.
Реализация на массиве. Стек состоит из цепи элементов с обозначением [s1…s.top]. s1 — это начальный элемент в очереди, s.top — последний. Если s.top равен нулю, то такой стек считается пустым. Протестировать на наличие пустых элементов можно с помощью команды stackEmpty. Если данные будут сниматься с пустого стека, то это может приводить к ошибке.
Реализация на динамическом массиве. При таком способе исчезает риск выйти за границы массива при выполнении вставки нового элемента: операция push.
Реализация на списке. Для выполнения реализации нужно создать сам список и перечень операций на нем. Добавляться элементы к нему будут через привязку к верхнему — команды head.data (текущий головной элемент) и head.next (добавляемый элемент, который становится головным).
Наш лучший курс для старта в IT. За 2 месяца вы пробуете себя в девяти разных профессиях: мобильной и веб-разработке, тестировании, аналитике и даже Data Science — выберите подходящую и сразу освойте ее.
Что такое стек
Постепенно осваиваем способы организации и хранения данных. Уже было про деревья, попробуем про стеки. Это для тех, кто хочет в будущем серьёзно работать в ИТ: одна из фундаментальных концепций, которая влияет на качество вашего кода, но не касается какого-то конкретного языка программирования.
�� Стек — это одна из структур данных. Структура данных — это то, как хранятся данные: например, связанные списки, деревья, очереди, множества, хеш-таблицы, карты и даже кучи (heap).
Как устроен стек
Стек хранит последовательность данных. Связаны данные так: каждый элемент указывает на тот, который нужно использовать следующим. Это линейная связь — данные идут друг за другом и нужно брать их по очереди. Из середины стека брать нельзя.
�� Главный принцип работы стека — данные, которые попали в стек недавно, используются первыми. Чем раньше попал — тем позже используется. После использования элемент стека исчезает, и верхним становится следующий элемент.
Классический способ объяснения принципов стека звучит так: представьте, что вы моете посуду и складываете одинаковые чистые тарелки стопкой друг на друга. Каждая новая тарелка — это элемент стека, а вы просто добавляете их по одной в стек.
Когда кому-то понадобится тарелка, он не будет брать её снизу или из середины — он возьмёт первую сверху, потом следующую и так далее.
�� Есть структура данных, похожая на стек, — называется очередь, или queue. Если в стеке кто последний пришёл, того первым заберут, то в очереди наоборот: кто раньше пришёл, тот раньше ушёл. Можно представить очередь в магазине: кто раньше её занял, тот первый дошёл до кассы. Очередь — это тоже линейный набор данных, но обрабатывается по-другому.
Стек вызовов
В программировании есть два вида стека — стек вызовов и стек данных.
Когда в программе есть подпрограммы — процедуры и функции, — то компьютеру нужно помнить, где он прервался в основном коде, чтобы выполнить подпрограмму. После выполнения он должен вернуться обратно и продолжить выполнять основной код. При этом если подпрограмма возвращает какие-то данные, то их тоже нужно запомнить и передать в основной код.
Чтобы это реализовать, компьютер использует стек вызовов — специальную область памяти, где хранит данные о точках перехода между фрагментами кода.
Допустим, у нас есть программа, внутри которой есть три функции, причём одна из них внутри вызывает другую. Нарисуем, чтобы было понятнее:
Программа запускается, потом идёт вызов синей функции. Она выполняется, и программа продолжает с того места, где остановилась. Потом выполняется зелёная функция, которая вызывает красную. Пока красная не закончит работу, все остальные ждут. Как только красная закончилась — продолжается зелёная, а после её окончания программа продолжает свою работу с того же места.
А вот как стек помогает это реализовать на практике:
Программа дошла до синей функции, сохранила точку, куда ей вернуться после того, как закончится функция, и если функция вернёт какие-то данные, то программа тоже их получит. Когда синяя функция закончится и программа получит верхний элемент стека, он автоматически исчезнет. Стек снова пустой.
С зелёной функцией всё то же самое — в стек заносится точка возврата, и программа начинает выполнять зелёную функцию. Но внутри неё мы вызываем красную, и вот что происходит:
При вызове красной функции в стек помещается новый элемент с информацией о данных, точке возврата и указанием на следующий элемент. Это значит, что когда красная функция закончит работу, то компьютер возьмёт из стека адрес возврата и вернёт управление снова зелёной функции, а красный элемент исчезнет. Когда и зелёная закончит работу, то компьютер из стека возьмёт новый адрес возврата и продолжит работу со старого места.
Переполнение стека
Почти всегда стек вызовов хранится в оперативной памяти и имеет определённый размер. Если у вас будет много вложенных вызовов или рекурсия с очень большой глубиной вложенности, то может случиться такая ситуация:
- рекурсия всё работает и работает;
- при каждом новом витке рекурсии в стек добавляются новый элемент;
- когда элементов будет слишком много, память закончится, новые элементы некуда будет складывать и произойдёт переполнение стека.
Переполнение — это плохо: данные могут залезать в чужую область памяти и записывать себя вместо прежних данных. Это может привести к сбою в работе других программ или самого компьютера. Ещё таким образом можно внедрить в оперативную память вредоносный код: если программа плохо работает со стеком, можно специально вызвать переполнение и записать в память что-нибудь вредоносное.
Стек данных
Стек данных очень похож на стек вызовов: по сути, это одна большая переменная, похожая на список или массив. Его чаще всего используют для работы с другими сложными типами данных: например, быстрого обхода деревьев, поиска всех возможных маршрутов по графу, — и для анализа разветвлённых однотипных данных.
Стек данных работает по такому же принципу, как и стек вызовов — элемент, который добавили последним, должен использоваться первым.
Что дальше
А дальше поговорим про тип данных под названием «куча». Да, такой есть, и с ним тоже можно эффективно работать. Стей тюнед.
Принципы программирования: стек и куча: что это такое?
С каждым годом мы применяем для программирования всё более продвинутые языки, позволяющие писать меньше кода, но получать нужные нам результаты. Однако всё это не проходит даром для разработчиков. Так как программисты всё реже занимаются низкоуровневыми вещами, уже никого не удивляет ситуация, когда разработчик не вполне понимает, что означают такие понятия, как куча и стек. Что это такое, как происходит компиляция на самом деле, в чём разница между динамической и статической типизацией.
К сожалению, некоторые программисты, даже будучи «джуниорами» и работая на реальных проектах, не совсем чётко ориентируются в таких, казалось бы, олдскульных вещах. Именно поэтому в нашей сегодняшней статье мы вспомним, что же это такое — стек и куча, для чего они нужны и где применяются. Несмотря на то, что и стек, и куча связаны с управлением памятью, стратегия и принципы управления кардинально различаются.
Стек — что это такое?
Большое число задач, связанных с обработкой информации, поддаются типизированному решению. В результате совсем неудивительно, что многие из них решаются с помощью специально придуманных методов, терминов и описаний. Среди них нередко можно услышать и такое слово, как стек (стэк). Хоть и звучит этот термин, на первый взгляд, странно и даже сложно, всё намного проще, чем кажется.
Итак, стек — это метод представления однотипных данных в порядке LIFO (Last In — First Out, то бишь, «первый вошел — последний вышел»). Некоторые ассоциируют стек с оружейным магазином для патронов, так как принцип работы схож, и первый вставленный в магазин патрон будет использоваться в последнюю очередь (у термина стек бывают и другие значения, поэтому, если речь идёт не об информационных технологиях, то смысл лучше уточнить).
Стек и простой жизненный пример
Представьте, что на столе в коробке лежит стопка бумажных листов. Чтобы получить доступ к самому нижнему листу, вам нужно достать самый первый лист, потом второй и так далее, пока не доберётесь до последнего. По схожему принципу и устроен стек: чтобы последний элемент стека стал верхним, нужно сначала вытащить все остальные. 
Стек и особенности его работы
Перейдя к компьютерной терминологии, скажем, что стек — это область оперативной памяти, создаваемая для каждого потока. И последний добавленный в стек кусочек памяти и будет первым в очереди, то есть первым на вывод из стека. И каждый раз, когда функцией объявляется переменная, она, прежде всего, добавляется в стек. А когда данная переменная пропадает из нашей области видимости (к примеру, функция заканчивается), эта самая переменная автоматически удаляется из стека. При этом если стековая переменная освобождается, то и область памяти, в свою очередь, становится доступной и свободной для других стековых переменных.
Благодаря природе, которую имеет стек, управление памятью становится весьма простым и логичным для выполнения на центральном процессоре. Это повышает скорость и быстродействие ЦП, и в особенности такое происходит потому, что время цикла обновления байта весьма незначительно (данный байт, скорее всего, привязан к кэшу центрального процессора).
Тем не менее у данной довольно строгой формы управления имеются и свои недостатки. Например, размер стека — это величина фиксированная, в результате чего при превышении лимита памяти, выделенной на стеке, произойдёт переполнение стека. Как правило, размер задаётся во время создания потока, плюс у каждой переменной имеется максимальный размер, который зависит от типа данных. Всё это позволяет ограничивать размеры некоторых переменных (допустим, целочисленных).
Кроме того, это вынуждает объявлять размер более сложных типов данных (к примеру, массивов) заранее, так как стек не позволит потом изменить его. Вдобавок ко всему, переменные, которые расположены на стеке, являются всегда локальными.
Для чего нужен стек?
Главное предназначение стека — решение типовых задач, предусматривающих поддержку последовательности состояний или связанных с инверсионным представлением данных. В компьютерной отрасли стек применяется в аппаратных устройствах (например, в центральном процессоре, как уже было упомянуто выше).
Практически каждый, кто занимался программированием, знает, что без стека невозможна рекурсия, так как при любом повторном входе в функцию требуется сохранение текущего состояния на вершине, причём при каждом выходе из функции, нужно быстро восстанавливать это состояние (как раз наша последовательность LIFO).
Если же копнуть глубже, то можно сказать, что, по сути, весь подход к запуску и выполнению приложений устроен на принципах стека. Не секрет, что прежде чем каждая следующая программа, запущенная из основной, будет выполняться, состояние предыдущей занесётся в стек, чтобы, когда следующая запущенная подпрограмма закончит выполняться, предыдущее приложение продолжило работу с места остановки.
Стеки и операции стека
Если говорить об основных операциях, то стек имеет таковых две: 1. Push — ни что иное, как добавление элемента непосредственно в вершину стека. 2. Pop — извлечение из стека верхнего элемента.
Также, используя стек, иногда выполняют чтение верхнего элемента, не выполняя его извлечение. Для этого предназначена операция peek.
Как организуется стек?
Когда программисты организуют или реализуют стек, они применяют два варианта: 1. Используя массив и переменную, указывающую на ячейку вершины стека. 2. Используя связанные списки.
У этих двух вариантов реализации стека есть и плюсы, и минусы. К примеру, связанные списки считаются более безопасными в плане применения, ведь каждый добавляемый элемент располагается в динамически созданной структуре (раз нет проблем с числом элементов, значит, отсутствуют дырки в безопасности, позволяющие свободно перемещаться в памяти программного приложения). Однако с точки зрения хранения и скорости применения связанные списки не столь эффективны, так как, во-первых, требуют дополнительного места для хранения указателей, во-вторых, разбросаны в памяти и не расположены друг за другом, если сравнивать с массивами.
Подытожим: стек позволяет управлять памятью более эффективно. Однако помните, что если вам потребуется использовать глобальные переменные либо динамические структуры данных, то лучше обратить своё внимание на кучу.
Стек и куча
Куча — хранилище памяти, расположенное в ОЗУ. Оно допускает динамическое выделение памяти и работает не так, как стек. По сути, речь идёт о простом складе для ваших переменных. Когда вы выделяете здесь участок памяти для хранения, к ней можно обращаться как в потоке, так и во всём приложении в целом (именно так и определяются переменные глобального типа). По завершении работы приложения все выделенные участки освобождаются.
Размер кучи задаётся во время запуска приложения, однако, в отличие от того, как работает стек, в куче размер ограничен только физически, что позволяет создавать переменные динамического типа.
Если сравнивать, опять же, с тем, как работает стек, то куча функционирует медленнее, т. к. переменные разбросаны по памяти, а не находятся вверху стека. Тем не менее данный факт не уменьшает важности кучи, и если вам надо работать с глобальными либо динамическими переменными, она больше подходит. Однако управлять памятью тогда должен программист либо сборщик мусора.
Итак, теперь вы знаете и что такое стек, и что такое куча. Это довольно простые знания, больше подходящие для новичков. Если же вас интересуют более серьёзные профессиональные навыки, выбирайте нужный вам курс по программированию в OTUS!