Структуры данных: применение стеков
Оценка выражения и синтаксический анализ
Калькуляторы, использующие обратную польскую запись, используют структуру стека для хранения значений. Выражения могут быть представлены в префиксной, постфиксной или инфиксной нотации, а преобразование из одной формы в другую может быть выполнено с использованием стека. Многие компиляторы используют стек для анализа синтаксиса выражений, программных блоков и т. д. перед переводом в низкоуровневый код. Большинство языков программирования являются контекстно-свободными языками, что позволяет их анализировать с помощью стековых машин.
Поиск с возвратом (Backtracking)
Другое важное применение стеков - поиск с возвратом (backtracking). Рассмотрим простой пример поиска правильного пути в лабиринте. Есть ряд точек, от начальной точки до пункта назначения. Начнем с одной точки. Чтобы добраться до конечного пункта, есть несколько путей. Предположим, мы выбрали случайный путь. Следуя определенному пути, мы понимаем, что выбранный нами путь неверен. Поэтому нам нужно найти способ, с помощью которого мы можем вернуться к началу этого пути. Это можно сделать с использованием стеков. С помощью стеков мы запоминаем точку, в которой мы достигли. Это делается путем добавления этой точки в стек. В случае, если мы окажемся на неправильном пути, мы можем извлечь последнюю точку из стека и, таким образом, вернуться к последней точке и продолжить наш квест, чтобы найти правильный путь. Это называется поиском с возвратом (backtracking).
Прототипом примера алгоритма поиска с возвратом является поиск в глубину, который находит все вершины графа, которые могут быть достигнуты из указанной начальной вершины. Другие приложения поиска с возвратом включают поиск в пространствах, представляющих потенциальные решения проблемы оптимизации. Ветвление и ограничение - это метод для выполнения таких обратных поисков без исчерпывающего поиска всех потенциальных решений в таком пространстве.
Управление памятью времени компиляции
Ряд языков программирования ориентирован на стек, то есть они определяют большинство основных операций (добавление двух чисел, печать символа) как получение их аргументов из стека и помещение любых возвращаемых значений обратно в стек. Например, PostScript имеет стек возврата и стек операндов, а также стек графических состояний и стек словарей. Многие виртуальные машины также ориентированы на стек, в том числе машина p-кода и виртуальная машина Java.
Почти все соглашения о вызовах - способы, с помощью которых подпрограммы получают свои параметры и возвращают результаты, - используют специальный стек ("стек вызовов") для хранения информации о вызовах и вложениях процедур/функций, чтобы переключиться в контекст вызываемой функции и восстановить функцию вызывающего абонента после завершения вызова. Функции следуют протоколу времени выполнения между вызывающим и вызываемым, чтобы сохранить аргументы и вернуть значение в стек. Стеки являются важным способом поддержки вложенных или рекурсивных вызовов функций. Этот тип стека неявно используется компилятором для поддержки операторов CALL и RETURN (или их эквивалентов) и не обрабатывается непосредственно программистом.
Некоторые языки программирования используют стек для хранения данных, локальных для процедуры. Пространство для локальных элементов данных выделяется из стека при входе в процедуру и освобождается при выходе из процедуры. Язык программирования C обычно реализуется таким образом. Использование одного и того же стека для вызовов данных и процедур имеет важные последствия для безопасности, о которых должен знать программист, чтобы избежать внесения в программу серьезных ошибок безопасности.
Эффективные алгоритмы
Несколько алгоритмов используют стек (отдельный от обычного стека вызовов функций большинства языков программирования) в качестве основной структуры данных, с помощью которой они организуют свою информацию. Они включают:
- Сканирование Грэма, алгоритм выпуклой оболочки двумерной системы точек. Выпуклая оболочка подмножества входных данных поддерживается в стеке, который используется для поиска и удаления вогнутостей на границе, когда в корпус добавляется новая точка.
- Часть алгоритма SMAWK для поиска минимумов строк монотонной матрицы использует стеки аналогично сканированию Грэма.
- Для всех ближайших меньших значений возникает проблема поиска для каждого числа в массиве ближайшего предшествующего числа, которое меньше его. Один алгоритм для этой проблемы использует стек, чтобы поддерживать набор кандидатов для ближайшего меньшего значения. Для каждой позиции в массиве стек уменьшается (pop) до тех пор, пока на его вершине не будет найдено меньшее значение, а затем значение в новой позиции помещается в стек.
- Алгоритм цепочки ближайших соседей, метод агломерационной иерархической кластеризации, основанный на поддержании стека кластеров, каждый из которых является ближайшим соседом своего предшественника в стеке. Когда этот метод находит пару кластеров, которые являются взаимными ближайшими соседями, они выталкиваются и объединяются.
Безопасность и стеки
Некоторые вычислительные среды используют стеки таким образом, что могут сделать их уязвимыми для нарушений безопасности и атак. Программисты, работающие в таких средах, должны проявлять особую осторожность, чтобы избежать ошибок этих реализаций.
Например, некоторые языки программирования используют общий стек для хранения как данных, локальных для вызываемой процедуры, так и информации о связях, которая позволяет процедуре вернуться к своему вызывающему. Это означает, что программа перемещает данные в один и тот же стек, который содержит критические адреса возврата для вызовов процедур. Если данные перемещаются в неправильное место в стеке или слишком большой элемент данных перемещается в место в стеке, которое недостаточно велико для его хранения, информация о возврате для вызовов процедур может быть повреждена, что приведет к сбою программы.
Вредоносные программы могут предпринять атаку с разрушением стека, которая использует преимущества этого типа реализации, предоставляя ввод данных слишком большого размера программе, которая не проверяет длину ввода. Такая программа может полностью скопировать данные в место в стеке, и при этом она может изменить адреса возврата для процедур, которые ее вызвали. Злоумышленник может поэкспериментировать, чтобы найти конкретный тип данных, которые могут быть предоставлены такой программе, так что адрес возврата текущей процедуры сбрасывается, чтобы указывать на область внутри самого стека (и в данных, предоставленных злоумышленником), который в свою очередь содержит инструкции, которые выполняют несанкционированные операции.
Этот тип атаки является разновидностью атаки переполнения буфера и является чрезвычайно частым источником нарушений безопасности в программном обеспечении, главным образом потому, что некоторые из наиболее популярных компиляторов используют общий стек для вызовов данных и процедур и не проверяют длину элементы данных. Зачастую программисты не пишут код для проверки размера элементов данных, и когда избыточный или слишком большой элемент данных копируется в стек, может возникнуть нарушение безопасности.
Читайте также:
Комментарии
Отправить комментарий