Стеки

title in here
Click to add title in here

Click to add title in here

Стеки

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

Стек (stack) — это список элементов, доступных только в одном конце списка. Элементы добавляются или удаляются из списка только в вершине (top) стека. Подносы в столовой или стопка коробок являются моделями стека.

Коробки

Модель стека

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

шашлыка. Перед приготовлением шашлыка гость сообщает, что он не ест грибов, и их необходимо убрать. Эта просьба означает удалить лук, удалить грибочек и затем вновь нанизать лук. Если гость не любит зеленый перец или лук, это доставит повару больше проблем.
Абстрактное понятие стека допускает неопределенно большой список. Логически подносы в столовой могут складываться бесконечно. В действительности подносы находятся на полке, а овощи нанизаны на коротких шампурах. Когда полка или шампур переполнены, мы не можем добавить (Push) еще один элемент в стек. Стек достигает максимального количества элементов, которыми он может управлять. Эта ситуация поясняет значение условия полного стека (stack full). Другая крайность — вы не можете взять поднос с пустой полки. Условие пустого стека (stack empty) подразумевает, что вы не можете удалить (Pop) элемент. Описание абстрактного типа данных Stack включает только условие пустого стека. Условие полного стека является уместным в том случае, если реализация содержит верхнюю границу размера списка.
В алгоритме быстрой сортировки стек используется для хранения границ неупорядоченных фрагментов. В принципе, порядок, в котором они будут обрабатываться, не критичен (главное, чтобы в конце концов все фрагменты оказались отсортированными), но удобнее всего стек использовать из-за простоты его реализации.

Реализация функций стека
 
В структуре стека важнейшее место занимают

операции, добавляющие и удаляющие элементы. Операция Push добавляет элемент в вершину стека. Об операции удаления элемента из стека говорят как об извлечении (операция Рор) из стека. Ниже показана последовательность операций Push и Pop. Последний вставленный в стек элемент является первым удаляемым элементом. По этой причине о стеке говорят, что он имеет порядок LIFO (last-in/first-out) (последний пришел/первый ушел).

A

A

A

A

A

B

B

B

C

Push A

Push B

Push C

Pop

Pop

D

Push D

Помещение в стек и извлечение из него.

элемента. При выборке элемент удаляется из стека, и это как

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

struct Node {
int left, right;
Node* p;
};
Node* top = 0;

// Элемент стека

// Вершина стека

В C++ определена стандартная константа NULL, значение которой равно нулю типа «указатель», но поскольку правила преобразования типов обеспечивают правильное преобразование целого нуля в нуль типа «указатель», в этой константе нет необходимости.

Функция помещения в стек обычно называется push, а выборки —

pop. Все необходимое передается функциям через параметры.

// Начальное формирование стека

Node *first(int d)
{
Node *pv = new Node;
pv->d = d;
pv->p = 0;
return pv;
}

элемента в стек, так как если указателю 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
return pv; // 10
}

присвоено значение первого элемента стека и значение указателя на начало

списка должно быть перенесено на следующий элемент стека.

// Извлечение из стека
Procedure readStack(Var u : EXST; Var i : integer); Var   x : EXST; Begin   i := u^.Data; {считываем значение поля данных в переменную}   x := u; {запоминаем адрес вершины стека}   u := u^.Next; {переносим вершину стека на следующий элемент}   dispose(x); {освобождаем память, занятую уже ненужным элементом стека} End.

занести в стек границы фрагмента, надо передать в функцию push()

эти границы, а также указатель на вершину стека, в который мы собираемся их заносить. Перед границами указано ключевое слово const, чтобы подчеркнуть тот факт, что они не должны изменяться внутри функции.
Прежде всего мы описываем вспомогательную переменную-указатель и заносим в нее адрес нового элемента стека, который создается с помощью операции new (oпeратор 1). Выделяется столько памяти, сколько необходимо для хранения структуры типа Node. В операторах 2 и 3 информационные поля этой структуры left и right заполняются значениями переданных в функцию границ фрагмента массива. Доступ к этим полям выполняется через указатель pv и операцию выбора ->. Новый элемент становится вершиной стека. Поле его указателя должно ссылаться на элемент, помещенный в стек ранее. Эта ссылка создается в операторе 4. Если «заталкиваемый» в стек элемент является первым, то в качестве первого аргумента функции push() надо задать 0. Функция push возвращает указатель на вершину стека. Им всегда является указатель на только что занесенный элемент (оператор 5).

стека выбирается указатель на его следующий
элемент (оператор 6), который

станет новой вершиной стека.
Этот указатель является возвращаемым значением функции
(оператор 10). Информационная часть элемента заносится в
переменные 1 и r, которые передаются в вызывающую функцию по
ссылке (операторы 7 и 8). После того как вся информация из элемента
выбрана, его можно удалить (оператор 9). Эти функции можно
применить в любой программе, где требуется стек, просто изменив
поля, составляющие его информационную часть, и соответствующие
параметры.