Что такое стек в программировании
Перейти к содержимому

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

  • автор:

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

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

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

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

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

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

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

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

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

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

Стек вызовов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стек данных

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

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

Что дальше

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

Стек

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

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

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

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

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

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

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

vsrat_7 1 (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

картинка (75)

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

Стек

Стек (от англ. stack — стопка) — структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO). Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. Вернемся к описанию операций стека:

  • [math] \mathtt [/math] — проверка стека на наличие в нем элементов,
  • [math] \mathtt [/math] (запись в стек) — операция вставки нового элемента,
  • [math] \mathtt [/math] (снятие со стека) — операция удаления нового элемента.

Реализации

Для стека с [math]n[/math] элементами требуется [math]O(n)[/math] памяти, так как она нужна лишь для хранения самих элементов.

На массиве

Перед реализацией стека выделим ключевые поля:

  • [math]\mathtt [/math] — массив, с помощью которого реализуется стек, способный вместить не более [math]n[/math] элементов,
  • [math]\mathtt[/math] — индекс последнего помещенного в стек элемента.

Стек состоит из элементов [math]\mathtt [/math] , где [math]\mathtt[/math] — элемент на дне стека, а [math]\mathtt[/math] — элемент на его вершине. Если [math]\mathtt[/math] , то стек не содержит ни одного элемента и является пустым (англ. empty). Протестировать стек на наличие в нем элементов можно с помощью операции — запроса [math] \mathtt [/math] . Если элемент снимается с пустого стека, говорят, что он опустошается (англ. underflow), что обычно приводит к ошибке. Если значение [math]\mathtt[/math] больше [math]\mathtt[/math] , то стек переполняется (англ. overflow). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)

Каждую операцию над стеком можно легко реализовать несколькими строками кода:

boolean empty(): return s.top == 0
function push(element : T): s.top = s.top + 1 s[s.top] = element
T pop(): if empty() return error "underflow" else s.top = s.top - 1 return s[s.top + 1]

Как видно из псевдокода выше, все операции со стеком выполняются за [math]O(1)[/math] .

На саморасширяющемся массиве

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

Создадим вектор и определим операции стека на нём. В функции [math] \mathtt [/math] Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в [math] \mathtt [/math] , перед тем, как изъять элемент из массива, — не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.

  • [math]\mathtt[/math] — старый массив, в котором хранится стек,
  • [math]\mathtt[/math] — временный массив, где хранятся элементы после перекопирования,
  • [math]\mathtt[/math] — верхушка стека,
  • [math]\mathtt[/math] — размер массива.
function push(element : T): if head == capacity - 1 T newStack[capacity * 2] for i = 0 to capacity - 1 newStack[i] = s[i] s = newStack capacity = capacity * 2 head++ s[head] = element
T pop(): temp = s[head] head-- if head < capacity / 4 T newStack[capacity / 2] for i = 0 to capacity / 4 - 1 newStack[i] = s[i] s = newStack capacity = capacity / 2 return temp

На списке

Стек можно реализовать и на списке. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем «держать» за голову. Добавляться новые элементы посредством операции [math] \mathtt [/math] будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью [math] \mathtt [/math] будет текущая голова. После вызова функции [math] \mathtt [/math] текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции [math] \mathtt [/math] будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.

Заведем конструктор вида ListItem(next : ListItem, data : T)

  • [math]\mathtt[/math] — значение в верхушке стека,
  • [math]\mathtt[/math] — значение следующее за верхушкой стека.
function push(element : T): head = ListItem(head, element)
T pop(): data = head.data head = head.next return data

В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же [math]\mathtt[/math] . Стоит заметить, что стек требует [math]O(n)[/math] дополнительной памяти на указатели в списке.

См. также

Источники информации

  • Википедия — Стек
  • Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
  • T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1
  • Динамические структуры данных: стеки

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

Стек — это вид структуры данных, в котором элементы упорядочены и добавление или удаление элементов происходит с верхней части стека — по принципу «Последним пришел — первым ушел» (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, элемент извлекается из вершины стека, и вершина обновляется, чтобы указывать на следующий узел в списке.

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

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

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

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

Что такое Data Science

Что такое Data Science

Кто такой веб-разработчик

5 февр. 2024 г.

Кто такой веб-разработчик

Какой язык программирования выбрать в 2024 году

31 янв. 2024 г.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *