Технология программирования. Вопрос №5

empty(<нач_стека>):boolean	- проверка стека на пустоту;
add(<нач_стека>,<новый_элемент>):<нач_стека>	- добавление элемента в стек;
take(<нач_стека>):<тип_элементов_стека>	- считывание значения верхнего элемента;
del(<нач_стека>):<нач_стека>.	- удаление верхнего элемента из стека.

Очередь

Очередью называется динамическая структура, у которой в каждый момент времени доступны два элемента: первый и последний. Из начала очереди элементы можно удалять, а к концу - добавлять. Примером очереди программистcкой вполне может служить очередь обывательская: скажем, в продуктовом магазине. Последовательность обработки элементов очереди хорошо отражают аббревиатуры LILO (Last In Last Out - "последним вошел, последним вышел") и FIFO (First In First Out - "первым вошел, первым вышел"). Реализовать очередь также можно при помощи массива, хотя здесь уже не удастся полностью избежать перемещения его компонент. Пусть k-я компонента массива хранит начало очереди, а (k+s)-я - ее конец. Тогда можно приписать новый элемент очереди в (k+s+1)-ю компоненту массива, а при удалении элемента из начала очереди ее голова сдвинется в (k+1)-ю компоненту. В процессе работы может оказаться, что вся очередь "сдвинулась" к концу массива, и ее снова нужно вернуть к началу. В этом случае и потребуется s перемещений компонент массива (s - это текущая длина очереди). Однако наиболее эффективной снова будет реализация при помощи односвязного линейного списка.

Для очереди должны быть определены следующие операции:

empty(<нач_очереди>):boolean	- проверка очереди на пустоту;
add(<кон_очереди>,<нов_эл-т>):<кон_очереди>	- добавление элемента в конец очереди;
take_beg(<нач_очереди>):<тип_эл-тов_очереди>	- считывание значения первого элемента;
take_end(<кон_очереди>):<тип_эл-тов_очереди>	- считывание значения последнего элемента;
del(<нач_очереди>):<нач_очереди>	- удаление элемента из начала очереди.

Дек

Дональд Кнут1) ввел понятие усложненной очереди, которая называется дек (deque - Double-Ended QUEue - двухконцевая очередь). В каждый момент времени у дека доступны как первый, так и последний элемент, причем добавлять и удалять элементы можно и в начале, и в конце дека. Таким образом, дек - это симметричная двусторонняя очередь. Реализация дека при помощи массива ничем не отличается от реализации обычной очереди, а вот в терминах списков дек удобнее представлять двусвязным (разнонаправленным) линейным списком. Набор операций для дека аналогичен набору операций для очереди, с той лишь разницей, что добавление и удаление элементов можно производить и в конце, и в начале структуры.

Рекурсия

В математике, да и не только в ней одной, часто встречаются объекты, определяемые при помощи самих себя. Они называются рекурсивными. Например, рекурсивно определяется функция факториал:

0! =1

n! = n*(n-1)!, для любого натурального n.

^

Рекурсивные подпрограммы

В программировании рекурсивной называется подпрограмма, исполнение которой приводит к ее же повторному вызову. Если подпрограмма просто вызывает сама себя, то такая рекурсия называется прямой. Если же несколько подпрограмм вызывают друг друга, но эти вызовы "замкнуты в кольцо", то такая рекурсия называется косвенной.

В случае косвенной рекурсии возникает проблема с описанием подпрограмм: по правилу языка Pascal, нельзя использовать никакой объект раньше, чем он был описан. И здесь полезной оказывается возможность отрывать объявление подпрограммы от ее описания.
^

Стековая организация рекурсии

В момент вызова подпрограммы в памяти создается ее контекст: выделяется место под все ее параметры, локальные переменные и константы. Уничтожается этот контекст только после того, как будет достигнут оператор end, закрывающий подпрограмму, либо в ее тексте встретится оператор exit, насильственно прерывающий ее выполнение. Если некоторая подпрограмма в процессе выполнения вызывает другую подпрограмму, то для вызванной процедуры или функции создается новый отдельный контекст (контекст вызвавшей подпрограммы при этом сохраняется) и т.д. Активным в каждый момент времени является последний контекст. После ликвидации текущего активного контекста активным становится последний "отложенный" контекст - тот, из которого только что закрытый и был вызван. Таким образом, на внутреннем уровне организован стек контекстов подпрограмм.
^

Ограничение глубины рекурсии

Теоретически, рекурсия может быть бесконечной. Однако такой вариант вряд ли кого-нибудь устроит: рекурсивный алгоритм, как и любой нерекурсивный его собрат, обязан выдавать результат своей работы за некое обозримое время. Кроме того, память у компьютера не резиновая, в ней может поместиться лишь конечное число контекстов одновременно открытых экземпляров рекурсивной подпрограммы. Следовательно, каждая рекурсивная подпрограмма должна содержать в себе признак окончания - своеобразный "забор", определяющий максимальную глубину вложенности для этой рекурсии. Признак конца рекурсии может быть как явным (например, в случае реализации факториала), так и неявным (в частности, описанная выше процедура razlozh рано или поздно обязательно закончится, поскольку на каждом шаге происходит уменьшение разлагаемого натурального числа).
^

Замена рекурсивных алгоритмов итеративными

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