Реализация стековых структур

Стек (stack) – это последовательность однотипных элементов, характерная тем, что элементы добавляются и удаляются только с одного конца, называемого вершиной стека. Стек работает по принципу: «Элемент, помещенный в стек последним, извлечен будет первым». Иногда этот принцип обозначается сокращением LIFO (от английского «Last In – First Out», т.е. «последним зашел – первым вышел»). Естественно, можно перевернуть этот принцип и сформулировать его так: «Элемент, помещенный в стек первым, извлечен будет последним». Иногда такой элемент называют дном стека.

Бытовой пример стека – стопка тяжелых предметов (например – бетонные плиты). Примеры использования стека в программировании:

• вложенные вызовы подпрограмм, в частности – рекурсивные:
• вызовы подпрограмм идут в одном порядке, а возвраты из них – в обратном; стек операндов при разборе арифметических выражений со вложенными скобками.

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

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

Со стеком связываются две основные операции:

• добавление (заталкивание) элемента в стек (PUSH);
• удаление (выталкивание) элемента из стека (POP).

Статическая реализация стека очень проста. Необходимо объявить:

• базовый массив с элементами необходимого типа (в том числе – и указателями!);
• переменную целого типа для индексации вершинного элемента (назовем ее SP, т.е. Stack Pointer, как называется один из регистров процессоров семейства Intel, используемый для выполнения стековых операций).

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

Оба способа совершенно эквивалентны, поэтому для определенности выберем первый способ. Тогда для пустого стека переменная SP = 1 (если индексация элементов массива начинается с 1) или SP = 0 (индексация с нуля – все языки Си-подобного типа). При каждом добавлении нового элемента переменная SP увеличивается на 1, а при удалении – уменьшается на 1.

Пример последовательного состояния трехэлементного стека символов:



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

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

Алгоритм операции добавления:

• проверка возможности добавления (стек-массив заполнен полностью?);
• размещение нового элемента в ячейке, определяемой значением переменной SP;
• увеличение SP на 1.

Алгоритм операции удаления:

• проверка возможности удаления (стек пустой?);
• уменьшение SP на 1;
• извлечение элемента из ячейки, определяемой значением переменной SP.

Кроме этих основных, можно ввести ряд дополнительных операций:

• начальная инициализация пустого стека (установка SP = 1 или 0);
• проверка заполненности стека (сравнение SP с размерностью массива);
• проверка пустоты стека (условие SP = 1 или 0);
• полная очистка стека (установка SP = 1 или 0);
• запрос вершинного элемента БЕЗ извлечения его из стека;
• вывод элементов стека (цикл по числу элементов в стеке).

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

В отличие от статической (непрерывной) реализации на основе массива при динамической реализации последовательные элементы стека могут располагаться в ЛЮБЫХ свободных областях памяти и совершенно не обязательно друг за другом! При этом возникает необходимость как-то связывать соседние элементы друг с другом: каждый элемент должен «знать» адрес размещения в памяти соседнего элемента. Это можно реализовать за счет включения в каждый элемент стека специального связующего поля для хранения адреса соседнего элемента. Такие связующие поля должны реализовываться с помощью указательных переменных.

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

Учитывая специфику стека, адресные указатели должны следовать от последнего добавленного в стек элемента (вершина стека) к самому первому (дно стека): вершинный элемент адресует предпоследний, тот – предпредпоследний и т.д. – до «донного» элемента. Этот «донный» элемент является последним в цепочке элементов, и его адресное поле должно быть нулевым (вот где пригодятся директивы nil/NULL).

Пример динамического стека с тремя элементами:



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



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

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

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

На языке Паскаль это выглядит следующим образом:



То же самое объявление на языке Си:



Тогда, следуя описанным ранее правилам использования указателей, конструкции SP^.info или SP -> info позволят получить доступ к информационной части вершинного элемента, а конструкции SP^.pred или SP -> pred - к его адресному полю, содержащему адрес элемента, который был помещен в стек непосредственно перед вершинным.

