Стек (абстрактный тип данных) - Stack (abstract data type)

Об использовании термина LIFO в бухгалтерском учете см. LIFO (бухгалтерский учет). Об использовании термина "отжимания вниз" в силовых тренировках см. Отжимание (упражнение).
Для использования в других целях см. Стек (значения).
Как и в случае стопки тарелок, добавление или удаление возможно только сверху.
Простое представление среды выполнения стека с толкать и поп операции.

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

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

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

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

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

История

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

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

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

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

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

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

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

Выполнение

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

Множество

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

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

В толкать операция добавляет элемент и увеличивает верх index после проверки переполнения:

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

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

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

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

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

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

структура frame: data: item next: frame или nil
структура stack: head: frame или nil size: integer
процедура инициализировать (stk: stack): stk.head ← nil 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): если stk.head = nil: сообщить об ошибке недостаточного заполнения r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 возвращаться р

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

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

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

> (setf куча (список 'а 'б 'c))  ;; установить переменную "стек"(А B C)> (поп куча)  ;; получить верхний (крайний левый) элемент, должен изменить стекА> куча        ;; проверить значение стека(B C)> (толкать 'новый куча)  ;; вставьте новую вершину в стек(НОВЫЙ B C)

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

импорт java.util.Stack;учебный класс StackDemo {    общественный статический пустота главный(Нить[]аргументы) {        Куча<Нить> куча = новый Куча<Нить>();        куча.толкать("А");    // Вставляем "A" в стек        куча.толкать("B");    // Вставляем "B" в стек        куча.толкать("C");    // Вставляем "C" в стек        куча.толкать("D");    // Вставляем "D" в стек        Система.из.println(куча.заглядывать());    // Печатает верх стека ("D")        куча.поп();    // удаляем верх ("D")        куча.поп();    // удаляем следующую вершину ("C")    }}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Штабелеукладчик

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

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

Существует также ряд небольших микропроцессоров, которые реализуют стек непосредственно в оборудовании, а некоторые микроконтроллеры имеют стек фиксированной глубины, к которому нет прямого доступа. Примерами являются Микроконтроллеры PIC, то Компьютерные Ковбои MuP21, то Харрис RTX линия, и Novix NC4016. Многие микропроцессоры на основе стека использовались для реализации языка программирования. Четвертый на микрокод уровень. Стеки также использовались в качестве основы для ряда мэйнфреймы и мини-компьютеры. Такие машины назывались штабельные машины, самый известный из которых Берроуз B5000.

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

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

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

Возврат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. ^ Напротив, простая QUEUE работает с FIFO (первым пришел-первым вышел ).
  2. ^ а б Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN  0-262-03384-4.
  3. ^ Тьюринг, Алан Мэтисон (1946-03-19) [1945], Предложения по развитию в отделе математики автоматизированного вычислительного механизма (АСВ) (NB. Представлено 1946-03-19 перед Исполнительным комитетом Национальной физической лаборатории (Великобритания).)
  4. ^ Карпентер, Брайан Эдвард; Доран, Роберт Уильям (1977-01-01) [октябрь 1975]. «Другая машина Тьюринга». Компьютерный журнал. 20 (3): 269–279. Дои: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 году. В ней описывается стек чисел (Захленкеллер), но называет ее линейной вспомогательной памятью (линейный исполнитель Hilfsspeicher).)
  6. ^ а б Фоте, Майкл; Wilke, Thomas, eds. (2015). Keller, 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) из оригинала 12.04.2020. Получено 2020-04-12. (77 страниц)
  7. ^ Бауэр, Фридрих Людвиг; Самельсон, Клаус (1957-03-30). "Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens" (на немецком). Мюнхен, Германия: Deutsches Patentamt. DE-PS 1094019. Получено 2010-10-01.
  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. Дои:10.1145/366959.366968. S2CID  16646147.
  11. ^ "IEEE-Computer-Pioneer-Preis - Бауэр, Фридрих Л." Технический университет Мюнхена, Факультет компьютерных наук. 1989-01-01. Архивировано из оригинал на 2017-11-07.
  12. ^ Хэмблин, Чарльз Леонард (Май 1957 г.). Схема безадресного кодирования на основе математической записи (PDF) (машинопись). N.S.W. Технологический университет. С. 121-1–121-12. В архиве (PDF) из оригинала 12.04.2020. Получено 2020-04-12. (12 страниц)
  13. ^ Каммерер, Вильгельм (1958). Ziffern-Rechenautomat mit Programmierung nach Mathematischem Formelbild (Дипломная работа) (на немецком языке). Фридрих-Шиллер-Universität, Йена, Германия.
  14. ^ Каммерер, Вильгельм (1960). Ziffernrechenautomaten. Elektronisches Rechnen und Regeln (на немецком). 1. Берлин, Германия: Академия-Верлаг.
  15. ^ Болл, Джон А. (1978). Алгоритмы для калькуляторов RPN (1-е изд.). Кембридж, Массачусетс, США: Wiley-Interscience, John Wiley & Sons, Inc. ISBN  978-0-471-03070-6.
  16. ^ Годсе, Атул П .; Годсе, Дипали А. (01.01.2010). Компьютерная архитектура. Технические публикации. С. 1–56. ISBN  978-8-18431534-9. Получено 2015-01-30.
  17. ^ Горовиц, Эллис: «Основы структур данных в Паскале», стр. 67. Computer Science Press, 1984
  18. ^ Грэм, Р.Л. (1972). Эффективный алгоритм определения выпуклой оболочки конечного плоского множества. Письма об обработке информации 1, 132-133
  19. ^ Аггарвал, Алок; Клаве, Мария М.; Моран, Шломо; Шор, Петр; Уилбер, Роберт (1987), "Геометрические приложения алгоритма поиска матрицы", Алгоритмика, 2 (1–4): 195–208, Дои:10.1007 / BF01840359, МИСТЕР  0895444, S2CID  7932878.
  20. ^ Беркман, Омер; Шибер, Барух; Вишкин, Узи (1993), «Оптимальные дважды логарифмические параллельные алгоритмы, основанные на нахождении всех ближайших меньших значений», Журнал алгоритмов, 14 (3): 344–370, CiteSeerX  10.1.1.55.5669, Дои:10.1006 / jagm.1993.1018.
  21. ^ Муртаг, Фионн (1983), «Обзор последних достижений в алгоритмах иерархической кластеризации» (PDF), Компьютерный журнал, 26 (4): 354–359, Дои:10.1093 / comjnl / 26.4.354.

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

внешняя ссылка