Из Википедии, бесплатной энциклопедии
  (Перенаправлено из стека (структура данных) )
Перейти к навигации Перейти к поиску
Чтобы узнать об использовании термина 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" в стек  стека . push ( "C" );  // Вставляем "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. ^ а б Фоте, Майкл; 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 (докторская диссертация) (на немецком языке). Университет Фридриха Шиллера , Йена, Германия.
  14. ^ Kämmerer, Вильгельм (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. ^ Аггарвал, Алок; Клаве, Мария М .; Моран, Шломо ; Шор, Петр ; Уилбер, Роберт (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 КБ)