Войти
Подобно стопке тарелок, добавление или удаление возможно только наверху. 
Простое представление среды выполнения стека с помощью операций push и pop. В информатике стек - это абстрактный тип данных, который служит коллекция элементов с двумя основными основными операциями:
Порядок, в котором элементы выходят из стека, приводит к его альтернативному имени, LIFO (последний пришел, первый вышел ). Кроме того, операция peek может предоставить доступ к вершине без изменения стека. Название «стек» для этого типа структуры происходит от аналогии с набором физических элементов, уложенных друг на друга. Эта структура позволяет легко снять элемент с вершины стека, в то время как для перехода к элементу, находящемуся глубже в стеке, может потребоваться сначала снять несколько других элементов.
Считается линейной структурой данных, или более абстрактно последовательная коллекция, операции push и pop происходят только на одном конце структуры, называемом вершиной стека. Эта структура данных позволяет реализовать стек как односвязный список и указатель на верхний элемент. Стек может быть реализован с ограниченной емкостью. Если стек заполнен и не содержит достаточно места, чтобы принять объект, который нужно отправить, стек считается находящимся в состоянии переполнения. Операция pop удаляет элемент из вершины стека.
Стек необходим для реализации поиска в глубину.
Стеки вошли в литературу по информатике в 1946 году, когда Алан М. Тьюринг использовали термины «закопать» и «не закопать» как средства вызова и возврата из подпрограмм. Подпрограммы уже были реализованы в Конраде Цузе Z4 в 1945.
Клаус Самельсон и Фридрих Л. Бауэр из Технические Мюнхенский университет предложил идею стека в 1955 году и подал патент в 1957. В марте 1988 года, когда Самельсон умер, Бауэр получил IEEE награду Computer Pioneer Award за изобретение принципа стека. Подобные концепции были независимо разработаны Чарльзом Леонардом Хэмблином в первой половине 1954 года и [de ] в 1958 году.
Стеки часто описываются с использованием аналогии подпружиненной стопки тарелок в кафетерии. Сверху стопки кладут чистые тарелки, прижимая уже имеющиеся. Когда пластина удаляется из стопки, та, которая находится под ней, выскакивает и становится новой верхней пластиной.
Во многих реализациях стек содержит больше операций, чем основные операции «push» и «pop». Примером несущественной операции является «вершина стека» или «просмотр», при которой наблюдается верхний элемент, не удаляя его из стека. Это можно сделать с помощью «pop», за которым следует «push», чтобы вернуть те же данные в стек, поэтому это не считается важной операцией. Если стек пуст, при выполнении операций «вершина стека» или «выталкивания» возникает состояние потери значимости. Кроме того, реализации часто имеют функцию, которая просто возвращает информацию о том, пуст ли стек.
Стек можно легко реализовать через массив или связанный список. То, что идентифицирует структуру данных как стек, в любом случае - это не реализация, а интерфейс: пользователю разрешено только вставлять или вставлять элементы в массив или связанный список с некоторыми другими вспомогательными операциями. Ниже будут продемонстрированы обе реализации с использованием псевдокода.
Массив может использоваться для реализации (ограниченного) стека следующим образом. Первый элемент, обычно с нулевым смещением , является нижним, в результате чего array [0]является первым элементом, помещенным в стек, а последний элемент удален. Программа должна отслеживать размер (длину) стека, используя переменную top, которая записывает количество элементов, выдвинутых на данный момент, таким образом указывая на то место в массиве, куда должен быть вставлен следующий элемент (при условии, что ноль - соглашение об индексах на основе). Таким образом, сам стек может быть эффективно реализован как трехэлементная структура:
структура stack: maxsize: integer top: integer items: array of item
procedure initialize (stk: stack, size : integer): stk.items ← новый массив элементов размера, изначально пустой stk.maxsize ← size stk.top ← 0
Операция push добавляет элемент и увеличивает верхний индекс после проверки на переполнение:
процедура push (stk: stack, x: item): if stk.top = stk.maxsize: сообщение об ошибке переполнения else : stk.items [stk.top ] ← x stk.top ← stk.top + 1
Аналогичным образом, pop уменьшает верхний индекс после проверки на недополнение и возвращает элемент, который ранее был верхним:
procedure pop ( stk: stack): if stk.top = 0: сообщить об ошибке недостаточного заполнения else : stk.top ← stk.top - 1 r ← stk.items [stk.top] return r
Используя динамический массив, можно реализовать стек, который может увеличиваться или уменьшаться сколько угодно. Размер стека - это просто размер динамического массива, который является очень эффективной реализацией стека, поскольку добавление элементов в конец динамического массива или удаление элементов из него требует амортизированного времени O (1).
Другой вариант реализации стеков - использование односвязного списка. Стек тогда является указателем на "голову" списка, возможно, со счетчиком для отслеживания размера списка:
структура frame: data: item next: frame или nil
структура stack: head: frame или nil size: integer
процедура initialize (stk: stack): stk.head ← nil stk.size ← 0
Нажатие и выталкивание элементов происходит в глава списка; переполнение невозможно в этой реализации (если память не исчерпана):
процедура push (stk: stack, x: item): newhead ← new frame newhead.data ← x newhead.next ← stk.head stk. head ← newhead stk.size ← stk.size + 1
процедура pop (stk: stack): if stk.head = nil: сообщить об ошибке недостаточного заполнения r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 return r
Некоторые языки, такие как Perl, LISP, JavaScript и Python делают операции со стеком push и pop доступными в их стандартных типах списков / массивов. Некоторые языки, особенно те, что принадлежат к семейству Forth (включая PostScript ), разработаны на основе определенных языков стека, которые напрямую видны программисту и управляются им.
Ниже приведен пример управления стеком в Common Lisp («>» - это приглашение интерпретатора Лиспа; строки, не начинающиеся с «>», - это ответы интерпретатора на выражения):
>(setf stack (list 'a' b 'c)) ;; установить переменную «стек» (A B C)>(pop stack) ;; получить верхний (крайний левый) элемент, должен изменить стек A>stack ;; проверить значение стека (B C)>(push 'new stack) ;; вставьте новую вершину в стек (НОВИНКА B C)
Некоторые из типов контейнеров стандартной библиотеки C ++ имеют операции push_back и pop_back с семантикой LIFO; Кроме того, класс шаблона стека адаптирует существующие контейнеры для предоставления ограниченного API только с операциями push / pop. В PHP есть класс SplStack. Библиотека Java содержит класс Stack , который является специализацией Vector . Ниже приводится пример программы на языке Java, использующей этот класс.
импортировать java.util.Stack; class StackDemo {public static void main (String args) {Stack stack = new Stack (); stack.push («А»); // Вставляем «A» в стек stack.push («B»); // Вставляем "B" в стек stack.push ("C"); // Вставляем "C" в стек stack.push ("D"); // Вставляем "D" в стек System.out.println (stack.peek ()); // Печатает верх стека ("D") stack.pop (); // удаляем верх ("D") stack.pop (); // удаление следующей вершины ("C")}} Обычно стеки используются на уровне архитектуры как средства выделения памяти и доступа к ней.
Типичный стек, хранящий локальные данные и информацию о вызовах для вызовов вложенных процедур (не обязательно вложенных процедур ). Эта стопка растет вниз от своего источника. Указатель стека указывает на текущий самый верхний элемент данных в стеке. Операция push уменьшает указатель и копирует данные в стек; операция pop копирует данные из стека, а затем увеличивает указатель на единицу. Каждая процедура, вызываемая в программе, сохраняет информацию о возвращении процедуры (желтым цветом) и локальные данные (другими цветами), помещая их в стек. Этот тип реализации стека чрезвычайно распространен, но он уязвим для атак переполнения буфера (см. Текст). Типичный стек - это область памяти компьютера с фиксированным источником и переменным размером. Первоначально размер стека равен нулю. Указатель стека, обычно в форме аппаратного регистра, указывает на последнее место в стеке, на которое ссылались; когда размер стека равен нулю, указатель стека указывает на начало стека.
Двумя операциями, применимыми ко всем стекам, являются:
Существует множество вариаций основного принципа работы со стеком. Каждый стек имеет фиксированное место в памяти, с которого он начинается. Когда элементы данных добавляются в стек, указатель стека смещается, чтобы указать текущий экстент стека, который расширяется от начала координат.
Указатели стека могут указывать на начало стека или на ограниченный диапазон адресов выше или ниже начала координат (в зависимости от направления роста стека); однако указатель стека не может пересекать начало стека. Другими словами, если источник стека находится по адресу 1000, а стек растет вниз (к адресам 999, 998 и т. Д.), Указатель стека никогда не должен увеличиваться больше 1000 (до 1001, 1002 и т. Д.). Если операция выталкивания в стеке заставляет указатель стека перемещаться за исходную точку стека, происходит опустошение стека. Если операция push заставляет указатель стека увеличиваться или уменьшаться за пределы максимального размера стека, происходит переполнение стека.
В некоторых средах, которые сильно зависят от стека, могут быть предусмотрены дополнительные операции, например:
Стеки часто визуализируются растущими снизу вверх (как в реальном мире). Их также можно визуализировать, растущими слева направо, так что «самый верхний» становится «крайним правым», или даже растущим сверху вниз. Важной особенностью является то, что нижняя часть стопки находится в фиксированном положении. Иллюстрация в этом разделе представляет собой пример визуализации роста сверху вниз: верх (28) - это «низ» стека, поскольку «верх» (9) стека - это то место, откуда элементы выталкиваются или выталкиваются.
При повороте вправо первый элемент перемещается в третью позицию, второй - в первую, а третий - во вторую. Вот две эквивалентные визуализации этого процесса:
яблоко, банан, банан === повернуть вправо ==>огурец, яблоко, яблоко
, огурец, яблоко, банан === повернуть влево ==>огурец, яблоко, банан
Стек обычно представлен в компьютерах блоком ячеек памяти, где «дно» находится в фиксированном месте, а указатель стека содержит адрес текущей «верхней» ячейки в стеке. Верхняя и нижняя термины используются независимо от того, растет ли стек в сторону более низких адресов памяти или в сторону более высоких адресов памяти.
Нажатие элемента в стек изменяет указатель стека на размер элемента (либо с уменьшением, либо с увеличением, в зависимости от направления, в котором стек растет в памяти), указывая на следующую ячейку и копирует новый верхний элемент в область стека. Опять же, в зависимости от точной реализации, в конце операции push указатель стека может указывать на следующее неиспользуемое место в стеке или может указывать на самый верхний элемент в стеке. Если стек указывает на текущий самый верхний элемент, указатель стека будет обновлен до того, как новый элемент будет помещен в стек; если он указывает на следующее доступное место в стеке, он будет обновлен после того, как новый элемент будет помещен в стек.
Выталкивание стека - это просто обратное выталкивание. Самый верхний элемент стека удаляется, а указатель стека обновляется в порядке, обратном порядку, используемому в операции push.
Многие конструкции CISC типа CPU, включая x86, Z80 и 6502, имеют специальный регистр для использования в качестве указателя стека стека вызовов с выделенными инструкциями call, return, push и pop, которые неявно обновляют выделенный регистр, тем самым увеличивая код плотность. Некоторые процессоры CISC, такие как PDP-11 и 68000, также имеют специальные режимы адресации для реализации стеков, обычно с полу-выделенным указателем стека как ну (типа А7 в 68000). Напротив, большинство конструкций ЦП RISC не имеют выделенных инструкций стека, и поэтому большинство, если не все регистры могут использоваться в качестве указателей стека по мере необходимости.
Архитектура x87 с плавающей запятой представляет собой пример набора регистров, организованных в виде стека, к которому осуществляется прямой доступ в отдельные регистры (относительно текущей вершины) также возможно. Как и в случае с машинами на основе стека в целом, наличие вершины стека в качестве неявного аргумента позволяет использовать небольшую площадь машинного кода с хорошим использованием шины пропускной способности и код кэширует, но также предотвращает некоторые типы оптимизации, возможные на процессорах, разрешая произвольный доступ к регистровому файлу для всех (двух или трех) операндов. Структура стека также делает реализации суперскалярных с переименованием регистров (для спекулятивного исполнения ) несколько более сложными для реализации, хотя это все еще возможно, как показано на примере современного x87 реализации.
Sun SPARC, AMD Am29000 и Intel i960 - все это примеры архитектур, использующих окна регистров в стеке регистров в качестве другой стратегии для Избегайте использования медленной основной памяти для аргументов функций и возвращаемых значений.
Существует также ряд небольших микропроцессоров, которые реализуют стек непосредственно в аппаратном обеспечении, а некоторые микроконтроллеры имеют стек фиксированной глубины, к которому нет прямого доступа. Примерами являются микроконтроллеры PIC , линия Harris RTX и. Многие микропроцессоры на основе стека использовались для реализации языка программирования Forth на уровне микрокода. Стеки также использовались в качестве основы для ряда мэйнфреймов и мини-компьютеров. Такие машины назывались стековыми машинами, наиболее известными из которых были Burroughs B5000.
Калькуляторы, использующие обратная польская запись использует структуру стека для хранения значений. Выражения могут быть представлены в префиксной, постфиксной или инфиксной нотации, а преобразование из одной формы в другую может быть выполнено с использованием стека. Многие компиляторы используют стек для анализа синтаксиса выражений, программных блоков и т. Д. Перед преобразованием в код низкого уровня. Большинство языков программирования - это контекстно-свободные языки, что позволяет анализировать их с помощью стековых машин.
Еще одно важное применение стеков - отслеживание с возвратом. Рассмотрим простой пример поиска правильного пути в лабиринте. Есть ряд точек, от начальной до конечной. Начнем с одной точки. Чтобы добраться до конечного пункта назначения, есть несколько путей. Допустим, мы выбрали случайный путь. Пройдя определенный путь, мы понимаем, что выбранный нами путь неправильный. Итак, нам нужно найти способ вернуться к началу этого пути. Это можно сделать с помощью стеков. С помощью стеков мы запоминаем точку, в которой достигли. Это делается путем помещения этой точки в стек. В случае, если мы окажемся на неправильном пути, мы можем вытолкнуть последнюю точку из стека и, таким образом, вернуться к последней точке и продолжить наш поиск, чтобы найти правильный путь. Это называется возвратом.
Прототипным примером алгоритма поиска с возвратом является поиск в глубину, который находит все вершины графа, которые могут быть достигнуты из указанной начальной вершины. Другие применения поиска с возвратом включают поиск в пробелах, которые представляют собой потенциальные решения проблемы оптимизации. Переход и граница - это метод выполнения такого поиска с обратным отслеживанием без исчерпывающего поиска всех потенциальных решений в таком пространстве.
Ряд языков программирования ориентированы на стек, что означает, что они определяют большинство основных операций (сложение двух чисел, печать символ), поскольку они берут свои аргументы из стека и помещают любые возвращаемые значения обратно в стек. Например, PostScript имеет стек возврата и стек операндов, а также стек состояния графики и стек словаря. Многие виртуальные машины также ориентированы на стек, в том числе машина с p-кодом и виртуальная машина Java.
Практически все соглашения о вызовах - «Способы, которыми подпрограммы получают свои параметры и возвращают результаты» - «используют специальный стек (« стек вызовов ») для хранения информации о вызове процедуры / функции и вложенности, чтобы переключиться на контекст вызываемой функции и вернуться к вызывающей функции после завершения вызова. Функции следуют протоколу времени выполнения между вызывающим и вызываемым, чтобы сохранить аргументы и возвращаемое значение в стеке. Стеки - важный способ поддержки вложенных или рекурсивных вызовов функций. Этот тип стека неявно используется компилятором для поддержки операторов CALL и RETURN (или их эквивалентов) и не управляется непосредственно программистом.
Некоторые языки программирования используют стек для хранения данных, локальных для процедуры. Пространство для локальных элементов данных выделяется из стека при входе в процедуру и освобождается при выходе из процедуры. Таким образом обычно реализуется язык программирования C. Использование одного и того же стека для вызовов данных и процедур имеет важные последствия для безопасности (см. Ниже), о которых программист должен знать, чтобы избежать внесения серьезных ошибок безопасности в программу.
Некоторые алгоритмы используют стек (отдельный от обычного стека вызовов функций большинства языков программирования) в качестве принципа структуры данных с которые они организуют свою информацию. К ним относятся:
Некоторые вычислительные среды используют стеки таким образом, что могут сделать их уязвимыми для нарушений безопасности И нападки. Программисты, работающие в таких средах, должны проявлять особую осторожность, чтобы избежать ошибок, связанных с этими реализациями.
Например, некоторые языки программирования используют общий стек для хранения как данных, локальных для вызываемой процедуры, так и информации о связывании, которая позволяет процедуре вернуться к вызывающей стороне. Это означает, что программа перемещает данные в один стек и из него, который содержит критические адреса возврата для вызовов процедур. Если данные перемещаются в неправильное место в стеке или элемент данных слишком большого размера перемещается в место стека, которое недостаточно велико для его размещения, возвращаемая информация для вызовов процедур может быть повреждена, что приведет к сбою программы.
Злоумышленники могут попытаться выполнить атаку разбиения стека, которая использует преимущества этого типа реализации, предоставляя ввод данных слишком большого размера в программу, которая не проверяет длину ввода. Такая программа может полностью скопировать данные в какое-либо место в стеке и тем самым изменить адреса возврата для процедур, которые ее вызвали. Злоумышленник может поэкспериментировать, чтобы найти определенный тип данных, которые могут быть предоставлены такой программе, чтобы адрес возврата текущей процедуры сбрасывался так, чтобы указывать на область в самом стеке (и в данных, предоставленных злоумышленником), который, в свою очередь, содержит инструкции по выполнению несанкционированных операций.
Этот тип атаки является разновидностью атаки переполнения буфера и является чрезвычайно частым источником нарушений безопасности в программном обеспечении, главным образом потому, что некоторые из самых популярных компиляторов используют общий стек для обоих данные и вызовы процедур и не проверяют длину элементов данных. Часто программисты также не пишут код для проверки размера элементов данных, и когда элемент данных слишком большого или меньшего размера копируется в стек, может произойти нарушение безопасности.
Портал компьютерного программирования 
В эту статью включены материалы общественного достояния из документа NIST : Black, Paul E. «Ограниченный стек». Словарь алгоритмов и структур данных. | Викискладе есть материалы, связанные с структурами данных стека. |
 | В Викиучебниках есть книга по тема: Структуры данных / стеки и очереди |
