Что такое стек в программировании

Что такое стек

Стек — это вид структуры данных, в котором элементы упорядочены и добавление или удаление элементов происходит с верхней части стека — по принципу «Последним пришел — первым ушел» (LIFO). Реализовать стек можно, например, С, JavaScript, С++, Java, Python, Lisp или C#.

Как работает стек

Визуально это похоже на стопку тарелок. Первую помытую взять сложно, как и находящуюся где-то внутри, проще начать с последней.

Стек придерживается линейной связи, в которой данные располагаются в строгом порядке и нарушить данную последовательность невозможно. Данные, оказавшиеся в стеке последними, должны использоваться первыми.

Четыре основные операции над стеком:

• push — добавление элемента
• pop — удаление верхнего элемента
• isEmpty — проверка стека на наличие в нем элементов
• peek — возвращение последнего элемента, не удаляя его.

Разновидности стеков

Существует несколько видов стека:

• Стек вызовов: область памяти, в которой хранится информация о точках перехода между элементами программного кода. Например: скрипт вызывает функцию, интерпретатор записывает ее в стек вызовов. Любые функции, вызванные этой функцией, добавляются в стек и выполняются по очереди. Когда основная функция отработает, интерпретатор извлечет ее из стека вызовов и продолжит выполнять код с того места, где он остановился ранее.
• Стек на основе массива: в этом типе стека элементы хранятся в массиве фиксированного размера, и доступ к ним осуществляется по индексу. Главным недостатком является ограниченность размера массива, что может привести к проблемам с добавлением новых элементов, если стек заполнен. Также этот тип стека может быть неэффективным, если требуется частое добавление и удаление элементов.
• Стек на основе связного списка: в нем элементы хранятся в связном списке, где каждый элемент содержит указатель на следующий элемент. Этот тип стека позволяет эффективно добавлять и удалять элементы, но может быть менее эффективным при доступе к элементам по индексу. Одним из преимуществ стека на основе связного списка является его динамичность — размер стека может быть изменен в любой момент времени.
• Стек на основе двухсторонней очереди (Deque): в этом случае элементы хранятся в двухсторонней очереди, где элементы могут быть добавлены или удалены с обоих концов.
• Стек на основе дерева: здесь элементы хранятся в дереве, где каждый узел содержит указатель на родительский узел. Этот тип стека может быть полезен для решения задач, связанных с деревьями, таких как обход дерева в глубину.
• Стек на основе кучи (Heap): в этом виде стека элементы хранятся в куче, где каждый элемент имеет приоритет. Этот тип стека может быть полезен для решения задач, связанных с приоритетами, таких как поиск минимального или максимального элемента.

Переполнение стека

Переполнение стека — это ситуация, когда стек заполняется элементами, превышающими его максимальный размер, установленный при создании стека. Когда стек переполняется, он не может больше хранить элементы, и любая попытка добавления нового элемента приведет к ошибке.

Причины переполнения стека

Рекурсия: если функция вызывает саму себя слишком много раз, то каждый новый вызов функции добавляет новый элемент в стек. Если глубина рекурсии слишком большая, то стек может переполниться.

Бесконечный цикл: если в цикле добавляются новые элементы в стек, то если цикл не останавливается, то стек может быстро заполниться.

Неправильно написанный код: некоторые ошибки в коде могут привести к тому, что стек будет заполняться слишком быстро. Например, если функция добавляет элементы в стек, но не удаляет их, то стек будет быстро заполнен.

Недостаточный размер стека: если размер стека недостаточно большой для хранения всех элементов, которые добавляются в него, то стек может переполниться.

Опасности переполнения стека

• Падение программы: переполнение стека может привести к аварийному завершению программы, что может привести к потере данных или другим негативным последствиям.
• Потеря данных: если стек переполнен, то данные, которые не помещаются в стек, могут быть потеряны.
• Уязвимость безопасности: переполнение стека может привести к уязвимостям безопасности, так как злоумышленник может использовать переполнение стека для выполнения вредоносного кода или других опасных действий.
• Непредсказуемое поведение программы: переполнение стека иногда запускает непредсказуемое поведение программы, включая зависание программы или ошибки в работе.

Важно следить за использованием стека и предотвращать его переполнение, например, путем использования итерационных алгоритмов вместо рекурсии и проверки глубины стека.

Реализация стека

Стек может быть выполнен с помощью связанного списка, массива фиксированной длины или динамического массива.

Пример стека на массиве в JavaScript

