Сообщения

Показаны сообщения с ярлыком "стек"

Структуры данных: применение стеков

Изображение
Оценка выражения и синтаксический анализ Калькуляторы, использующие обратную польскую запись, используют структуру стека для хранения значений. Выражения могут быть представлены в префиксной, постфиксной или инфиксной нотации, а преобразование из одной формы в другую может быть выполнено с использованием стека. Многие компиляторы используют стек для анализа синтаксиса выражений, программных блоков и т. д. перед переводом в низкоуровневый код. Большинство языков программирования являются контекстно-свободными языками, что позволяет их анализировать с помощью стековых машин. Поиск с возвратом (Backtracking) Другое важное применение стеков - поиск с возвратом (backtracking). Рассмотрим простой пример поиска правильного пути в лабиринте. Есть ряд точек, от начальной точки до пункта назначения. Начнем с одной точки. Чтобы добраться до конечного пункта, есть несколько путей. Предположим, мы выбрали случайный путь. Следуя определенному пути, мы понимаем, что выбранный нами путь неверен. По...

Структуры данных: стек на аппаратном уровне

Изображение
Обычное использование стеков на уровне архитектуры - это средство выделения и доступа к памяти. Базовая архитектура стека Типичный стек - это область памяти компьютера с фиксированным началом и переменным размером. Первоначально размер стека равен нулю. Указатель стека, обычно в форме аппаратного регистра, указывает на самое последнее упомянутое местоположение в стеке; когда размер стека равен нулю, указатель стека указывает на начало стека. Две операции, применимые ко всем стекам: операция push , в которой элемент данных размещается в месте, указанном указателем стека, а адрес в указателе стека регулируется размером элемента данных; операция pop или pull: элемент данных в текущем местоположении, на который указывает указатель стека, удаляется, а указатель стека регулируется размером элемента данных. Существует много вариантов базового принципа стековых операций. Каждый стек имеет фиксированное место в памяти, с которого он начинается. Когда элементы данных добавляются в стек,...

Структуры данных: стек

Изображение
В информатике стек (stack) - это абстрактный тип данных, который служит набором элементов с двумя основными операциями: push , которая добавляет элемент в коллекцию; pop , которая удаляет последний добавленный элемент, который еще не был удален; Порядок, в котором элементы выходят из стека, порождает его альтернативное имя, LIFO (last in, first out) (последний пришел, первый вышел). Кроме того, операция peek может дать доступ к вершине без изменения стека. Название "стек" для этого типа структуры происходит от аналогии с набором физических элементов, уложенных друг на друга, что позволяет легко убрать элемент с верха стека, в то время как переход к элементу, находящемуся глубже в стеке может потребовать сначала снять несколько других предметов. Рассматриваемые как линейная структура данных или, более абстрактно, последовательная коллекция, операции push и pop выполняются только на одном конце структуры, называемой вершиной стека. Это позволяет реализовать стек в виде...