6.1.2. Основные операции над стеком.
К основным операциям над стеком относятся: создание пустого стека; проверка стека на пустоту; добавление элемента в конец стека; удаление элемента из конца стека; извлечение данных, начиная с последнего элемента стека.
Алгоритм создания стека
Выделение памяти под первый элемент стека и внесение в него информации.
Установка вершины стека Тор на созданный элемент.
Алгоритм добавления элемента в стек
Выделение памяти под новый элемент.
Внесение значения в информационное поле нового элемента и установка связи между ним и старой вершиной стека Тор.
Помещение вершины стека Тор на новый элемент.
Алгоритм удаления элемента из стека
Извлечение информации из информационного поля вершины стека Тор в переменную и установка на вершину стека вспомогательного указателя Р.
Перемещение указателя вершины стека Тор на следующий элемент и освобождение памяти, занимаемой старой вершиной стека.
6.2. Организация данных – очередь.
6.2.1. Простая очередь – это такая организация данных, при которой включение элементов в последовательность производится с одного конца этой последовательности, а исключение – с другого, т. е. принципом обслуживания простой очереди является принцип FIFO – first in first out (первым пришел – первым вышел) –первый включенный в очередь элемент первым из нее и удаляется.
Представление простой очереди в виде списка
Простую очередь можно реализовать на линейном списке, в котором элементы включаются с одного конца, называемого хвостом, а выбираются и удаляются с другого конца, называемого вершиной.
Для создания простой очереди и работы с ней необходимо иметь два указателя: на начало и на конец очереди, поэтому ее можно организовать на основе двусвязного линейного списка.
При добавлении элемента в очередь указатель вершины остается неизменным, в ссылочное поле последнего элемента заносится адрес нового элемента, и указатель конца перемещается на новый элемент.
При удалении элемента из очереди первый элемент из памяти удаляется, а указатель вершины перемещается к следующему элементу.
6.2.2. Дек (двусторонняя очередь) представляет собой способ организации данных, в которой можно добавлять и удалять элементы с двух сторон.
Дек можно организовать в виде двусвязного ациклического списка, при этом первый и последний элементы списка соответствуют входам (выходам) дека.
7. Обратная польская запись (постфиксная запись) и ее использование
7.1. Обратная польская запись.
В настоящее время классическим считается метод трансляции выражений, основанный на использовании промежуточной обратной польской записи, названной так в честь польского математика Яна Лукашевича, который впервые использовал эту форму представления выражений в математической логике.
Например, имеется простое арифметическое выражение с вещественными переменными
a + b * с – d /(а+b)
Графически его можно представить в виде дерева:
Узлы дерева соответствуют операциям, а ветви – операндам. Левая ветвь, исходящая из узла, отвечает левому операнду, а правая – правому. В каждой ветви операциям, которые выполняются раньше, соответствуют нижележащие узлы. Верхний узел (корень дерева) отвечает операции, которая выполняется последней, – с него начинается построение дерева.
Если, начав с нижнего листа самой левой ветви дерева, обойти все листья и узлы дерева так, чтобы ветви рассматривались слева направо, а узел – только после обхода всех исходящих из него ветвей (стрелки на рис.), то последовательность просмотра листьев и узлов дает обратную польскую запись исходного выражения:
abc*+dab+/-
Эту бесскобочную запись называют также постфиксной записью, потому что знак каждой операции записан после соответствующих операндов.
В обратной польской записи операнды располагаются в том же порядке, что в исходном выражении, а знаки операций при просмотре записи слева направо встречаются в том порядке, в котором нужно выполнять соответствующие действия. Отсюда вытекает основное преимущество обратной польской записи перед обычной записью выражений со скобками: выражение можно вычислить в процессе однократного просмотра слева направо.