Стек (абстрактный тип данных) - Stack (abstract data type)
В информатике , А стек представляет собой абстрактный тип данных , который служит в качестве коллекции элементов, с двумя основными главными операциями:
- Push , который добавляет элемент в коллекцию, и
- Pop , который удаляет последний добавленный элемент, который еще не был удален.
Порядок, в котором элементы выходят из стека, дает начало его альтернативному имени, LIFO ( последний пришел , первый вышел ). Кроме того, PEEK операция может дать доступ к вершине без изменения стеки. Название «стек» для этого типа структуры происходит от аналогии с набором физических элементов, уложенных друг на друга. Эта структура позволяет легко снять элемент с вершины стека, в то время как для того, чтобы добраться до элемента, находящегося глубже в стеке, может потребоваться сначала снять несколько других элементов.
Операции push и pop, рассматриваемые как линейная структура данных или, более абстрактно, как последовательная коллекция, происходят только на одном конце структуры, называемом вершиной стека. Эта структура данных позволяет реализовать стек как односвязный список и указатель на верхний элемент. Стек может быть реализован с ограниченной емкостью. Если стек заполнен и не содержит достаточно места, чтобы принять объект, который нужно отправить, стек считается находящимся в состоянии переполнения . Операция pop удаляет элемент из вершины стека.
Стек необходим для реализации поиска в глубину .
История
Стеки вошли в литературу по информатике в 1946 году, когда Алан М. Тьюринг использовал термины «закопать» и «закопать» как средства вызова подпрограмм и возврата из них. Подпрограммы уже реализованы в Конрада Цузе «s Z4 в 1945 году.
Клаус Самельсон и Фридрих Л. Бауэр из Технического университета Мюнхена предложили идею стека в 1955 году и подали патент в 1957. В марте 1988 года, когда Самельсон умер, Бауэр получил премию IEEE Computer Pioneer Award за изобретение стека. принцип. Подобные концепции были независимо разработаны Чарльзом Леонардом Хамблином в первой половине 1954 года и Вильгельмом Каммерером в 1958 году.
Стопки часто описываются аналогично подпружиненной стопке тарелок в кафетерии. Сверху стопки кладут чистые тарелки, прижимая уже имеющиеся. Когда пластина удаляется из стопки, та, которая находится под ней, всплывает и становится новой верхней пластиной.
Несущественные операции
Во многих реализациях в стеке больше операций, чем в основных операциях «push» и «pop». Примером несущественной операции является «вершина стека» или «просмотр», при которой наблюдает за верхним элементом, не удаляя его из стека. Это можно сделать с помощью «pop», за которым следует «push», чтобы вернуть те же данные в стек, поэтому это не считается важной операцией. Если стек пуст, при выполнении операций «вершина стека» или «выталкивания» возникает состояние потери значимости. Кроме того, многие реализации обеспечивают проверку того, пуст ли стек, и тот, который возвращает его размер.
Программные стеки
Реализация
Стек можно легко реализовать через массив или связанный список . Что идентифицирует структуру данных как стек в любом случае, так это не реализация, а интерфейс: пользователю разрешено только вставлять или помещать элементы в массив или связанный список с некоторыми другими вспомогательными операциями. Ниже будут продемонстрированы обе реализации с использованием псевдокода .
Множество
Массив можно использовать для реализации (ограниченного) стека следующим образом. Первый элемент, обычно при нулевом смещении , является нижним, в результате чего array[0]он первым помещается в стек, а последний элемент выталкивается. Программа должна отслеживать размер (длину) стека, используя переменную top, которая записывает количество элементов, выдвинутых на данный момент, таким образом указывая на то место в массиве, куда должен быть вставлен следующий элемент (при условии, что ноль - соглашение об индексах на основе). Таким образом, сам стек может быть эффективно реализован как трехэлементная структура:
structure stack:
maxsize : integer
top : integer
items : array of item
procedure initialize(stk : stack, size : integer):
stk.items ← new array of size items, initially empty
stk.maxsize ← size
stk.top ← 0
Операция push добавляет элемент и увеличивает верхний индекс после проверки переполнения:
procedure push(stk : stack, x : item):
if stk.top = stk.maxsize:
report overflow error
else:
stk.items[stk.top] ← x
stk.top ← stk.top + 1
Точно так же pop уменьшает верхний индекс после проверки на недополнение и возвращает элемент, который ранее был верхним:
procedure pop(stk : stack):
if stk.top = 0:
report underflow error
else:
stk.top ← stk.top − 1
r ← stk.items[stk.top]
return r
Используя динамический массив , можно реализовать стек, который может увеличиваться или уменьшаться сколько угодно. Размер стека - это просто размер динамического массива, который является очень эффективной реализацией стека, поскольку добавление элементов или удаление элементов из конца динамического массива требует амортизированного времени O (1).
Связанный список
Другой вариант реализации стеков - использование односвязного списка . Стек тогда является указателем на "голову" списка, возможно, со счетчиком для отслеживания размера списка:
structure frame:
data : item
next : frame or nil
structure stack:
head : frame or nil
size : integer
procedure initialize(stk : stack):
stk.head ← nil
stk.size ← 0
Нажатие и выталкивание элементов происходит в начале списка; переполнение невозможно в этой реализации (если память не исчерпана):
procedure push(stk : stack, x : item):
newhead ← new frame
newhead.data ← x
newhead.next ← stk.head
stk.head ← newhead
stk.size ← stk.size + 1
procedure pop(stk : stack):
if stk.head = nil:
report underflow error
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 (" > " - это приглашение интерпретатора Lisp; строки, не начинающиеся с " > ", являются ответами интерпретатора на выражения):
> (setf stack (list 'a 'b 'c)) ;; set the variable "stack"
(A B C)
> (pop stack) ;; get top (leftmost) element, should modify the stack
A
> stack ;; check the value of stack
(B C)
> (push 'new stack) ;; push a new top onto the stack
(NEW B C)
Некоторые типы контейнеров стандартной библиотеки C ++ имеют операции push_back и pop_back с семантикой LIFO; Кроме того, класс шаблона стека адаптирует существующие контейнеры для предоставления ограниченного API только с операциями push / pop. В PHP есть класс SplStack . Библиотека Java содержит Stackкласс, который является специализацией Vector. Ниже приведен пример программы на языке Java , использующей этот класс.
import java.util.Stack;
class StackDemo {
public static void main(String[]args) {
Stack<String> stack = new Stack<String>();
stack.push("A"); // Insert "A" in the stack
stack.push("B"); // Insert "B" in the stack
stack.push("C"); // Insert "C" in the stack
stack.push("D"); // Insert "D" in the stack
System.out.println(stack.peek()); // Prints the top of the stack ("D")
stack.pop(); // removing the top ("D")
stack.pop(); // removing the next top ("C")
}
}
Аппаратный стек
Обычно стеки используются на уровне архитектуры как средства выделения памяти и доступа к ней.
Базовая архитектура стека
Типичный стек - это область памяти компьютера с фиксированным происхождением и переменным размером. Изначально размер стека равен нулю. Указатель стека, как правило , в виде аппаратного регистра, указывает на самое последнее ссылочного место в стеке; когда размер стека равен нулю, указатель стека указывает на начало стека.
Две операции, применимые ко всем стекам:
- толчок операции, в которой элемент данных помещается в месте , на который указывает указатель стека, а также адрес в указатель стека корректируется по размеру элемента данных;
- поп или тянуть операция: элемент данных в текущем местоположении , на который указывает указатель стека удаляется, а указатель стека корректируется по размеру элемента данных.
Существует множество вариаций основного принципа работы со стеком. Каждый стек имеет фиксированное место в памяти, с которого он начинается. Когда элементы данных добавляются в стек, указатель стека смещается, чтобы указать текущий экстент стека, который расширяется от начала координат.
Указатели стека могут указывать на начало стека или на ограниченный диапазон адресов выше или ниже начала координат (в зависимости от направления роста стека); однако указатель стека не может пересекать начало стека. Другими словами, если источник стека находится по адресу 1000, а стек растет вниз (к адресам 999, 998 и т. Д.), Указатель стека никогда не должен увеличиваться больше 1000 (до 1001, 1002 и т. Д.). Если операция выталкивания в стеке заставляет указатель стека перемещаться за исходную точку стека, происходит опустошение стека . Если операция push приводит к увеличению или уменьшению указателя стека сверх максимального размера стека, происходит переполнение стека .
Некоторые среды, которые сильно зависят от стеков, могут предоставлять дополнительные операции, например:
- Дублировать : верхний элемент выскакивает, а затем снова нажимается (дважды), так что дополнительная копия бывшего верхнего элемента теперь находится сверху, а оригинал под ним.
- Peek : проверяется (или возвращается) самый верхний элемент, но указатель стека и размер стека не изменяются (то есть элемент остается в стеке). Во многих статьях это также называется верхней операцией.
- Обмен или обмен : два самые верхние элементы на биржевую стопку мест.
- Rotate (or Roll) : n самых верхних элементов перемещаются по стопке по очереди. Например, если n = 3, элементы 1, 2 и 3 в стеке перемещаются в позиции 2, 3 и 1 в стеке соответственно. Многие варианты этой операции возможны, с наиболее распространенными из которых называется левый поворот и правый поворот.
Стеки часто визуализируются растущими снизу вверх (как настоящие стеки). Они также могут быть визуализированы растущими слева направо, так что «самый верхний» становится «крайним правым», или даже растущим сверху вниз. Важной особенностью является то, что нижняя часть стопки находится в фиксированном положении. Иллюстрация в этом разделе представляет собой пример визуализации роста сверху вниз: верх (28) - это «низ» стека, поскольку «верх» стека (9) - это то место, откуда элементы выталкиваются или выталкиваются.
При повороте вправо первый элемент переместится в третью позицию, второй - в первую, а третий - во вторую. Вот две эквивалентные визуализации этого процесса:
apple banana banana ===right rotate==> cucumber cucumber apple
cucumber apple banana ===left rotate==> cucumber apple banana
Стек обычно представлен в компьютерах блоком ячеек памяти, где «дно» находится в фиксированном месте, а указатель стека содержит адрес текущей «верхней» ячейки в стеке. Верхняя и нижняя терминология используются независимо от того, растет ли стек в сторону меньших адресов памяти или в сторону более высоких адресов памяти.
При нажатии элемента в стек указатель стека регулируется по размеру элемента (либо уменьшается, либо увеличивается, в зависимости от направления, в котором стек растет в памяти), указывая его на следующую ячейку и копирует новый верхний элемент в область стека. Опять же, в зависимости от точной реализации, в конце операции push указатель стека может указывать на следующее неиспользуемое место в стеке или может указывать на самый верхний элемент в стеке. Если стек указывает на текущий самый верхний элемент, указатель стека будет обновлен до того, как новый элемент будет помещен в стек; если он указывает на следующее доступное место в стеке, он будет обновлен после того, как новый элемент будет помещен в стек.
Выталкивание стека - это просто обратное нажатие. Самый верхний элемент в стеке удаляется, а указатель стека обновляется в порядке, обратном порядку, используемому в операции push.
Стек в основной памяти
Многие CISC -типа CPU конструкций, включая x86 , Z80 и 6502 , имеют специальный регистр для использования в качестве стека вызовов указатель стека с выделенным вызова, возврат, толчок и поп - команды , которые неявно обновить специальный регистр, увеличивая таким образом код плотности. Некоторые процессоры CISC, такие как PDP-11 и 68000 , также имеют специальные режимы адресации для реализации стеков , обычно с полу-выделенным указателем стека (например, A7 в 68000). Напротив, в большинстве конструкций ЦП RISC нет выделенных команд стека, и поэтому большинство, если не все регистры могут использоваться в качестве указателей стека по мере необходимости.
Стек в регистрах или выделенной памяти
Архитектура с плавающей запятой x87 является примером набора регистров, организованных в виде стека, где также возможен прямой доступ к отдельным регистрам (относительно текущей вершины). Как и в случае с машинами на основе стека в целом, наличие вершины стека в качестве неявного аргумента позволяет использовать небольшой объем машинного кода с хорошим использованием полосы пропускания шины и кешей кода , но также предотвращает некоторые типы оптимизации, возможные на процессорах, разрешающие произвольный доступ к регистровому файлу для всех (двух или трех) операндов. Структура стека также несколько усложняет реализацию суперскалярных реализаций с переименованием регистров (для спекулятивного выполнения ), хотя это все еще возможно, как показано на примере современных реализаций x87 .
Sun SPARC , AMD Am29000 и Intel i960 - все это примеры архитектур, использующих окна регистров в стеке регистров в качестве другой стратегии, позволяющей избежать использования медленной основной памяти для аргументов функций и возвращаемых значений.
Существует также ряд небольших микропроцессоров, которые реализуют стек непосредственно в аппаратном обеспечении, а некоторые микроконтроллеры имеют стек фиксированной глубины, к которому нет прямого доступа. Примерами являются микроконтроллеры PIC , Computer Cowboys MuP21 , линейка Harris RTX и Novix NC4016 . Многие микропроцессоры на основе стека использовались для реализации языка программирования Forth на уровне микрокода . Стеки также использовались в качестве основы для ряда мэйнфреймов и мини-компьютеров . Такие машины назывались штабелеукладчиками , самым известным из которых является Burroughs B5000 .
Применение стеков
Оценка выражений и синтаксический анализ
В калькуляторах, использующих обратную польскую нотацию, для хранения значений используется стековая структура. Выражения могут быть представлены в префиксной, постфиксной или инфиксной нотации, а преобразование из одной формы в другую может выполняться с использованием стека. Многие компиляторы используют стек для анализа синтаксиса выражений, программных блоков и т. Д. Перед преобразованием в код низкого уровня. Большинство языков программирования являются контекстно-свободными языками , что позволяет анализировать их с помощью стековых машин.
Возврат
Еще одно важное применение стеков - поиск с возвратом . Рассмотрим простой пример поиска правильного пути в лабиринте. Есть ряд точек, от начальной до конечной. Начнем с одной точки. Чтобы добраться до конечного пункта, есть несколько путей. Предположим, мы выбрали случайный путь. Пройдя определенный путь, мы понимаем, что выбранный нами путь неправильный. Поэтому нам нужно найти способ вернуться к началу этого пути. Это можно сделать с помощью стеков. С помощью стеков мы запоминаем точку, в которой достигли. Это делается путем помещения этой точки в стек. В случае, если мы окажемся на неправильном пути, мы можем вытащить последнюю точку из стека и, таким образом, вернуться к последней точке и продолжить поиски правильного пути. Это называется возвратом.
Прототипическим примером алгоритма поиска с возвратом является поиск в глубину , который находит все вершины графа, которые могут быть достигнуты из указанной начальной вершины. Другие приложения поиска с возвратом включают поиск в пробелах, которые представляют собой потенциальные решения проблемы оптимизации. Переход и граница - это метод выполнения такого поиска с обратным отслеживанием без исчерпывающего поиска всех потенциальных решений в таком пространстве.
Управление памятью времени компиляции
Ряд языков программирования имеют стек-ориентированный , то есть они определяют самые основные операции (сложение двух чисел, печать символа) , как принимать их аргументы из стека, а также размещение любого возврата значения обратно в стек. Например, PostScript имеет стек возврата и стек операндов, а также стек состояния графики и стек словаря. Многие виртуальные машины также ориентированы на стек, в том числе машина с p-кодом и виртуальная машина Java .
Почти все соглашения о вызовах - «способы, которыми подпрограммы получают свои параметры и возвращают результаты» - «используют специальный стек (« стек вызовов ») для хранения информации о вызове процедуры / функции и вложенности, чтобы переключиться в контекст вызываемой функции. и вернуться к функции вызывающего абонента, когда вызов завершится. Функции следуют протоколу времени выполнения между вызывающим и вызываемым, чтобы сохранить аргументы и возвращаемое значение в стеке. Стеки - важный способ поддержки вложенных или рекурсивных вызовов функций. Этот тип стека неявно используется компилятором для поддержки операторов CALL и RETURN (или их эквивалентов) и не управляется напрямую программистом.
Некоторые языки программирования используют стек для хранения локальных для процедуры данных. Пространство для локальных элементов данных выделяется из стека при входе в процедуру и освобождается при выходе из процедуры. Язык программирования C обычно реализуется таким образом. Использование одного и того же стека для вызовов данных и процедур имеет важные последствия для безопасности (см. Ниже), о которых программист должен знать, чтобы избежать внесения серьезных ошибок безопасности в программу.
Эффективные алгоритмы
Некоторые алгоритмы используют стек (отдельный от обычного стека вызовов функций большинства языков программирования) в качестве основной структуры данных, с помощью которой они организуют свою информацию. Это включает:
- Скан Грэма , алгоритм выпуклой оболочки двумерной системы точек. Выпуклая оболочка подмножества входных данных поддерживается в стеке, который используется для поиска и удаления вогнутостей на границе, когда к корпусу добавляется новая точка.
- Часть алгоритма SMAWK для поиска минимумов строк монотонной матрицы использует стеки аналогично сканированию Грэма.
- Все ближайшие меньшие значения , проблема поиска для каждого числа в массиве ближайшего предыдущего числа, которое меньше его. Один алгоритм для этой проблемы использует стек для поддержки коллекции кандидатов для ближайшего меньшего значения. Для каждой позиции в массиве стек выталкивается до тех пор, пока на его вершине не будет найдено меньшее значение, а затем значение в новой позиции помещается в стек.
- Алгоритм цепи ближайшего соседа , метод агломерационной иерархической кластеризации , основанной на поддержание стеки кластеров, каждый из которых является ближайшим соседом своего предшественника в стеке. Когда этот метод находит пару кластеров, которые являются ближайшими соседями, они выталкиваются и объединяются.
Безопасность
Некоторые вычислительные среды используют стеки таким образом, что могут сделать их уязвимыми для нарушений безопасности и атак. Программисты, работающие в таких средах, должны проявлять особую осторожность, чтобы избежать ошибок этих реализаций.
Например, некоторые языки программирования используют общий стек для хранения как данных, локальных для вызываемой процедуры, так и информации о связывании, которая позволяет процедуре вернуться к вызывающей стороне. Это означает, что программа перемещает данные в один стек и из него, который содержит критические адреса возврата для вызовов процедур. Если данные перемещаются в неправильное место в стеке или элемент данных слишком большого размера перемещается в место стека, которое недостаточно велико для его хранения, возвращаемая информация для вызовов процедур может быть повреждена, что приведет к сбою программы.
Злоумышленники могут попытаться осуществить атаку с разбиванием стека, которая использует преимущества этого типа реализации, предоставляя ввод данных слишком большого размера в программу, которая не проверяет длину ввода. Такая программа может полностью скопировать данные в какое-либо место в стеке и при этом изменить адреса возврата для процедур, которые ее вызвали. Злоумышленник может поэкспериментировать, чтобы найти определенный тип данных, которые могут быть предоставлены такой программе, чтобы адрес возврата текущей процедуры сбрасывался так, чтобы указывать на область в самом стеке (и в данных, предоставленных злоумышленником), который, в свою очередь, содержит инструкции по выполнению несанкционированных операций.
Этот тип атаки является разновидностью атаки переполнения буфера и является чрезвычайно частым источником нарушений безопасности в программном обеспечении, в основном потому, что некоторые из самых популярных компиляторов используют общий стек как для данных, так и для вызовов процедур и не проверяют длину элементы данных. Часто программисты также не пишут код для проверки размера элементов данных, и когда элемент данных слишком большого или меньшего размера копируется в стек, может произойти нарушение безопасности.
Смотрите также
использованная литература
-
Эта статья включает материалы, являющиеся общественным достоянием из документа NIST : Блэк, Пол Э. «Ограниченный стек» . Словарь алгоритмов и структур данных .
дальнейшее чтение
- Дональд Кнут . Искусство программирования , Том 1: Основные алгоритмы , третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89683-4 . Раздел 2.2.1: Стеки, очереди и дек, стр. 238–243.