Стек (абстрактный тип данных)

Эта статья об абстрактном понятии. Некоторые конкретные варианты использования этого термина в вычислениях см. в разделе « Стек (значения) § Вычисления» .

Как и в случае со стопкой тарелок, добавление или удаление целесообразно только сверху.

Простое представление среды выполнения стека с операциями push и pop .

В информатике стек — это абстрактный тип данных , который служит набором элементов с двумя основными операциями:

• Push , который добавляет элемент в коллекцию, и
• Pop , который удаляет последний добавленный элемент.

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

Порядок, в котором элемент добавляется в стек или удаляется из него, описывается как «последний вошел — первым вышел » и обозначается аббревиатурой LIFO . Как и в случае со стеком физических объектов, эта структура позволяет легко удалить элемент с вершины стека, но для доступа к данным, расположенным глубже в стеке, может потребоваться сначала удалить несколько других элементов.

Рассматривая последовательную коллекцию, стек имеет один конец, который является единственной позицией, в которой могут выполняться операции push и pop ( верхняя часть стека), и фиксированный другой конец, нижний . Стек может быть реализован, например, как односвязный список с указателем на верхний элемент.

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

Стек необходим для реализации поиска в глубину .

История

Смотрите также: Ян Лукасевич § Работа

Стеки вошли в литературу по информатике в 1946 году, когда Алан Тьюринг использовал термины «захоронить» и «вытащить из подпрограммы» как средство вызова подпрограмм и возврата из них. Подпрограммы и двухуровневый стек уже были реализованы в Конрада Цузе в Z4 1945 году.

Клаус Самельсон и Фридрих Л. Бауэр из Мюнхенского технического университета предложили идею стека под названием Operationskeller («операционный подвал») в 1955 году. и подал патент в 1957 году. В марте 1988 года, когда Самельсон умер, Бауэр получил премию IEEE Computer Pioneer Award за изобретение принципа стека. Подобные концепции были независимо разработаны Чарльзом Леонардом Хэмблином в первой половине 1954 года. и Вильгельм Кеммерер с его автоматической памятью («автоматическая память») в 1958 году.

Стопки часто описываются по аналогии с подпружиненной стопкой тарелок в кафетерии. Чистые тарелки кладут наверх стопки, отодвигая все уже находящиеся там тарелки. Когда верхняя пластина удаляется из стопки, та, что находится под ней, поднимается и становится новой верхней пластиной.

Необязательные операции

Во многих реализациях стек содержит больше операций, чем основные операции «push» и «pop». Примером несущественной операции является «вершина стека» или «просмотр», которая наблюдает за верхним элементом, не удаляя его из стека. Поскольку эту операцию можно разбить на «выталкивание», за которым следует «нажатие» для возврата тех же данных в стек, это не считается важной операцией. Если стек пуст, при выполнении операций «верхнего стека» или «извлечения» возникнет состояние опустошения. Кроме того, многие реализации обеспечивают проверку того, пуст ли стек, и операцию, возвращающую его размер.

Программные стеки

Выполнение

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

Множество

Массив можно использовать для реализации (ограниченного) стека следующим образом. Первый элемент, обычно с нулевым смещением , является нижним, в результате чего 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 (" > " — это приглашение интерпретатора Лиспа; строки, не начинающиеся с " > " — это ответы интерпретатора на выражения):

> (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")
    }
}

Аппаратный стек

Основная статья: Распределение памяти на основе стека

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

Базовая архитектура стека

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

Две операции, применимые ко всем стекам:

• Операция push : адрес в указателе стека корректируется в соответствии с размером элемента данных, и элемент данных записывается в место, на которое указывает указатель стека.
• Операция извлечения или извлечения : считывается элемент данных в текущем местоположении, на которое указывает указатель стека, и указатель стека перемещается на расстояние, соответствующее размеру этого элемента данных.

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

Указатели стека могут указывать на начало стека или на ограниченный диапазон адресов выше или ниже начала координат (в зависимости от направления роста стека); однако указатель стека не может пересекать начало стека. Другими словами, если начало стека находится по адресу 1000 и стек растет вниз (к адресам 999, 998 и т. д.), указатель стека никогда не должен увеличиваться за пределы 1000 (до 1001 или выше). Если операция извлечения стека приводит к перемещению указателя стека за пределы начала стека, опустошение стека происходит . Если операция push приводит к тому, что указатель стека увеличивается или уменьшается за пределы максимального размера стека, переполнение стека происходит .