const arr = []; //Добавляем элементы в массив arr.push("Один"); console.log(arr); // выведет ["Один"] arr.push('Два'); console.log(); // выведет ["Один", "Два"] //Удаляем элемент arr.pop(); console.log(arr); // выведет ["Один"] //Добавим еще один элемент arr.push("Сосиска"); //Отобразим последний элемент, не удаляя его console.log(arr.peek()); // выведет Сосиска //Проверим, пуст ли наш стек console.log(arr.isEmpty()); // выведет false

Пример стека на связанном списке в Python

class Node: def __init__(self, data=None): self.data = data self.next = None class LinkedStack: def __init__(self): self.top = None # Проверим, пуст ли наш стек def is_empty(self): return self.top is None # Добавляем элемент в стек def push(self, item): new_node = Node(item) new_node.next = self.top self.top = new_node # Удаляем элемент из вершины стека и возвращаем его def pop(self): if self.is_empty(): raise Exception("Stack is empty") item = self.top.data self.top = self.top.next return item # Отобразим последний элемент, не удаляя его def peek(self): if self.is_empty(): raise Exception("Stack is empty") return self.top.data

Класс Node представляет узел связанного списка, а класс LinkedStack использует узлы, чтобы создать стек. Каждый узел содержит данные (data) и ссылку на следующий узел (next). При вызове метода push, создается новый узел с переданным элементом, и ссылка на этот узел устанавливается в вершину стека (top). При вызове метода pop, элемент извлекается из вершины стека, и вершина обновляется, чтобы указывать на следующий узел в списке.

Софья Пирогова

автор статей / копирайтер

Вам может также понравиться.

Кто такие свитчеры

27 янв. 2024 г.

Как быстро и правильно гуглить

26 янв. 2024 г.

Что такое стек

Постепенно осваиваем способы организации и хранения данных. Уже было про деревья, попробуем про стеки. Это для тех, кто хочет в будущем серьёзно работать в ИТ: одна из фундаментальных концепций, которая влияет на качество вашего кода, но не касается какого-то конкретного языка программирования.

�� Стек — это одна из структур данных. Структура данных — это то, как хранятся данные: например, связанные списки, деревья, очереди, множества, хеш-таблицы, карты и даже кучи (heap).

Как устроен стек

Стек хранит последовательность данных. Связаны данные так: каждый элемент указывает на тот, который нужно использовать следующим. Это линейная связь — данные идут друг за другом и нужно брать их по очереди. Из середины стека брать нельзя.

�� Главный принцип работы стека — данные, которые попали в стек недавно, используются первыми. Чем раньше попал — тем позже используется. После использования элемент стека исчезает, и верхним становится следующий элемент.

Классический способ объяснения принципов стека звучит так: представьте, что вы моете посуду и складываете одинаковые чистые тарелки стопкой друг на друга. Каждая новая тарелка — это элемент стека, а вы просто добавляете их по одной в стек.

Когда кому-то понадобится тарелка, он не будет брать её снизу или из середины — он возьмёт первую сверху, потом следующую и так далее.

�� Есть структура данных, похожая на стек, — называется очередь, или queue. Если в стеке кто последний пришёл, того первым заберут, то в очереди наоборот: кто раньше пришёл, тот раньше ушёл. Можно представить очередь в магазине: кто раньше её занял, тот первый дошёл до кассы. Очередь — это тоже линейный набор данных, но обрабатывается по-другому.

Стек вызовов

В программировании есть два вида стека — стек вызовов и стек данных.

Когда в программе есть подпрограммы — процедуры и функции, — то компьютеру нужно помнить, где он прервался в основном коде, чтобы выполнить подпрограмму. После выполнения он должен вернуться обратно и продолжить выполнять основной код. При этом если подпрограмма возвращает какие-то данные, то их тоже нужно запомнить и передать в основной код.

Чтобы это реализовать, компьютер использует стек вызовов — специальную область памяти, где хранит данные о точках перехода между фрагментами кода.

Допустим, у нас есть программа, внутри которой есть три функции, причём одна из них внутри вызывает другую. Нарисуем, чтобы было понятнее:

Программа запускается, потом идёт вызов синей функции. Она выполняется, и программа продолжает с того места, где остановилась. Потом выполняется зелёная функция, которая вызывает красную. Пока красная не закончит работу, все остальные ждут. Как только красная закончилась — продолжается зелёная, а после её окончания программа продолжает свою работу с того же места.

А вот как стек помогает это реализовать на практике:

Программа дошла до синей функции, сохранила точку, куда ей вернуться после того, как закончится функция, и если функция вернёт какие-то данные, то программа тоже их получит. Когда синяя функция закончится и программа получит верхний элемент стека, он автоматически исчезнет. Стек снова пустой.

С зелёной функцией всё то же самое — в стек заносится точка возврата, и программа начинает выполнять зелёную функцию. Но внутри неё мы вызываем красную, и вот что происходит:

