Что такое стек простыми словами?
Автор — Владимир Балун
ex-TeamLead в Яндекс
Непонимание принципов работы стека приводит к ошибкам в коде, проблемам на собеседованиях и сложностям при изучении алгоритмов.
В этой статье разберем, что такое стек, как работает принцип LIFO, какие операции поддерживает эта структура данных и где на самом деле применяется.
В этой статье разберем, что такое стек, как работает принцип LIFO, какие операции поддерживает эта структура данных и где на самом деле применяется.
1. Что такое стек?
Стек — это абстрактная структура данных, которая работает по принципу стопки книг
Представим стол, на котором лежит стопка книг, и что у человека есть только одна рука. В такой ситуации невозможно достать книгу из середины или из нижней части стопки, не разрушив всю конструкцию. Поэтому взаимодействовать можно только с книгой, которая находится сверху.
Если нужно убрать книгу из середины стопки, то снимается верхняя книга. Если требуется добавить новую книгу сверху, она кладется на вершину стопки. Таким образом, работа со стеком ограничена только его вершиной.
Это означает, что:
Если нужно убрать книгу из середины стопки, то снимается верхняя книга. Если требуется добавить новую книгу сверху, она кладется на вершину стопки. Таким образом, работа со стеком ограничена только его вершиной.
Это означает, что:
- добавлять элементы можно только в конец структуры;
- удалять элементы можно только из конца структуры;
- обращаться можно только к последнему элементу.
Такой принцип оперирования данными описывается аббревиатурой LIFO (Last In, First Out) — «тот, кто пришел последним, будет обслужен первым»
Визуализация LIFO — принципа работы с данными
2. Реализация стека
Стек реализовывают либо на основе динамического массива, либо на основе связанного списка.
В случае массива вершиной стека является последний элемент массива:
В случае массива вершиной стека является последний элемент массива:
В случае связанного списка вершиной стека является первый элемент списка — его голова:
3. Основные операции над стеком
Получение вершины стека
Для получения вершины стека:
- в массиве необходимо обратиться к элементу с индексом (size — 1);
- в связанном списке используется указатель на голову списка.
В обоих случаях обращение к верхнему элементу — это константная операция
Добавление элемента
При добавлении элемента в стек на основе массива новый элемент помещается в конец массива.
Представим, что нужно добавить элемент «5». Если в массиве есть свободное место, то операция выполняется быстро: элемент добавляется в массив и обновляется размер.
Представим, что нужно добавить элемент «5». Если в массиве есть свободное место, то операция выполняется быстро: элемент добавляется в массив и обновляется размер.
В динамический массив добавлен новый элемент «5» и обновлен его «size» с 3 до 4
Если места недостаточно, то требуется делать релокацию, или перевыделение памяти. Поэтому асимптотическая сложность вставки в стек, который реализован на основе динамического массива, будет амортизированной константой.
Для стека на основе связанного списка создается новый узел, после чего обновляется указатель на голову списка.
Для стека на основе связанного списка создается новый узел, после чего обновляется указатель на голову списка.
В связанном списке для добавления нового элемента «5» создается новый узел и обновляется «head»
Вставка в начало связанного списка также является константной операцией
Удаление элемента
При удалении элемента из стека на основе массива удаляется последний элемент и уменьшается значение размера массива.
Удаление элемента из динамического массива привело к уменьшению его «size» с 4 до 3
Удаление из конца массива — это константная операция
В случае удаления из связанного списка нужно:
1. Обновить указатель на голову
1. Обновить указатель на голову
2. Перестать ссылаться на прежний первый элемент
Удаление из начала связанного списка — это тоже константная операция
4. Кейсы использования стека в разработке
Одним из наиболее ярких примеров использования стека является аппаратный стек вызовов функций. При вызове функции ее данные — локальные переменные, аргументы и другая служебная информация — помещаются на вершину стека в виде фрейма функции.
Когда выполнение функции завершается и происходит возврат, данные этого фрейма больше не нужны. Верхушка стека «удаляется», и программа возвращается к предыдущему состоянию. При следующем вызове функции ее данные снова помещаются на вершину стека.
Таким образом, стек естественным образом обеспечивает корректную работу вложенных вызовов функций и соответствует принципу LIFO.
Когда выполнение функции завершается и происходит возврат, данные этого фрейма больше не нужны. Верхушка стека «удаляется», и программа возвращается к предыдущему состоянию. При следующем вызове функции ее данные снова помещаются на вершину стека.
Таким образом, стек естественным образом обеспечивает корректную работу вложенных вызовов функций и соответствует принципу LIFO.
5. Заключение
Несмотря на простую концепцию LIFO, стек используется в разработке в самых разных задачах: от хранения данных до работы вызовов функций внутри программы. Понимание его устройства помогает лучше разбираться в алгоритмах, анализировать сложность операций и увереннее проходить технические собеседования.
Если хотите подробнее разобраться в работе стека, то смотрите наше видео с наглядными примерами из курса по структурам данных.
Если хотите подробнее разобраться в работе стека, то смотрите наше видео с наглядными примерами из курса по структурам данных.
Другие статьи
Почему понимание стека важно разработчику
Понятие "стек" лежит в основе большого количества механизмов, с которыми разработчик сталкивается при создании приложения. Когда разработчик понимает, почему функции возвращаются в обратном порядке, где хранятся локальные данные и каким образом система управляет последовательностью вызовов, становится легче анализировать ошибки и находить причины проблем. Например, слишком глубокая рекурсия может привести к переполнению стека вызовов, потому что для каждого нового вызова функции требуется дополнительная память.
Поэтому стек - это не просто еще одна структура данных, а один из базовых инструментов, с помощью которого программы управляют последовательностью операций, состоянием и выполнением процессов
Поэтому стек - это не просто еще одна структура данных, а один из базовых инструментов, с помощью которого программы управляют последовательностью операций, состоянием и выполнением процессов
Стек и очередь: что их отличает?
Стек часто сравнивают с очередью, потому что обе структуры используются для хранения последовательности элементов, но принцип их работы отличается. Стек работает по принципу LIFO, а очередь — по принципу FIFO.
В очереди первым обрабатывается элемент, который пришел первым. Например, если пользователь отправил несколько задач на обработку, система может помещать их в очередь и выполнять последовательно в том же порядке. В стеке ситуация обратная: последний добавленный элемент будет извлечен первым.
В очереди первым обрабатывается элемент, который пришел первым. Например, если пользователь отправил несколько задач на обработку, система может помещать их в очередь и выполнять последовательно в том же порядке. В стеке ситуация обратная: последний добавленный элемент будет извлечен первым.
Где стек используется в реальных системах?
В разработке стек встречается внутри операционных систем, виртуальных машин, компиляторов и прикладных программ. Например, стек вызовов позволяет хранить информацию о выполняемых функциях и возвращаться к месту, откуда была вызвана текущая функция.
Еще один распространенный пример — история действий в приложении. При создании новой операции ее можно добавить в стек. Когда пользователь выполняет отмену действия, программа достает последнее изменение и возвращает систему к предыдущему состоянию. Такой подход используется при реализации undo/redo и других механизмов управления состоянием.
Стек также можно использовать при обработке выражений, проверке скобок и выполнении алгоритмов обхода графов. В последнем случае структура помогает хранить вершины, которые необходимо обработать на следующем шаге. В результате программа может последовательно выполнять набор процессов, не сохраняя всю логику обхода непосредственно в коде алгоритма.
Еще один распространенный пример — история действий в приложении. При создании новой операции ее можно добавить в стек. Когда пользователь выполняет отмену действия, программа достает последнее изменение и возвращает систему к предыдущему состоянию. Такой подход используется при реализации undo/redo и других механизмов управления состоянием.
Стек также можно использовать при обработке выражений, проверке скобок и выполнении алгоритмов обхода графов. В последнем случае структура помогает хранить вершины, которые необходимо обработать на следующем шаге. В результате программа может последовательно выполнять набор процессов, не сохраняя всю логику обхода непосредственно в коде алгоритма.
Как стек выглядит в разных языках программирования?
Как вы будете работать со стэком зависит от языка программирования, который используется для разработки в конкретном проекте.
Например, в Python используется список и операции append и pop, чтобы получить поведение стека. Это удобно, когда не требуется отдельная специализированная структура.
В PHP похожую логику можно реализовать с помощью массива. В других языках программирования существуют готовые структуры данных или библиотеки, которые предоставляют операции добавления и удаления элементов из вершины. При этом сама идея остается неизменной: новый элемент добавляется наверх, а извлечение происходит с той же стороны.
Например, в Python используется список и операции append и pop, чтобы получить поведение стека. Это удобно, когда не требуется отдельная специализированная структура.
В PHP похожую логику можно реализовать с помощью массива. В других языках программирования существуют готовые структуры данных или библиотеки, которые предоставляют операции добавления и удаления элементов из вершины. При этом сама идея остается неизменной: новый элемент добавляется наверх, а извлечение происходит с той же стороны.