stringtranslate.com

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

Подобно стопке тарелок, добавлять или убирать что-либо можно только сверху.
Простое представление среды выполнения стека с операциями push и pop .

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

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

Порядок, в котором элемент добавляется в стек или удаляется из него, описывается как «последним пришел, первым ушел » и обозначается аббревиатурой 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] и Вильгельмом Кеммерером  [de] с его automatisches Gedächtnis («автоматической памятью») в 1958 году. [14] [15] [7]

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

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

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

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

Выполнение

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

Множество

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

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

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

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

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

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

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

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

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

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

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

процедура push(stk : stack, x : item): newhead ← новый кадр newhead.data ← x newhead.next ← stk.head stk.head ← новыйhead размер_шт. ← размер_шт. + 1
процедура pop(stk : stack): если stk.head = nil: сообщить об ошибке переполнения r ← stk.head.data stk.head ← stk.head.next размер_шт. ← размер_шт. - 1 возврат г

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

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

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

> ( setf stack ( list 'a 'b 'c )) ;; установить переменную "stack" ( 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программируемый карманный калькулятор HP-42S 1988 года выпуска, как и почти все калькуляторы компании того времени , имел 4-уровневый стек и мог отображать два из четырех значений регистров стека X, Y, Z и T одновременно благодаря своему двухстрочному дисплею, в данном случае X и Y. В более поздних моделях, таких как HP-48 , количество уровней было увеличено и ограничивалось только объемом памяти.

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

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

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

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

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

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

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

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

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

Откат назад

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

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

Ссылки

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

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

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

На Викискладе есть медиафайлы по теме «Стековые структуры данных» .
В Wikibooks есть книга по теме: Структуры данных/Стеки и очереди