При вызове красной функции в стек помещается новый элемент с информацией о данных, точке возврата и указанием на следующий элемент. Это значит, что когда красная функция закончит работу, то компьютер возьмёт из стека адрес возврата и вернёт управление снова зелёной функции, а красный элемент исчезнет. Когда и зелёная закончит работу, то компьютер из стека возьмёт новый адрес возврата и продолжит работу со старого места.

Переполнение стека

Почти всегда стек вызовов хранится в оперативной памяти и имеет определённый размер. Если у вас будет много вложенных вызовов или рекурсия с очень большой глубиной вложенности, то может случиться такая ситуация:

• рекурсия всё работает и работает;
• при каждом новом витке рекурсии в стек добавляются новый элемент;
• когда элементов будет слишком много, память закончится, новые элементы некуда будет складывать и произойдёт переполнение стека.

Переполнение — это плохо: данные могут залезать в чужую область памяти и записывать себя вместо прежних данных. Это может привести к сбою в работе других программ или самого компьютера. Ещё таким образом можно внедрить в оперативную память вредоносный код: если программа плохо работает со стеком, можно специально вызвать переполнение и записать в память что-нибудь вредоносное.

Стек данных

Стек данных очень похож на стек вызовов: по сути, это одна большая переменная, похожая на список или массив. Его чаще всего используют для работы с другими сложными типами данных: например, быстрого обхода деревьев, поиска всех возможных маршрутов по графу, — и для анализа разветвлённых однотипных данных.

Стек данных работает по такому же принципу, как и стек вызовов — элемент, который добавили последним, должен использоваться первым.

Что дальше

А дальше поговорим про тип данных под названием «куча». Да, такой есть, и с ним тоже можно эффективно работать. Стей тюнед.

Стек

Стек — одна из основ организации и хранения данных. При этом она напрямую не взаимодействует ни с одним из языков программирования. Стек — это способ формирования структуры данных, а структура — это вариант хранения информации: списков, «веток», схем, множеств, таблиц.

«IT-специалист с нуля» наш лучший курс для старта в IT

Как работает стек

Главная особенность — в последовательном способе хранения. Элементы необходимо брать и использовать только по очереди. В рамках стека работает линейная связь: данные следуют друг за другом в строгом порядке, и нарушать эту последовательность нельзя. Ключевой принцип — информация, попавшая в стек последней по хронологии, должна использоваться первой по очереди. Элемент данных используется, и стек пропадает. Следующим в очереди к использованию становится более ранний по времени попадания элемент.

Визуально это можно сравнить со стопкой тарелок после мытья: они устанавливаются друг на друга. Первую помытую тарелку или тарелку из середины стопки взять проблематично, а в нашем случае — вовсе нельзя. Обратная стеку модель — очередь. Если стек подразумевает использование более новых элементов, то в очереди преимущество — за более старыми.

Профессия / 8 месяцев
IT-специалист с нуля

Попробуйте 9 профессий за 2 месяца и выберите подходящую вам

Разновидности стеков

Стеки можно разделить на две большие группы: стеки вызовов и стеки данных.

Стеки вызовов. Это отдельная область памяти, в которой хранится информация о точках перехода между элементами кода. Этот вариант активно применяется в программировании, когда компьютеру требуется помнить, где произошел разрыв в коде, чтобы выполнить подпрограмму. Выполнив поиск, он вынужден начинать операцию с самого начала. При возвращении данных программой они запоминаются и передаются в основной код.

Работает это следующим образом: происходит запуск программы, вызывается крайняя функция. После ее выполнения программа будет продолжать с места остановки. Появляется новая функция, вызванная изначальной. Она, в свою очередь, вызывает третью функцию, совершающую свое заданное действие.

Стеки данных. У них очень много схожих со стеками вызовов черт. В их основе — одна переменная значительных размеров, которая похожа на массив или список. Используются они при работе с более массивными и разветвленными данными. Но принцип работы схож с классическим — сначала используется более поздний элемент кода.

Переполнение стека

Стеки точно так же расходуют оперативную память компьютера. При выполнении большого количества запросов и методов глубокой погруженности может произойти:

1. безостановочная работа рекурсии;
2. добавление новых элементов в стек после очередного витка рекурсии;
3. переполнение из-за большого количества новых элементов и отсутствия места для их складирования.

Опасность в том, что данные могут появляться в чужой области памяти и занимать место прежних данных. Компьютеру в такой ситуации грозят сбои в работе и даже выход из строя.

Курс для новичков «IT-специалист
с нуля» – разберемся, какая профессия вам подходит, и поможем вам ее освоить

Реализация стека

Стек можно реализовать на массиве, на динамическом массиве и на списке.

