Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Чтобы узнать об использовании термина LIFO в бухгалтерском учете, см. LIFO (бухгалтерский учет) . Чтобы узнать об использовании термина «отжимание» в силовой тренировке, см. « Отжимание (упражнение)» .
Для использования в других целях, см Стек (значения) .
Как и в случае стопки тарелок, добавление или удаление возможно только сверху.
Простое представление среды выполнения стека с помощью операций push и pop .

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

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

Порядок, в котором элементы выходят из стека, дает начало его альтернативному имени LIFO ( последний пришел , первый вышел ). Кроме того, PEEK операция может дать доступ к вершине без изменения стеки. [1] Название «стек» для этого типа структуры происходит от аналогии с набором физических элементов, уложенных друг на друга. Эта структура позволяет легко снять элемент с вершины стека, в то время как для того, чтобы добраться до элемента, находящегося глубже в стеке, может потребоваться сначала снять несколько других элементов. [2]

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

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

История [ править ]

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

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

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

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

Несущественные операции [ править ]

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

Программные стеки [ править ]

Реализация [ править ]

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

Массив [ править ]

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

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

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

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

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

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

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

Связанный список [ править ]

Другой вариант реализации стеков - использование односвязного списка . Стек тогда является указателем на "голову" списка, возможно, со счетчиком для отслеживания размера списка:

каркас конструкции : данные: элемент следующий: кадр или ноль
стек структуры : голова: рамка или ноль размер: целое число
инициализация процедуры (stk: stack): stk.head ← ноль stk.size ← 0

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

процедура push (stk: stack, x: item): newhead ← новый кадр 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 вернуть г

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

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

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

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

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

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

Аппаратный стек [ править ]

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

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

Базовая архитектура стека [ править ]

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

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

Ко всем стекам применимы две операции:

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

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

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

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

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

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

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

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

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

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

Применение стеков [ править ]

Оценка выражений и синтаксический анализ [ править ]

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

Возврат [ править ]

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

Еще одно важное применение стеков - поиск с возвратом.. Рассмотрим простой пример поиска правильного пути в лабиринте. Есть ряд точек, от начальной до конечной. Начнем с одной точки. Чтобы добраться до конечного пункта назначения, есть несколько путей. Допустим, мы выбрали случайный путь. Пройдя определенный путь, мы понимаем, что выбранный нами путь неправильный. Итак, нам нужно найти способ вернуться к началу этого пути. Это можно сделать с помощью стеков. С помощью стеков мы запоминаем точку, в которой достигли. Это делается путем помещения этой точки в стек. В случае, если мы окажемся на неправильном пути, мы можем вытолкнуть последнюю точку из стека и, таким образом, вернуться к последней точке и продолжить наш поиск, чтобы найти правильный путь. Это называется возвратом.

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

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

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

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

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

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

Эффективные алгоритмы [ править ]

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

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

