Стек (абстрактный тип данных)
В информатике стек — это абстрактный тип данных , который служит набором элементов с двумя основными операциями:
- Push , который добавляет элемент в коллекцию, и
- Pop , который удаляет последний добавленный элемент.
Кроме того, операция просмотра может без изменения стека вернуть значение последнего добавленного элемента. имен Стек — это аналогия набора физических предметов, сложенных друг на друга, например стопки тарелок.
Порядок, в котором элемент добавляется в стек или удаляется из него, описывается как «последний вошел — первым вышел » и обозначается аббревиатурой LIFO . [номер 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] и Вильгельм Кеммерер с его автоматической памятью («автоматическая память») в 1958 году. [14] [15] [7]
Стопки часто описываются по аналогии с подпружиненной стопкой тарелок в кафетерии. [16] [1] [17] Чистые тарелки кладут наверх стопки, отодвигая все уже находящиеся там тарелки. Когда верхняя пластина удаляется из стопки, та, что находится под ней, поднимается и становится новой верхней пластиной.
Необязательные операции
[ редактировать ]Во многих реализациях стек содержит больше операций, чем основные операции «push» и «pop». Примером несущественной операции является «вершина стека» или «просмотр», которая наблюдает за верхним элементом, не удаляя его из стека. [18] Поскольку эту операцию можно разбить на «выталкивание», за которым следует «нажатие», чтобы вернуть те же данные в стек, это не считается важной операцией. Если стек пуст, при выполнении операций «верхнего стека» или «извлечения» возникнет состояние опустошения. Кроме того, многие реализации обеспечивают проверку того, пуст ли стек, и операцию, возвращающую его размер.
Программные стеки
[ редактировать ]Выполнение
[ редактировать ]Стек можно легко реализовать либо через массив , либо через связанный список , поскольку это всего лишь частный случай списка. В любом случае структуру данных как стек идентифицирует не реализация, а интерфейс: пользователю разрешено только извлекать или помещать элементы в массив или связанный список с небольшим количеством других вспомогательных операций. Ниже будут продемонстрированы обе реализации с использованием псевдокода .
Множество
[ редактировать ]Массив можно использовать для реализации (ограниченного) стека следующим образом. Первый элемент, обычно на нулевом смещении , является нижним, в результате чего 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 stackA> 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 bananabanana ===right rotate==> cucumbercucumber apple
cucumber applebanana ===left rotate==> cucumberapple banana
Стек обычно представляется в компьютерах блоком ячеек памяти, «нижняя часть» которого находится в фиксированном месте, а указатель стека содержит адрес текущей «верхней» ячейки в стеке. «Верхняя» и «нижняя» номенклатура используется независимо от того, действительно ли стек увеличивается в сторону более высоких адресов памяти.
При помещении элемента в стек указатель стека корректируется на размер элемента (уменьшается или увеличивается, в зависимости от направления роста стека в памяти), указывает его на следующую ячейку и копируется новый верхний элемент в область стека. Опять же, в зависимости от конкретной реализации, в конце операции отправки указатель стека может указывать на следующее неиспользуемое место в стеке или на самый верхний элемент в стеке. Если стек указывает на текущий самый верхний элемент, указатель стека будет обновлен перед тем, как в стек будет помещен новый элемент; если он указывает на следующее доступное место в стеке, он будет обновлен после помещения нового элемента в стек.
Извлечение стека — это просто обратное нажатие. Самый верхний элемент стека удаляется, а указатель стека обновляется в порядке, противоположном тому, который использовался в операции 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 . По крайней мере, одно семейство микроконтроллеров, COP400 , реализует стек либо непосредственно в аппаратном обеспечении, либо в оперативной памяти через указатель стека, в зависимости от устройства. Многие микропроцессоры на основе стека использовались для реализации языка программирования Forth на уровне микрокода .
Применение стеков
[ редактировать ]Оценка выражения и синтаксический анализ
[ редактировать ]Калькуляторы, использующие обратную польскую запись, используют структуру стека для хранения значений. Выражения могут быть представлены в префиксной, постфиксной или инфиксной нотации, а преобразование из одной формы в другую может выполняться с использованием стека. Многие компиляторы используют стек для анализа синтаксиса перед переводом в код низкого уровня. Большинство языков программирования являются контекстно-свободными языками , что позволяет анализировать их с помощью стековых машин.
Возврат
[ редактировать ]Еще одно важное применение стеков — возврат . Иллюстрацией этого является простой пример поиска правильного пути в лабиринте, который содержит ряд точек, начальную точку, несколько путей и пункт назначения. Если необходимо выбрать случайные пути, то после следования по неправильному пути должен быть метод, с помощью которого можно вернуться к началу этого пути. Этого можно достичь за счет использования стеков, поскольку последняя правильная точка может быть помещена в стек и извлечена из стека в случае неправильного пути.
Прототипическим примером алгоритма поиска с возвратом является поиск в глубину , который находит все вершины графа, до которых можно добраться из указанной начальной вершины. Другие применения обратного отслеживания включают поиск в пространствах, которые представляют собой потенциальные решения проблемы оптимизации. Ветви и границы — это метод выполнения таких поисков с возвратом без исчерпывающего поиска всех потенциальных решений в таком пространстве.
Управление памятью во время компиляции
[ редактировать ]Ряд языков программирования ориентированы на стек , то есть они определяют большинство основных операций (сложение двух чисел, вывод символа) как получение аргументов из стека и помещение возвращаемых значений обратно в стек. Например, PostScript имеет стек возврата и стек операндов, а также стек состояния графики и стек словаря. Многие виртуальные машины также ориентированы на стек, включая машину с p-кодом и виртуальную машину Java .
Почти все соглашения о вызовах —способы, которыми подпрограммы получают свои параметры и возвращают результаты—используют специальный стек (« стек вызовов ») для хранения информации о вызове процедуры/функции и вложенности, чтобы переключиться на контекст вызываемой функции. и восстановить функцию вызывающего абонента после завершения вызова. Функции следуют протоколу времени выполнения между вызывающим и вызываемым объектами для сохранения аргументов и возвращаемого значения в стеке. Стеки — важный способ поддержки вложенных или рекурсивных вызовов функций. Этот тип стека неявно используется компилятором для поддержки операторов CALL и RETURN (или их эквивалентов) и не подвергается непосредственному манипулированию программистом.
Некоторые языки программирования используют стек для хранения данных, локальных для процедуры. Пространство для элементов локальных данных выделяется из стека при входе в процедуру и освобождается при выходе из процедуры. Язык программирования C обычно реализуется таким образом. Использование одного и того же стека для вызовов данных и процедур имеет важные последствия для безопасности ( см. ниже ), о которых программист должен знать, чтобы избежать серьезных ошибок безопасности в программе.
Эффективные алгоритмы
[ редактировать ]Некоторые алгоритмы используют стек (отдельный от обычного стека вызовов функций большинства языков программирования) в качестве основной структуры данных , с помощью которой они организуют свою информацию. К ним относятся:
- Сканирование Грэма — алгоритм выпуклой оболочки двумерной системы точек. Выпуклая оболочка подмножества входных данных сохраняется в стеке, который используется для поиска и удаления вогнутостей на границе при добавлении новой точки в оболочку. [19]
- Часть алгоритма SMAWK для поиска минимумов строк монотонной матрицы использует стеки аналогично сканированию Грэма. [20]
- Все ближайшие меньшие значения — проблема поиска для каждого числа в массиве ближайшего предшествующего числа, меньшего его. Один из алгоритмов решения этой проблемы использует стек для хранения набора кандидатов на ближайшее меньшее значение. Для каждой позиции в массиве стек извлекается до тех пор, пока на его вершине не будет найдено меньшее значение, а затем значение в новой позиции помещается в стек. [21]
- Алгоритм цепочки ближайших соседей — метод агломеративной иерархической кластеризации , основанный на поддержании стека кластеров, каждый из которых является ближайшим соседом своего предшественника в стеке. Когда этот метод находит пару кластеров, которые являются общими ближайшими соседями, они извлекаются и объединяются. [22]
Безопасность
[ редактировать ]В некоторых вычислительных средах стеки используются таким образом, что могут сделать их уязвимыми для нарушений безопасности и атак. Программисты, работающие в таких средах, должны проявлять особую осторожность, чтобы избежать подобных ошибок в этих реализациях.
Например, некоторые языки программирования используют общий стек для хранения как данных, локальных для вызываемой процедуры, так и связывающей информации, которая позволяет процедуре вернуться к вызывающей стороне. Это означает, что программа перемещает данные в тот же стек, который содержит критические адреса возврата для вызовов процедур, и из него. Если данные перемещаются в неправильное место в стеке или элемент данных слишком большого размера перемещается в место стека, которое недостаточно велико для его размещения, возвращаемая информация для вызовов процедур может быть повреждена, что приведет к сбою программы.
Злоумышленники могут попытаться провести атаку с разрушением стека , которая использует этот тип реализации, предоставляя вводимые данные слишком большого размера программе, которая не проверяет длину ввода. Такая программа может полностью скопировать данные в определенное место в стеке и при этом изменить адреса возврата для процедур, которые ее вызвали. Злоумышленник может экспериментировать, чтобы найти определенный тип данных, которые могут быть предоставлены такой программе, чтобы адрес возврата текущей процедуры был сброшен и указывал на область внутри самого стека (и внутри данных, предоставленных злоумышленником). который, в свою очередь, содержит инструкции, выполняющие несанкционированные операции.
Этот тип атаки является разновидностью атаки на переполнение буфера и является чрезвычайно частым источником нарушений безопасности в программном обеспечении, главным образом потому, что некоторые из наиболее популярных компиляторов используют общий стек как для вызовов данных, так и для вызовов процедур, и не проверяют длину элементы данных. Часто программисты также не пишут код для проверки размера элементов данных, и когда в стек копируется элемент данных слишком большого или меньшего размера, может произойти нарушение безопасности.
См. также
[ редактировать ]- Список структур данных
- Очередь
- Двусторонняя очередь
- ФИФО (вычисления и электроника)
- Стек оперативной памяти (он же автоматический стек памяти)
Примечания
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 232–233. ISBN 0-262-03384-4 .
- ^ Тьюринг, Алан Мэтисон (19 марта 1946 г.) [1945]. Предложения по разработке в математическом отделе автоматической вычислительной машины (АВС) . (Примечание. Представлено 19 марта 1946 г. Исполнительному комитету Национальной физической лаборатории (Великобритания).)
- ^ Карпентер, Брайан Эдвард ; Доран, Роберт Уильям (1 января 1977 г.) [октябрь 1975 г.]. «Другая машина Тьюринга» . Компьютерный журнал . 20 (3): 269–279. дои : 10.1093/comjnl/20.3.269 . (11 страниц)
- ^ Блаау, Геррит Энн ; Брукс-младший, Фредерик Филлипс (1997). Компьютерная архитектура: концепции и эволюция . Бостон, Массачусетс, США: Addison-Wesley Longman Publishing Co., Inc.
- ^ ЛаФорест, Чарльз Эрик (апрель 2007 г.). «2.1 Лукасевич и первое поколение: 2.1.2 Германия: Конрад Цузе (1910–1995); 2.2 Первое поколение стековых компьютеров: 2.2.1 Zuse Z4». Стековая компьютерная архитектура второго поколения (PDF) (диссертация). Ватерлоо, Канада: Университет Ватерлоо . стр. 8, 11. Архивировано (PDF) из оригинала 20 января 2022 г. Проверено 2 июля 2022 г. (178 страниц)
- ^ Самельсон, Клаус (1957) [1955]. Написано на Международном коллоквиуме по проблемам вычислительной техники, Дрезден, Германия. Проблемы технологии программирования (на немецком языке). Берлин, Германия: Немецкое научное издательство VEB . стр. 61–68. (Примечание. Эта статья была впервые представлена в 1955 году. В ней описывается стек чисел ( числовой подвал ), но называется линейная вспомогательная память ( линейная вспомогательная память ).)
- ^ Jump up to: а б с д Фоте, Майкл; Уилке, Томас, ред. (2015) [14 ноября 2014 г.]. Написано в Йене, Германия. Подвал, стек и автоматическая память — структура с потенциалом [ Подвал, стек и автоматическая память — структура с потенциалом ] (PDF) (Материалы коллоквиума 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 страниц)
- ^ Бауэр, Фридрих Людвиг ; Самельсон, Клаус (30 марта 1957 г.). «Процедура автоматической обработки закодированных данных и вычислительная машина для осуществления этого процесса» (на немецком языке). Мюнхен, Германия: Патентное ведомство Германии. ДЕ-ПС 1094019 . Проверено 1 октября 2010 г.
- ^ Бауэр, Фридрих Людвиг ; Гус, Герхард [на немецком языке] (1982). Информатика – вводный обзор (на немецком языке). Том 1 (3-е изд.). Берлин: Springer Verlag . п. 222. ИСБН 3-540-11722-9 .
Термин «Келлер» для этого был введен Бауэром и Самельсоном в заявке на патент Германии от 30 марта 1957 года.
- ^ Самельсон, Клаус ; Бауэр, Фридрих Людвиг (1959). «Последовательный перевод формул». Электронно-вычислительные системы (на немецком языке). 1 (4): 176–182.
- ^ Самельсон, Клаус ; Бауэр, Фридрих Людвиг (1960). «Последовательный перевод формул» . Коммуникации АКМ . 3 (2): 76–83. дои : 10.1145/366959.366968 . S2CID 16646147 .
- ^ «IEEE-Computer-Pioneer-Preis – Бауэр, Фридрих Л.» Технический университет Мюнхена , факультет компьютерных наук. 1 января 1989 г. Архивировано из оригинала 07.11.2017.
- ^ Хэмблин, Чарльз Леонард (май 1957 г.). Схема безадресного кодирования, основанная на математической записи (PDF) (машинописный текст). Технологический университет Нового Южного Уэльса . стр. 121-1–121-12. Архивировано (PDF) из оригинала 12 апреля 2020 г. Проверено 12 апреля 2020 г. (12 страниц)
- ^ Кеммерер, Вильгельм [на немецком языке] (11 декабря 1958 г.). Числовой калькулятор с программированием по математическим формулам (Диссертация) (на немецком языке). Йена, Германия: Факультет математики и естественных наук Университета Фридриха Шиллера . urn:nbn:de:gbv:27-20130731-133019-7 . ППН:756275237. Архивировано из оригинала 14 октября 2023 г. Проверено 14 октября 2023 г. [2] (2+69 страниц)
- ^ Кеммерер, Вильгельм [на немецком языке] (1960). Числовые калькуляторы . Электронные вычисления и правила (на немецком языке). Том 1. Берлин, Германия: Akademie-Verlag .
- ^ Болл, Джон А. (1978). Алгоритмы калькуляторов РПН (1-е изд.). Кембридж, Массачусетс, США: Wiley-Interscience , John Wiley & Sons, Inc. ISBN 978-0-471-03070-6 . LCCN 77-14977 .
- ^ Годзе, Атул П.; Годзе, Дипали А. (1 января 2010 г.). Компьютерная архитектура . Технические публикации. стр. 1–56. ISBN 978-8-18431534-9 . Проверено 30 января 2015 г.
- ^ Горовиц, Эллис (1984). Основы структур данных в Паскале . Пресса по информатике . п. 67.
- ^ Грэм, Рональд «Рон» Льюис (1972). Эффективный алгоритм определения выпуклой оболочки конечного плоского множества (PDF) . Письма об обработке информации. 1. Том. 1. С. 132–133. Архивировано (PDF) из оригинала 22 октября 2022 г.
- ^ Аггарвал, Алок; Клове, Мария М .; Моран, Шломо ; Шор, Питер ; Уилбер, Роберт (1987). «Геометрические приложения алгоритма матричного поиска». Алгоритмика . 2 (1–4): 195–208. дои : 10.1007/BF01840359 . МР 0895444 . S2CID 7932878 . .
- ^ Беркман, Омер; Шибер, Барух ; Вишкин, Узи (1993). «Оптимальные дважды логарифмические параллельные алгоритмы, основанные на поиске всех ближайших меньших значений». Журнал алгоритмов . 14 (3): 344–370. CiteSeerX 10.1.1.55.5669 . дои : 10.1006/jagm.1993.1018 . .
- ^ Мурта, Фионн (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 г.]. Написано в Киле, Германия. Работы Фридриха Л. Бауэра и Клауса Самельсона 1950-х годов по введению терминов «принцип подвала» и «подвал-автомат» ) ( PDF ( на немецком языке). Йена, Германия: Институт компьютерных наук, Кильский университет Кристиана Альбрехта. стр. 19–29. Архивировано (PDF) из оригинала 14 ноября 2022 г. Проверено 14 ноября 2022 г. (11 страниц) (Примечание. Опубликовано в Fothe & Wilke .)
- Гус, Герхард [на немецком языке] (7 августа 2017 г.). История немецкоязычной информатики - языки программирования и проектирование компиляторов [ История информатики в немецкоязычных странах - Языки программирования и проектирование компиляторов ] (PDF) (на немецком языке). Карлсруэ, Германия: Факультет компьютерных наук Технологического института Карлсруэ (KIT). Архивировано (PDF) из оригинала 19 мая 2022 г. Проверено 14 ноября 2022 г. (11 страниц)