Реализация на массиве. Стек состоит из цепи элементов с обозначением [s1…s.top]. s1 — это начальный элемент в очереди, s.top — последний. Если s.top равен нулю, то такой стек считается пустым. Протестировать на наличие пустых элементов можно с помощью команды stackEmpty. Если данные будут сниматься с пустого стека, то это может приводить к ошибке.

Реализация на динамическом массиве. При таком способе исчезает риск выйти за границы массива при выполнении вставки нового элемента: операция push.

Реализация на списке. Для выполнения реализации нужно создать сам список и перечень операций на нем. Добавляться элементы к нему будут через привязку к верхнему — команды head.data (текущий головной элемент) и head.next (добавляемый элемент, который становится головным).

IT-специалист с нуля

Наш лучший курс для старта в IT. За 2 месяца вы пробуете себя в девяти разных профессиях: мобильной и веб-разработке, тестировании, аналитике и даже Data Science — выберите подходящую и сразу освойте ее.

Статьи по теме:

Что такое стек в программировании

Стек в программировании – это абстрактный тип данных, представляющий собой список элементов, организованный по принципу «последний пришел, первый ушел» (LIFO — Last In, First Out). Под этим подразумевается, что последний элемент, добавленный в стек, становится первым кандидатом на удаление. Действия с элементами стека обычно ограничиваются двумя основными операциями: добавлением (push) и удалением (pop) элементов.

Стек, как абстрактная структура данных, абсолютно не привязан к конкретному языку программирования. Его можно реализовать на большинстве из них, будь то Python, C++, Java, JavaScript и другие.

Зачем нужен стек в программировании

Стек является ключевым элементом во многих аспектах программирования. Подробнее рассмотрим некоторые из них:

1. Выполнение функций и подпрограмм: При вызове функций стек используется для сохранения адресов возврата и локальных переменных. Это позволяет возвращаться к правильной точке после завершения работы функции и восстанавливать состояние исполнения.
2. Обратная польская нотация (ОПН): Стеки используются в вычислениях ОПН, которая является распространенным способом записи арифметических и логических выражений без использования скобок.
3. Рекурсия: В рекурсивных функциях стек помогает отслеживать и контролировать глубину рекурсии, сохраняя состояние выполнения при каждом вложенном вызове.
4. Управление памятью: Стек обеспечивает очень простой способ управления памятью. Данные, которые больше не нужны, автоматически удаляются из стека, когда функция или процедура завершается.

Примеры использования стека в программировании

Пример 1: Проверка правильности скобочной последовательности

Пусть задача состоит в том, чтобы проверить, правильно ли в тексте расставлены скобки различных типов: «()», «[]», «<>«. Для решения этой задачи можно использовать стек. Каждый раз, когда встречается открывающая скобка, она добавляется в стек, а когда встречается закрывающая скобка, проверяется, соответствует ли она скобке на вершине стека. Если да, то вершина стека удаляется, если нет, то скобочная последовательность некорректна. Если после просмотра всей строки стек пуст, то последовательность скобок правильна.

Пример 2: Реализация «Отменить действие»

Стеки используются в текстовых редакторах и IDE для реализации функции «Отменить». Каждое действие пользователя добавляется в стек. Когда пользователь нажимает «Отменить», выполняется операция pop, и состояние возвращается к предыдущему.

Эти примеры лишь иллюстрируют многообразие применений стека в программировании. Эта структура данных оказывает огромное влияние на эффективность и функциональность многих программных продуктов.

Пример 3: Обход деревьев и графов

Стек также играет важную роль при обходе деревьев и графов. В обходе в глубину, например, вершины графа добавляются в стек, а затем обрабатываются в порядке, обратном порядку их добавления. Это позволяет удобно осуществлять обход структур данных, следуя «вглубь», прежде чем двигаться «вширь».

Пример 4: Выполнение выражений в Обратной Польской Нотации (ОПН)

Рассмотрим выполнение арифметического выражения, записанного в Обратной Польской Нотации. Допустим, у нас есть выражение «5 3 4 + *». Это ОПН-форма выражения «5 * (3 + 4)». Алгоритм вычисления такого выражения с использованием стека выглядит следующим образом:

1. Читаем символы из выражения слева направо. Если символ — число, добавляем его в стек.
2. Если символ — операция (в данном случае «+» или «*»), извлекаем из стека два верхних элемента, выполняем операцию и помещаем результат обратно в стек.
3. Когда все символы выражения прочитаны, в стеке остается одно число — результат вычисления выражения.

Хотите быть успешным HR-специалистом или IT-рекрутером? Узнавайте о главных трендах и лайфхаках с нашим блогом в Telegram!