Стеки повсеместно используются в программировании, поскольку они позволяют организовать удобную структуру хранения данных. Это обеспечивает безотказную работу программ и устройств при выполнении последовательности действий. Так, стеки позволяют «откатывать» действия в браузерах или в Photoshop. «РБК Тренды» разбирались, какими бывают и как работают стеки, а также — где и как они используются.
Что такое стек
Стек (от англ. stack — «стопка») — это способ организации данных в памяти компьютера, который соответствует принципу LIFO (англ. last in — first out, «последним пришел — первым вышел»). Таким образом, последний элемент в стеке используется первым, а добавлять новые элементы и удалять их можно только с одного конца, который называется вершиной. Визуально это похоже на горку посуды, колоду карт или игрушечную пирамидку, где, чтобы достать второй сверху предмет, нужно сначала убрать первый. Схему стека описал математик Алан Тьюринг в 1946 году, однако он использовал для нее понятие «burying» (от англ. «захоронение»).
Стеки напрямую не взаимодействуют ни с одним из языков программирования, а просто позволяют сформировать последовательность использования данных. При этом данные могут храниться в различных форматах: списков, «деревьев», схем, множеств, таблиц и т.д.
Элементы из стека берутся и используются только по очереди. Они следуют друг за другом в строгом порядке, и нарушать последовательность нельзя. Когда все элементы стека использованы, он пропадает.
Для работы со стеками используется несколько основных команд:
- push — добавление элемента на вершину стека;
- pop — удаление элемента с вершины;
- top — возвращение элемента на вершину;
- peek — считывание элемента с вершины стека без удаления;
- isEmpty — проверка пустоты стека;
- isFull — проверка заполненности стека;
- size — количество элементов, доступных в стеке;
- change — замена элемента в заданной позиции;
- display — показывает все элементы, доступные в стеке.
Для чего используют стеки
При управлении памятью любой современный компьютер использует стек в качестве основного средства своей работы. Каждая программа, работающая в системе, имеет собственный стек памяти. Подобная организация данных также помогает реализовать вызов функций на компьютерах.
Кроме того, стеки применяются:
- в операциях отмены в текстовых и графических редакторах;
- для отмены действий в браузерах;
- для отмены или повтора операций в базах данных;
- в приложениях искусственного интеллекта, когда нужно выполнить вычисления в обратном порядке;
- для передачи параметров между приложениями и ядром операционной системы.
Какие бывают стеки
Стек вызовов
Стек вызовов (call stack) — это структура данных, которая управляет вызовами функций во время выполнения программы. Когда программа выполняется на компьютере, то он поочередно вызывает разные функции, отвечающие за конкретные действия (подпрограммы). При этом в стеке хранятся данные о вызове функций в виде точек перехода — моментов, когда компьютер прервал выполнение одной функции и перешел к другой. Так, если внутри одной функции вызывается другая, то компьютер ставит на паузу выполнение первой, сохраняет в стеке точку перехода, а затем выполняет вторую. Когда же выполнена последняя функция, компьютер возвращается к первой, а программа продолжает работу с того же места. При этом стек опустошается.
Приведем пример. Допустим, нам нужно приготовить яичницу с беконом на завтрак. Зададим последовательность действий, каждое из которых будет выполняться как функция в стеке в определенной последовательности. Начинаем с добавления бекона, и эта функция будет выполняться первой, а далее описываем последовательность действий. При этом функция добавления специй будет выполняться внутри функции обжаривания бекона.
function fryEggs () {
console.log ("Обжариваем яйца...");
}
function addEggs () {
console.log ("Добавляем яйца...");
fryEggs ();
}
function addSpices () {
console.log ("Добавляем специи...");
addEggs ();
}
function fryBacon () {
console.log ("Обжариваем бекон...");
addSpices ();
}
function addBacon () {
console.log ("Добавляем бекон...");
fryBacon ();
}
addBacon (); // Начинаем готовить яичницу
Стек данных
Стек данных — такая организация структуры, когда можно читать и удалять только последний элемент. Этот вид стеков используют для работы с разветвленными типами данных: деревьями, графами, XML-документами, JSON-объектами и другими.
Например, стек можно применить для обхода деревьев в глубину, чтобы вывести все значения его узлов. Для этого работа начинается с корня, а затем постепенно расширяется на ветви дерева. Каждый пройденный узел (разветвление) добавляется в стек, а при получении значения удаляется из него.
Еще один пример — стек на основе кучи (heap). В нем элементы хранятся в куче, но каждый имеет приоритет. Такой тип применяется в решении задач, связанных с приоритетами, например для поиска минимального или максимального элемента.
Рассмотрим пример реализации стека на основе кучи в языке программирования JavaScript. Память кучи не упорядочена определенным образом, поэтому ссылки (адреса) на объекты в ней (дома) нужно сохранять в стеке. В JavaScript объекты и функции хранятся в куче, а примитивные значения и ссылки — в стеке.
Реализация стека
Существует несколько типов реализации стеков:
- На массиве фиксированной длины. Такой стек состоит из цепи элементов заранее заданного размера, а новые элементы добавляются только к последнему. При выполнении функций может возникнуть риск переполнения и сбоев.
- На динамическом массиве. Для выполнения такого стека в процессе выделяется новый участок памяти большего размера и все копируется туда, что позволяет выполнять вставку нового элемента. При этом операции добавления и удаления можно выполнять как с конца, так и с начала массива.
- На связном списке. Для выполнения этого стека требуется список и перечень операций на нем. Элементы к списку будут добавляться через привязку к первому.
Выбор реализации зависит от задачи. Так, если нужен быстрый доступ к элементам, но сам стек имеет фиксированный размер или меняется редко, то лучше выбрать динамический массив. Однако, когда величина стека заранее неизвестна, то стоит обратиться к связанному списку.
Преимущества и недостатки стеков
Благодаря простоте организации стеки используются повсеместно в администрировании, дизайне, интернет-маркетинге, программировании и разработке. Такая организация данных имеет как преимущества, так и недостатки.
Плюсы стеков:
- простота — это понятная структура данных для широкого спектра приложений;
- эффективность: операции push и pop в стеке могут выполняться постоянно, обеспечивая эффективный доступ к данным;
- использование принципа LIFO, что полезно во многих сценариях, когда требуется постоянно вызывать функции;
- ограниченное потребление памяти, так как в ней хранятся только те элементы, которые помещены в стеки.
Минусы стеков:
- ограниченный доступ к данным по принципу пирамиды;
- возможность переполнения, когда в стек помещается больше элементов, чем он может вместить, что приводит к потере данных;
- отсутствие произвольного доступа к элементам;
- ограниченная емкость.
Переполнение стека
Переполнение стека (stack overflow) — это ситуация, когда он заполняется элементами, превышающими его максимальный размер, установленный при создании. В этом случае стек больше не может хранить элементы, и любая попытка добавления нового вызывает ошибку. Эта ошибка настолько широко распространена, что в честь нее назвали самый популярный сервис вопросов и ответов для IT-специалистов — Stack Overflow.
Чем грозит переполнение стека:
- аварийным завершением программы, которое может привести к потере данных или другим последствиям;
- ошибками в программе, в том числе зависаниям при ее работе;
- собственно, потере данных: те элементы, которые не помещаются в стек, могут быть удалены;
- уязвимостям безопасности: злоумышленники могут использовать переполнение стека для выполнения вредоносного кода или других действий.
Причины переполнения стека:
- рекурсия: когда функция вызывает саму себя слишком много раз, то каждый новый вызов добавляет новый элемент в стек. При слишком большой глубине рекурсии стек может переполниться;
- бесконечный цикл: когда цикл не останавливается при добавлении новых элементов, то стек может быстро заполниться;
- ошибки в коде, которые приводят к слишком быстрому заполнению стека. Такое возможно, когда функция добавляет элементы, но не удаляет их;
- недостаточный размер стека.
При разработке стека нужно учитывать, что в разных языках программирования различаются лимиты на вызовы функций. Так, в Python глубина рекурсии по умолчанию ограничена 1 тыс. вызовов, но ее можно увеличить вручную, а в языках C или C++ этот лимит выше. Кроме того, нужно заранее определить размер стека, так как большие массивы или другие данные в программах могут потребовать дополнительной емкости.
Читайте также: