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

Абстрактный тип данных

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

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

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

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

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

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

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

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

История

Стэки вошли в литературу по информатике в 1946 году, когда Алан Тьюринг использовал термины «захоронить» и «вытащить из погребения» как средство вызова подпрограмм и возврата из них. ^{[2] [3]} Подпрограммы и двухуровневый стек уже были реализованы в Z4 Конрада Цузе в 1945 году. ^{[4] [5]}

Клаус Самельсон и Фридрих Л. Бауэр из Технического университета Мюнхена предложили идею стека под названием Operationskeller («операционный подвал») в 1955 году ^{[6] [7]} и подали патент в 1957 году. ^{[8] [9] [10] [ 11]} В марте 1988 года, когда Самельсон уже умер, Бауэр получил премию IEEE Computer Pioneer Award за изобретение принципа стека. ^{[12] [7]} Подобные концепции были независимо развиты Чарльзом Леонардом Хэмблином в первой половине 1954 года ^{[13] [7]} и Вильгельмом Каммерером  [де] с его autotisches Gedächtnis («автоматическая память») в 1958 году. ^{[14] [15] [7]}

Стопки часто описываются по аналогии с подпружиненной стопкой тарелок в кафетерии. ^{[16] [1] [17]} Чистые тарелки кладутся наверх стопки, отталкивая все уже находящиеся там тарелки. Когда верхняя пластина удаляется из стопки, та, что находится под ней, поднимается и становится новой верхней пластиной.

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

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

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

Выполнение

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

Множество

Массив можно использовать для реализации (ограниченного) стека следующим образом. Первый элемент, обычно с нулевым смещением , является нижним, в результате array[0]чего первый элемент помещается в стек, а последний элемент извлекается. Программа должна отслеживать размер (длину) стека, используя переменную top , которая записывает количество элементов, помещенных на данный момент, указывая тем самым на место в массиве, куда должен быть вставлен следующий элемент (при условии, что значение равно нулю). соглашение об индексировании на основе). Таким образом, сам стек можно эффективно реализовать как трехэлементную структуру:

стек структур : максимальный размер: целое число верх: целое число items: массив элементов

процедура инициализации (stk: стек, размер: целое число): stk.items ← новый массив элементов размера , изначально пустой stk.maxsize ← размер stk.top ← 0

Операция push добавляет элемент и увеличивает верхний индекс после проверки на переполнение:

процедура push(stk : стек, x : элемент): if stk.top = stk.maxsize: сообщить об ошибке переполнения еще : stk.items[stk.top] ← x стк.топ ← стк.топ + 1

Аналогично, pop уменьшает верхний индекс после проверки на отсутствие переполнения и возвращает элемент, который ранее был верхним:

процедура pop(stk : stack): если stk.top = 0: сообщить об ошибке переполнения еще : stk.top ← stk.top − 1 r ← stk.items[stk.top] вернуть р

Используя динамический массив , можно реализовать стек, который может увеличиваться или уменьшаться по мере необходимости. Размер стека — это просто размер динамического массива, что является очень эффективной реализацией стека, поскольку добавление элементов в конец динамического массива или удаление элементов из него требует амортизированного времени O(1).

Связанный список

Другой вариант реализации стеков — использование односвязного списка . В этом случае стек является указателем на «голову» списка, возможно, со счетчиком для отслеживания размера списка:

каркас структуры : данные: элемент следующий: кадр или ноль

стек структур : голова: рамка или ноль размер: целое число

инициализация процедуры (stk: стек): stk.head ← ноль stk.size ← 0

Нажатие и извлечение элементов происходит в начале списка; в этой реализации переполнение невозможно (если не исчерпана память):

процедура push(stk: стек, x: элемент): newhead ← новый кадр newhead.data ← x newhead.next ← stk.head stk.head ← newhead stk.size ← stk.size + 1

процедура pop(stk : stack): если stk.head = nil: сообщить об ошибке переполнения г ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 вернуть р

Стеки и языки программирования

Некоторые языки, такие как Perl , LISP , JavaScript и Python , делают операции стека push и pop доступными для своих стандартных типов списка/массива. Некоторые языки, особенно языки семейства Forth (включая PostScript ), разработаны на основе определяемых языком стеков, которые непосредственно видны программисту и которыми он может управлять.

Ниже приведен пример управления стеком в Common Lisp (« > » — это приглашение интерпретатора Lisp; строки, не начинающиеся с « > », — это ответы интерпретатора на выражения):

> ( setf stack ( list 'a 'b'c ) ) ;; установите переменную «стек» ( A B C ) > ( pop stack ) ;; получить верхний (крайний левый) элемент, следует изменить стек A > stack ;; проверьте значение стека ( BC ) > ( push 'new stack ) ;; добавить новую вершину в стек ( NEW B C )                     

Некоторые типы контейнеров стандартной библиотеки C++ имеют операции push_back и pop_back с семантикой LIFO; кроме того, класс шаблона стека адаптирует существующие контейнеры для предоставления ограниченного API только с операциями push/pop. В PHP есть класс SplStack. Библиотека Java содержит класс, являющийся специализацией . Ниже приведен пример программы на языке Java , использующей этот класс.StackVector

импортировать java.util.Stack ; класс  StackDemo { public static void main ( String [] args ) { Stack < String > stack = new Stack < String > (); куча . нажать ( «А» ); // Вставляем "A" в стек stack . нажать ( «Б» ); // Вставляем "B" в стек stack . нажать ( "С" ); // Вставляем «C» в стек stack . нажать ( «Д» ); // Вставляем "D" в стек System . вне . println ( стек . peek ()); // Печатает верхнюю часть стека ("D") stack . поп (); // удаление верхнего ("D") стека . поп (); // удаляем следующую вершину ("C") } }                          

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

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

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

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

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

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

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

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

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

• Дубликат : верхний элемент извлекается, а затем дважды нажимается, так что две копии бывшего верхнего элемента теперь лежат вверху.
• Peek : самый верхний элемент проверяется (или возвращается), но указатель стека и размер стека не изменяются (то есть элемент остается в стеке). Эту операцию также можно назвать верхней операцией.
• Обмен или обмен : два верхних предмета в стопке меняются местами.
• Поворот (или переворот) : n самых верхних элементов перемещаются в стеке поочередно. Например, если n = 3 , элементы 1, 2 и 3 в стеке перемещаются на позиции 2, 3 и 1 в стеке соответственно. Возможны многие варианты этой операции, наиболее распространенные из которых называются поворотом влево и поворотом вправо.

Стеки часто визуализируются растущими снизу вверх (как в реальных стеках). Их также можно визуализировать растущими слева направо, где верх находится крайне справа, или даже растущими сверху вниз. Важной особенностью является то, что нижняя часть стопки находится в фиксированном положении. Иллюстрация в этом разделе представляет собой пример визуализации роста сверху вниз: верх (28) — это «низ» стека, поскольку «верх» стека (9) — это место, откуда элементы помещаются или извлекаются.

Поворот вправо переместит первый элемент в третью позицию, второй в первую и третий во вторую. Вот две эквивалентные визуализации этого процесса:

яблоко бананбанан ===повернуть вправо==> огурецогурец яблоко

огурец яблокобанан ===поворот влево==> огурецяблоко банан

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Возврат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

• Портал компьютерного программирования

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

Примечания

1. Напротив, очередь работает «первым пришел — первым вышел», что обозначается аббревиатурой FIFO .

Рекомендации

1. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 232–233. ISBN 0-262-03384-4.
2. Тьюринг, Алан Мэтисон (19 марта 1946) [1945]. Предложения по разработке в математическом отделе автоматической вычислительной машины (АВС) .(Примечание. Представлено 19 марта 1946 г. Исполнительному комитету Национальной физической лаборатории (Великобритания).)
3. Карпентер, Брайан Эдвард ; Доран, Роберт Уильям (1 января 1977 г.) [октябрь 1975 г.]. «Другая машина Тьюринга». Компьютерный журнал . 20 (3): 269–279. дои : 10.1093/comjnl/20.3.269 .(11 страниц)
4. Блаау, Геррит Энн ; Брукс-младший, Фредерик Филлипс (1997). Компьютерная архитектура: концепции и эволюция . Бостон, Массачусетс, США: Addison-Wesley Longman Publishing Co., Inc.
5. ЛаФорест, Чарльз Эрик (апрель 2007 г.). «2.1 Лукасевич и первое поколение: 2.1.2 Германия: Конрад Цузе (1910–1995); 2.2 Первое поколение стековых компьютеров: 2.2.1 Zuse Z4». Стековая компьютерная архитектура второго поколения (PDF) (диссертация). Ватерлоо, Канада: Университет Ватерлоо . стр. 8, 11. Архивировано (PDF) из оригинала 20 января 2022 г. Проверено 2 июля 2022 г.(178 страниц)
6. Самельсон, Клаус (1957) [1955]. Написано в Международном коллоквиуме по проблемам науки, Дрезден, Германия. Проблема дер Programmierungstechnik (на немецком языке). Берлин, Германия: VEB Deutscher Verlag der Wissenschaften . стр. 61–68.(Примечание. Эта статья была впервые представлена ​​в 1955 году. В ней описан стек чисел ( Zahlenkeller ), но названа она линейной вспомогательной памятью ( lineer Hilfsspeicher ).)
7. Фоте, Майкл; Уилке, Томас, ред. (2015) [14 ноября 2014 г.]. Написано в Йене, Германия. Келлер, Stack und autotisches Gedächtnis – eine Struktur mit Potenzial [Подвал, стек и автоматическая память - структура с потенциалом ] (PDF) (Tagungsband zum Kolloquium, 14 ноября 2014 г., Йена). Серия GI: Конспекты лекций по информатике (LNI) - Тематика (на немецком языке). Том. Т-7. Бонн, Германия: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH. ISBN 978-3-88579-426-4. ISSN  1614-3213. Архивировано (PDF) из оригинала 12 апреля 2020 г. Проверено 12 апреля 2020 г.[1] (77 страниц)
8. Бауэр, Фридрих Людвиг ; Самельсон, Клаус (30 марта 1957 г.). «Verfahren zur autotischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens» (на немецком языке). Мюнхен, Германия: Deutsches Patentamt. ДЕ-ПС 1094019 . Проверено 1 октября 2010 г.
9. Бауэр, Фридрих Людвиг ; Гус, Герхард [на немецком языке] (1982). Informatik – Eine einführende Übersicht (на немецком языке). Том. Часть 1 (3-е изд.). Берлин: Springer-Verlag . п. 222. ИСБН 3-540-11722-9. Die Bezeichnung 'Keller' hierfür wurde von Bauer und Samelson в einer deutschen Patentanmeldung vom 30. Marz 1957 eingeführt.
10. Самельсон, Клаус ; Бауэр, Фридрих Людвиг (1959). «Sequentielle Formelübersetzung» [Последовательный перевод формул]. Elektronische Rechenanlagen (на немецком языке). 1 (4): 176–182.
11. Самельсон, Клаус ; Бауэр, Фридрих Людвиг (1960). «Последовательный перевод формул». Коммуникации АКМ . 3 (2): 76–83. дои : 10.1145/366959.366968 . S2CID  16646147.
12. "IEEE-Computer-Pioneer-Preis - Бауэр, Фридрих Л." Технический университет Мюнхена , факультет компьютерных наук. 1 января 1989 г. Архивировано из оригинала 07.11.2017.
13. Хэмблин, Чарльз Леонард (май 1957 г.). Схема безадресного кодирования, основанная на математической нотации (PDF) (машинописный текст). Технологический университет Нового Южного Уэльса . стр. 121-1–121-12. Архивировано (PDF) из оригинала 12 апреля 2020 г. Проверено 12 апреля 2020 г.(12 страниц)
14. Кеммерер, Вильгельм [на немецком языке] (11 декабря 1958). Ziffern-Rechenautomat mit Programmierung nach mathematischem Formelbild (Габилитационная диссертация) (на немецком языке). Йена, Германия: Mathematisch-naturwissenschaftliche Fakultät, Университет Фридриха Шиллера . урна:nbn:de:gbv:27-20130731-133019-7. ППН:756275237. Архивировано из оригинала 14 октября 2023 г. Проверено 14 октября 2023 г.[2] (2+69 страниц)
15. Каммерер, Вильгельм [на немецком языке] (1960). Ziffernrechenautomaten . Elektronisches Rechnen und Regeln (на немецком языке). Том. 1. Берлин, Германия: Akademie-Verlag .
16. Болл, Джон А. (1978). Алгоритмы калькуляторов РПН (1-е изд.). Кембридж, Массачусетс, США: Wiley-Interscience , John Wiley & Sons, Inc. ISBN  978-0-471-03070-6. LCCN  77-14977.
17. Годзе, Атул П.; Годзе, Дипали А. (1 января 2010 г.). Компьютерная архитектура. Технические публикации. стр. 1–56. ISBN 978-8-18431534-9. Проверено 30 января 2015 г.
18. Горовиц, Эллис (1984). Основы структур данных в Паскале . Пресса по информатике . п. 67.
19. Грэм, Рональд «Рон» Льюис (1972). Эффективный алгоритм определения выпуклой оболочки конечного плоского множества (PDF) . Письма об обработке информации. 1. Том. 1. С. 132–133. Архивировано (PDF) из оригинала 22 октября 2022 г.
20. Аггарвал, Алок; Клове, Мария М .; Моран, Шломо ; Шор, Питер ; Уилбер, Роберт (1987). «Геометрические приложения алгоритма матричного поиска». Алгоритмика . 2 (1–4): 195–208. дои : 10.1007/BF01840359. MR  0895444. S2CID  7932878..
21. Беркман, Омер; Шибер, Барух ; Вишкин, Узи (1993). «Оптимальные дважды логарифмические параллельные алгоритмы, основанные на поиске всех ближайших меньших значений». Журнал алгоритмов . 14 (3): 344–370. CiteSeerX 10.1.1.55.5669 . дои : 10.1006/jagm.1993.1018. .
22. Мурта, Фионн (1983). «Обзор последних достижений в алгоритмах иерархической кластеризации» (PDF) . Компьютерный журнал . 26 (4): 354–359. дои : 10.1093/comjnl/26.4.354 ..

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

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

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

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

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