Безопасность [ править ]

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Напротив, простая QUEUE управляет FIFO ( первым пришел - первым ушел ).
  2. ^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.
  3. ^ Тьюринг, Алан Матисон (1946-03-19) [1945], Предложения по развитию в математическом отделе автоматического вычислительного двигателя (ACE) (NB. Представлено 1946-03-19 перед Исполнительным комитетом Национальной физической лаборатории (Великобритания).)
  4. ^ Карпентер, Брайан Эдвард ; Доран, Роберт Уильям (1977-01-01) [октябрь 1975]. «Другая машина Тьюринга» . Компьютерный журнал . 20 (3): 269–279. DOI : 10.1093 / comjnl / 20.3.269 . (11 страниц)
  5. ^ Самельсон, Клаус (1957) [1955]. Написано в Internationales Kolloquium über Probleme der Rechentechnik, Дрезден, Германия. Probleme der Programmierungstechnik (на немецком языке). Берлин, Германия: VEB Deutscher Verlag der Wissenschaften . С. 61–68.(NB. Эта статья была впервые представлена ​​в 1955 году. Она описывает стек чисел ( Zahlenkeller ), но называет его линейной вспомогательной памятью ( linearer Hilfsspeicher ).)
  6. ^ a b Фот, Майкл; Wilke, Thomas, eds. (2015). Келлер, Stack und automatisches 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. Архивации (PDF) с оригинала на 2020-04-12 . Проверено 12 апреля 2020 . (77 страниц)
  7. ^ Бауэр, Фридрих Людвиг ; Самельсон, Клаус (1957-03-30). "Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens" (на немецком языке). Мюнхен, Германия: Deutsches Patentamt. DE-PS 1094019 . Проверено 1 октября 2010 .
  8. ^ Бауэр, Фридрих Людвиг ; Гус, Герхард (1982). Informatik - Eine einführende Übersicht (на немецком языке). Часть 1 (3-е изд.). Берлин: Springer-Verlag . п. 222. ISBN. 3-540-11722-9. Die Bezeichnung 'Keller' hierfür wurde von Bauer und Samelson in einer deutschen Patentanmeldung vom 30. März 1957 eingeführt.
  9. ^ Самельсон, Клаус ; Бауэр, Фридрих Людвиг (1959). «Sequentielle Formelübersetzung» [Последовательный перевод формул]. Elektronische Rechenanlagen (на немецком языке). 1 (4): 176–182.
  10. ^ Самельсон, Клаус ; Бауэр, Фридрих Людвиг (1960). «Последовательный перевод формул». Коммуникации ACM . 3 (2): 76–83. DOI : 10.1145 / 366959.366968 . S2CID 16646147 . 
  11. ^ "IEEE-Computer-Pioneer-Preis - Бауэр, Фридрих Л." Технический университет Мюнхена , факультет компьютерных наук. 1989-01-01. Архивировано из оригинала на 2017-11-07.
  12. ^ Хэмблин, Чарльз Леонард (май 1957 г.). Схема безадресного кодирования на основе математической нотации (PDF) (машинописный текст). Технологический университет Нового Южного Уэльса . С. 121-1–121-12. Архивации (PDF) с оригинала на 2020-04-12 . Проверено 12 апреля 2020 . (12 страниц)
  13. ^ Kämmerer, Вильгельм (1958). Ziffern-Rechenautomat mit Programmierung nach Mathematischem Formelbild (докторская диссертация) (на немецком языке). Friedrich-Schiller-Universität , Йена, Германия.
  14. ^ Каммерер, Вильгельм (1960). Ziffernrechenautomaten . Elektronisches Rechnen und Regeln (на немецком языке). 1 . Берлин, Германия: Akademie-Verlag .
  15. ^ Болл, Джон А. (1978). Алгоритмы для вычислителей РПН (1-е изд.). Кембридж, Массачусетс, США: Wiley-Interscience , John Wiley & Sons, Inc. ISBN  978-0-471-03070-6.
  16. ^ Годсе, Атул П .; Годсе, Дипали А. (01.01.2010). Компьютерная архитектура . Технические публикации. С. 1–56. ISBN 978-8-18431534-9. Проверено 30 января 2015 .
  17. ↑ Горовиц, Эллис: «Основы структур данных в Паскале», стр. 67. Computer Science Press, 1984
  18. Перейти ↑ Graham, RL (1972). Эффективный алгоритм определения выпуклой оболочки конечного плоского множества . Письма об обработке информации 1, 132-133
  19. ^ Аггарваль, Alok; Клаве, Мария М .; Моран, Шломо ; Шор, Петр ; Уилбер, Роберт (1987), "Геометрические применения алгоритма матричного-поиск", Algorithmica , 2 (1-4): 195-208, DOI : 10.1007 / BF01840359 , МР 0895444 , S2CID 7932878  .
  20. ^ Беркман, Омер; Шибер, Барух; Вишкин, Узи (1993), "Оптимальные дважды логарифмические параллельные алгоритмы, основанные на нахождении всех ближайших меньших значений", Журнал алгоритмов , 14 (3): 344–370, CiteSeerX 10.1.1.55.5669 , doi : 10.1006 / jagm.1993.1018 .
  21. ^ Мерта, Финн (1983), "Обзор последних достижений в области иерархических алгоритмов кластеризации" (PDF) , Компьютерный журнал , 26 (4): 354-359, DOI : 10,1093 / comjnl / 26.4.354 .
  •  Эта статья включает материалы, являющиеся общественным достоянием  из  документа NIST :  Блэк, Пол Э. «Ограниченный стек» . Словарь алгоритмов и структур данных .

Дальнейшее чтение [ править ]

  • Дональд Кнут . Искусство программирования , Том 1: Основные алгоритмы , третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89683-4 . Раздел 2.2.1: Стеки, очереди и дек, стр. 238–243. 

Внешние ссылки [ править ]

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