Основы теории. Стек является одной из наиболее используемых и наиболее важных структур данныхСтек является одной из наиболее используемых и наиболее важных структур данных. Стеком называется структура данных, в которой элемент, занесенный первым, извлекается последним. Стеки применяются очень часто. Например, распознавание синтаксиса в компиляторе, как и оценка выражений, основано на стеке. На нижнем уровне стеки используются для передачи параметров функциям, выполнения вызова функции и возвращения из нее. Стек (stack) — это список элементов, доступных только в одном конце списка. Элементы добавляются или удаляются из списка только в вершине (top) стека. Подносы в столовой или стопка коробок являются моделями стека. Стек предназначен для хранения элементов, доступных естественным путем в вершине списка. Представим шампур, на который нанизаны нарезанные овощи, подготовленные для шашлыка. Перед приготовлением шашлыка гость сообщает, что он не ест грибов, и их необходимо убрать. Эта просьба означает удалить лук, удалить грибочек и затем вновь нанизать лук.
Рисунок 1 – Модель стека Если гость не любит зеленый перец или лук, это доставит повару больше проблем.Абстрактное понятие стека допускает неопределенно большой список. Логически подносы в столовой могут складываться бесконечно. В действительности подносы находятся на полке, а овощи нанизаны на коротких шампурах. Когда полка или шампур переполнены, мы не можем добавить (Push) еще один элемент в стек. Стек достигает максимального количества элементов, которыми он может управлять. Эта ситуация поясняет значение условия полного стека (stackfull). Другая крайность — вы не можете взять поднос с пустой полки. Условие пустого стека (stackempty) подразумевает, что вы не можете удалить (Pop) элемент. Описание абстрактного типа данных Stack включает только условие пустого стека. Условие полного стека является уместным в том случае, если реализация содержит верхнюю границу размера списка.В алгоритме быстрой сортировки стек используется для хранения границ неупорядоченных фрагментов. В принципе, порядок, в котором они будут обрабатываться, не критичен (главное, чтобы в конце концов все фрагменты оказались отсортированными), но удобнее всего стек использовать из-за простоты его реализации. В структуре стека важнейшее место занимают операции, добавляющие и удаляющие элементы. Операция Pushдобавляет элемент в вершину стека. Об операции удаления элемента из стека говорят как об извлечении (операция Рор) из стека. На рис. 3 показана последовательность операций Push и Pop. Последний вставленный в стек элемент является первым удаляемым элементом. По этой причине о стеке говорят, что он имеет порядок LIFO (last-in/first-out) (последний пришел/первый ушел).
Рисунок 2 – Помещение в стек и извлечение из него Для стека определены всего две операции: занесение элемента и выборка элемента. При выборке элемент удаляется из стека, и это как раз то, что и требуется.Для работы со стеком достаточно одной переменной — указателя на его вершину. Назовем ее top. Каждый элемент стека должен содержать два целых числа, представляющих собой левую и правую границы фрагмента массива, и указатель на следующий элемент: struct Node // Элементстека { int left, right; Node* p; }; Node* top = 0; // Вершинастека В C++ определена стандартная константа NULL, значение которой равно нулю типа «указатель», но поскольку правила преобразования типов обеспечивают правильное преобразование целого нуля в нуль типа «указатель», в этой константе нет необходимости.Удобно оформить занесение и выборку элемента в виде отдельных функций.Функция помещения в стек обычно называется push, а выборки — pop. Все необходимое передается функциям через параметры. // Начальное формирование стека Node *first(intd) { Node *pv = newNode; pv-> d = d; pv-> p = 0; returnpv; }
Однако можно и не использовать отдельную функцию для занесения первого элемента в стек, так как если указателю top присвоить 0 перед первым обращением к функции push(), то функция push вполне прилично справится с созданием первого элемента стека: // Занесениевстек Node* push(Node* top, const int l, const int r) { Node* pv = new Node; // 1 pv-> left = 1; // 2 pv-> right = г; // 3 pv-> p = top: // 4 return pv; // 5 } // Выборкаизстека Node* pop(Node* top, int& l, int& r) { Node* pv = top-> p; // 6 l = top-> left; // 7 r = top-> right; // 8 delete top; // 9 returnpv; // 10 } Операция извлечение из стека. В результате выполнения данной операции некоторой переменной i должно быть присвоено значение первого элемента стека и значение указателя на начало списка должно быть перенесено на следующий элемент стека. // Извлечение из стека boolPop(Stek **u, Data& x) { if(*u == NULL) { cout < < " Pustoj stek" < < endl; return false; } Stek *t = *u; x.a = t-> d.a; // Получаем значения полей на вершине стека *u = t-> next; // Перенастройка вершины deletet; // Удаление ненужного элемента returntrue; }
Рассмотрим эти функции, самым тщательным образом вникая в детали. Чтобы занести в стек границы фрагмента, надо передать в функцию push() эти границы, а также указатель на вершину стека, в который мы собираемся их заносить. Перед границами указано ключевое слово const, чтобы подчеркнуть тот факт, что они не должны изменяться внутри функции. Прежде всего мы описываем вспомогательную переменную-указатель и заносим в нее адрес нового элемента стека, который создается с помощью операции new (oпeратор 1). Выделяется столько памяти, сколько необходимо для хранения структуры типа Node. В операторах 2 и 3 информационные поля этой структуры left и right заполняются значениями переданных в функцию границ фрагмента массива. Доступ к этим полям выполняется через указатель pv и операцию выбора ->. Новый элемент становится вершиной стека. Поле его указателя должно ссылаться на элемент, помещенный в стек ранее. Эта ссылка создается в операторе 4. Если «заталкиваемый» в стек элемент является первым, то в качестве первого аргумента функции push() надо задать 0. Функция push возвращает указатель на вершину стека. Им всегда является указатель на только что занесенный элемент (оператор 5). Выборка из стека (функция pop) выполняется аналогично. Сначала из вершины стека выбирается указатель на его следующий элемент (оператор 6), который станет новой вершиной стека. Этот указатель является возвращаемым значением функции (оператор 10). Информационная часть элемента заносится в переменные 1 и r, которые передаются в вызывающую функцию по ссылке (операторы 7 и 8). После того как вся информация из элемента выбрана, его можно удалить (оператор 9). Эти функции можно применить в любой программе, где требуется стек, просто изменив поля, составляющие его информационную часть, и соответствующие параметры.
|