Некоторые среды, которые сильно полагаются на стеки, могут предоставлять дополнительные операции, например:

• Дубликат : верхний элемент извлекается, а затем дважды нажимается, так что две копии бывшего верхнего элемента теперь лежат вверху.
• Peek : самый верхний элемент проверяется (или возвращается), но указатель стека и размер стека не изменяются (это означает, что элемент остается в стеке). Эту операцию также можно назвать верхней операцией.
• Обмен или обмен : два верхних предмета в стопке меняются местами.
• Поворот (или переворот) : 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.

Стек в основной памяти

Многие CISC -типа ЦП конструкции , включая x86 , Z80 и 6502 , имеют выделенный регистр для использования в качестве указателя стека вызовов с выделенными инструкциями вызова, возврата, отправки и извлечения, которые неявно обновляют выделенный регистр, тем самым увеличивая кода плотность . Некоторые процессоры CISC, такие как PDP-11 и 68000 , также имеют специальные режимы адресации для реализации стеков , обычно с полувыделенным указателем стека (например, A7 в 68000). Напротив, большинство конструкций ЦП RISC не имеют выделенных инструкций стека, и поэтому большинство, если не все, регистры могут использоваться в качестве указателей стека по мере необходимости.

Стек в регистрах или выделенной памяти

Программируемый карманный калькулятор HP-42S 1988 года имел, как и почти все калькуляторы компании того времени , четырехуровневый стек и мог одновременно отображать два из четырех значений регистров стека X, Y, Z и T. время из-за двухстрочного дисплея, здесь X и Y. В более поздних моделях, таких как HP-48 , количество уровней было увеличено и теперь ограничено только объемом памяти.

Основная статья: Штабелер

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

Ряд мэйнфреймов и миникомпьютеров представляли собой стековые машины, наиболее известными из которых были большие системы Берроуза . Другие примеры включают машины CISC HP 3000 и машины CISC от Tandem Computers .

Архитектура x87 с плавающей запятой является примером набора регистров, организованных в виде стека, где также возможен прямой доступ к отдельным регистрам (относительно текущей вершины).

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

Sun SPARC , AMD Am29000 и Intel i960 — все это примеры архитектур, которые используют окна регистров в стеке регистров в качестве еще одной стратегии, позволяющей избежать использования медленной основной памяти для аргументов функций и возвращаемых значений.

Существует также ряд небольших микропроцессоров, которые реализуют стек непосредственно аппаратно, а некоторые микроконтроллеры имеют стек фиксированной глубины, к которому нет прямого доступа. Примерами являются микроконтроллеры PIC , Computer Cowboys MuP21 , линейка Harris RTX и Novix NC4016 . По крайней мере, одно семейство микроконтроллеров, COP400 , реализует стек либо непосредственно в аппаратном обеспечении, либо в оперативной памяти через указатель стека, в зависимости от устройства. Многие микропроцессоры на основе стека использовались для реализации языка программирования Forth на уровне микрокода .

Применение стеков

Оценка выражения и синтаксический анализ

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

Возврат

Основная статья: Возврат

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

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

Управление памятью во время компиляции

Основные статьи: Распределение памяти на основе стека и стековая машина

Типичный стек вызовов, хранящий локальные данные и информацию о вызовах для нескольких уровней вызовов процедур. Этот стек растет вниз от своего начала. Указатель стека указывает на текущую самую верхнюю датум в стеке. Операция push уменьшает указатель и копирует данные в стек; операция pop копирует данные из стека, а затем увеличивает указатель. Каждая процедура, вызываемая в программе, сохраняет информацию о возврате процедуры (желтым цветом) и локальные данные (другими цветами), помещая их в стек. Этот тип реализации стека чрезвычайно распространен, но он уязвим для атак переполнения буфера (см. текст).

Ряд языков программирования ориентированы на стек , то есть они определяют большинство основных операций (сложение двух чисел, вывод символа) как получение аргументов из стека и помещение возвращаемых значений обратно в стек. Например, PostScript имеет стек возврата и стек операндов, а также стек состояния графики и стек словаря. Многие виртуальные машины также ориентированы на стек, включая машину с p-кодом и виртуальную машину Java .