Как обычно, основные операции со стеком – добавление нового элемента на вершину и удаление вершинного элемента. Но прежде всего надо выполнить инициализацию пустого стека – установить основной указатель SP в нулевое значение:

SP := nil;
SP = NULL;

После этого в стек можно добавлять элементы.

Алгоритм операции добавления:

1. Динамическое выделение памяти для нового элемента. Для этого необходима вспомогательная указательная переменная, например - с именем pTemp. Основной указатель SP для этого использовать нельзя! Выделение памяти выполняется обычным образом - за счет вызова стандартной функции, например – New(pTemp).
2. Заполнение полей нового элемента с помощью указателя pTemp. При этом в его адресное поле надо занести адрес старого вершинного элемента. Этот адрес берется как значение основного указателя SP
   pTemp^.pred := SP;
3. Изменение основного указателя SP так, чтобы он теперь указывал на новый вершинный элемент
   SP := pTemp;

Замечания по алгоритму добавления:

1. В алгоритме важен порядок следования шагов. Например, перестановка шагов 2 и 3 приведет к неправильному результату, т.к. значение указателя SP будет изменено раньше, чем оно будет использовано при установке адресного поля нового элемента.
2. Алгоритм правильно работает и при добавлении первого элемента в пустой стек.
3. Теоретически на первом шаге возможна ситуация отсутствия свободной динамической памяти и как следствие – невозможность добавления нового элемента. При необходимости можно проверить результат работы стандартного вызова New/malloc с точки зрения успешности выделения новой области памяти.

Алгоритм операции удаления

1. Проверка стека на пустоту: указатель SP равен нулю или нет?
2. Для последующей обработки удаляемого элемента адресуем его с помощью вспомогательного указателя (например – pTemp), устанавливая pTemp в значение основного указателя SP.
3. Изменение основного указателя SP так, чтобы он указывал на новый вершинный элемент. Адрес этого элемента извлекается из адресного поля удаляемого элемента:

   SP := SP^.pred; // а можно и так: SP := pTemp^.pred;
   

4. Обрабатываем удаляемый элемент с помощью указателя pTemp. Варианты обработки: освободить память с помощью стандартного вызова и указателя pTemp («жесткое» удаление) или включить удаляемый элемент во вспомогательную структуру, например – стек удаленных элементов («мягкое» удаление).

Замечания по алгоритму удаления:

1. Порядок шагов важен, менять их местами нельзя.
2. Алгоритм правильно работает и для случая удаления единственного элемента, когда стек становится пустым.

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

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

Необходимые действия:

1. Адресуем вершинный элемент с помощью вспомогательного указателя:
   pTemp := SP;
2. Организуем цикл по условию достижения донного элемента:
   while ( pTemp <> nil ) do < тело цикла >
3. В теле цикла обрабатываем информационное поле текущего элемента и изменяем вспомогательный указатель на адрес предшествующего элемента: «обработка pTemp^.info»
   pTemp := pTemp^.pred;

Немного по-другому выполняется полное уничтожение динамического стека. В результате циклического прохода выделенная каждому элементу память должна быть освобождена! Здесь для прохода уже можно использовать основной указатель SP, а вот вспомогательный указатель pTemp надо использовать для освобождения памяти.

Необходимые действия:

1. Организуем цикл прохода по стеку
   while ( SP <> nil ) do < тело цикла >
2. В теле цикла устанавливаем pTemp в значение указателя SP, меняем SP на адрес следующего элемента и освобождаем память с помощью указателя pTemp:
   pTemp := SP;
   SP := SP^.pred;
   Dispose (pTemp);

В заключение приведем сравнение статической (непрерывной) и динамической (связной) реализации стека.

Статическая реализация:

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

Динамическая реализация:

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

Напоминаю, что вы можете в любое время обратиться ко мне для решения задач по программированию, написанию программ для курсовых, практических или лабораторных работ на C++, C#, Java, JavaScript и PHP.