Почти все соглашения о вызовах ‍—‌способы, которыми подпрограммы получают свои параметры и возвращают результаты‍—‌используют специальный стек (« стек вызовов ») для хранения информации о вызове процедуры/функции и вложенности, чтобы переключиться на контекст вызываемой функции. и восстановить функцию вызывающего абонента после завершения вызова. Функции следуют протоколу времени выполнения между вызывающим и вызываемым объектами для сохранения аргументов и возвращаемого значения в стеке. Стеки — важный способ поддержки вложенных или рекурсивных вызовов функций. Этот тип стека неявно используется компилятором для поддержки операторов CALL и RETURN (или их эквивалентов) и не подвергается непосредственному манипулированию программистом.

Некоторые языки программирования используют стек для хранения данных, локальных для процедуры. Пространство для элементов локальных данных выделяется из стека при входе в процедуру и освобождается при выходе из процедуры. Язык программирования C обычно реализуется таким образом. Использование одного и того же стека для вызовов данных и процедур имеет важные последствия для безопасности ( см. ниже ), о которых программист должен знать, чтобы избежать серьезных ошибок безопасности в программе.

Эффективные алгоритмы

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

• Сканирование Грэма — алгоритм выпуклой оболочки двумерной системы точек. Выпуклая оболочка подмножества входных данных сохраняется в стеке, который используется для поиска и удаления вогнутостей на границе при добавлении новой точки в оболочку.
• Часть алгоритма SMAWK для поиска минимумов строк монотонной матрицы использует стеки аналогично сканированию Грэма.
• Все ближайшие меньшие значения — проблема поиска для каждого числа в массиве ближайшего предшествующего числа, меньшего его. Один из алгоритмов решения этой проблемы использует стек для хранения набора кандидатов на ближайшее меньшее значение. Для каждой позиции в массиве стек извлекается до тех пор, пока на его вершине не будет найдено меньшее значение, а затем значение в новой позиции помещается в стек.
• Алгоритм цепочки ближайших соседей — метод агломеративной иерархической кластеризации , основанный на поддержании стека кластеров, каждый из которых является ближайшим соседом своего предшественника в стеке. Когда этот метод находит пару кластеров, которые являются ближайшими соседями, они извлекаются и объединяются.

Безопасность

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

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

Злоумышленники могут попытаться провести атаку с разрушением стека , которая использует этот тип реализации, предоставляя вводимые данные слишком большого размера программе, которая не проверяет длину ввода. Такая программа может полностью скопировать данные в определенное место в стеке и при этом изменить адреса возврата для процедур, которые ее вызвали. Злоумышленник может экспериментировать, чтобы найти определенный тип данных, которые могут быть предоставлены такой программе, чтобы адрес возврата текущей процедуры был сброшен и указывал на область внутри самого стека (и внутри данных, предоставленных злоумышленником). который, в свою очередь, содержит инструкции, выполняющие несанкционированные операции.

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

См. также

• Список структур данных
• Очередь
• Двусторонняя очередь
• ФИФО (вычисления и электроника)
• Стек оперативной памяти (он же автоматический стек памяти)

Ссылки

• В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Ограниченный стек» . Словарь алгоритмов и структур данных . НИСТ .

Дальнейшее чтение

• Дональд Кнут . Искусство компьютерного программирования , Том 1: Фундаментальные алгоритмы , Третье издание. Аддисон-Уэсли, 1997. ISBN   0-201-89683-4 . Раздел 2.2.1: Стеки, очереди и деки, стр. 238–243.
• Лангмаак, Ганс [на немецком языке] (2015) [14 ноября 2014 г.]. Написано в Киле, Германия. Работы Фридриха Л. Бауэра и Клауса Самельсона 1950-х годов по введению терминов «принцип подвала» и «подвал-автомат» ) ( PDF ( на немецком языке). Йена, Германия: Институт компьютерных наук, Кильский университет Кристиана Альбрехта. стр. 19–29. Архивировано (PDF) из оригинала 14 ноября 2022 г. Проверено 14 ноября 2022 г. (11 страниц) (Примечание. Опубликовано в Fothe & Wilke .)
• Гус, Герхард [на немецком языке] (7 августа 2017 г.). История немецкоязычной информатики - языки программирования и проектирование компиляторов [ История информатики в немецкоязычных странах - Языки программирования и проектирование компиляторов ] (PDF) (на немецком языке). Карлсруэ, Германия: Факультет компьютерных наук Технологического института Карлсруэ (KIT). Архивировано (PDF) из оригинала 19 мая 2022 г. Проверено 14 ноября 2022 г. (11 страниц)

Внешние ссылки

• Stack Machines – новая волна
• Ограничивающая глубина стека
• Анализ размера стека для программ, управляемых прерываниями