Содержание
- 2. Click to add title in here Click to add title in here Click to add title
- 3. Стеки Стек предназначен для хранения элементов, доступных естественным путем в вершине списка. Представим шампур, на который
- 4. Стеки Реализация функций стека В структуре стека важнейшее место занимают операции, добавляющие и удаляющие элементы. Операция
- 5. Стеки Для стека определены всего две операции: занесение элемента и выборка элемента. При выборке элемент удаляется
- 6. Стеки Удобно оформить занесение и выборку элемента в виде отдельных функций. Функция помещения в стек обычно
- 7. Стеки Однако можно и не использовать отдельную функцию для занесения первого элемента в стек, так как
- 8. Стеки В результате выполнения этой операции некоторой переменной i должно быть присвоено значение первого элемента стека
- 9. Стеки Рассмотрим эти функции, самым тщательным образом вникая в детали. Чтобы занести в стек границы фрагмента,
- 10. Стеки Выборка из стека (функция pop) выполняется аналогично. Сначала из вершины стека выбирается указатель на его
- 12. Скачать презентацию
Click to add title in here
Click to add title in
Click to add title in here
Click to add title in
Click to add title in here
Click to add title in here
Стеки
Стек является одной из наиболее используемых и наиболее важных структур данных.
Стеком называется структура данных, в которой элемент, занесенный первым, извлекается последним. Стеки применяются очень часто. Например, распознавание синтаксиса в компиляторе, как и оценка выражений, основано на стеке. На нижнем уровне стеки используются для передачи параметров функциям, выполнения вызова функции и возвращения из нее.
Стек (stack) — это список элементов, доступных только в одном конце списка. Элементы добавляются или удаляются из списка только в вершине (top) стека. Подносы в столовой или стопка коробок являются моделями стека.
Коробки
Модель стека
Стеки
Стек предназначен для хранения элементов, доступных естественным путем в вершине списка.
Стеки
Стек предназначен для хранения элементов, доступных естественным путем в вершине списка.
Абстрактное понятие стека допускает неопределенно большой список. Логически подносы в столовой могут складываться бесконечно. В действительности подносы находятся на полке, а овощи нанизаны на коротких шампурах. Когда полка или шампур переполнены, мы не можем добавить (Push) еще один элемент в стек. Стек достигает максимального количества элементов, которыми он может управлять. Эта ситуация поясняет значение условия полного стека (stack full). Другая крайность — вы не можете взять поднос с пустой полки. Условие пустого стека (stack empty) подразумевает, что вы не можете удалить (Pop) элемент. Описание абстрактного типа данных Stack включает только условие пустого стека. Условие полного стека является уместным в том случае, если реализация содержит верхнюю границу размера списка.
В алгоритме быстрой сортировки стек используется для хранения границ неупорядоченных фрагментов. В принципе, порядок, в котором они будут обрабатываться, не критичен (главное, чтобы в конце концов все фрагменты оказались отсортированными), но удобнее всего стек использовать из-за простоты его реализации.
Стеки
Реализация функций стека
В структуре стека важнейшее место занимают операции, добавляющие
Стеки
Реализация функций стека
В структуре стека важнейшее место занимают операции, добавляющие
A
A
A
A
A
B
B
B
C
Push A
Push B
Push C
Pop
Pop
D
Push D
Помещение в стек и извлечение из него.
Стеки
Для стека определены всего две операции: занесение элемента и выборка элемента.
Стеки
Для стека определены всего две операции: занесение элемента и выборка элемента.
struct Node {
int left, right;
Node* p;
};
Node* top = 0;
// Элемент стека
// Вершина стека
В C++ определена стандартная константа NULL, значение которой равно нулю типа «указатель», но поскольку правила преобразования типов обеспечивают правильное преобразование целого нуля в нуль типа «указатель», в этой константе нет необходимости.
Стеки
Удобно оформить занесение и выборку элемента в виде отдельных функций. Функция
Стеки
Удобно оформить занесение и выборку элемента в виде отдельных функций. Функция
// Начальное формирование стека
Node *first(int d)
{
Node *pv = new Node;
pv->d = d;
pv->p = 0;
return pv;
}
Стеки
Однако можно и не использовать отдельную функцию для занесения первого элемента
Стеки
Однако можно и не использовать отдельную функцию для занесения первого элемента
// Занесение в стек
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
}
Стеки
В результате выполнения этой операции некоторой переменной i должно быть присвоено
Стеки
В результате выполнения этой операции некоторой переменной i должно быть присвоено
// Извлечение из стека
Procedure readStack(Var u : EXST; Var i : integer); Var x : EXST; Begin i := u^.Data; {считываем значение поля данных в переменную} x := u; {запоминаем адрес вершины стека} u := u^.Next; {переносим вершину стека на следующий элемент} dispose(x); {освобождаем память, занятую уже ненужным элементом стека} End.
Стеки
Рассмотрим эти функции, самым тщательным образом вникая в детали. Чтобы занести
Стеки
Рассмотрим эти функции, самым тщательным образом вникая в детали. Чтобы занести
Прежде всего мы описываем вспомогательную переменную-указатель и заносим в нее адрес нового элемента стека, который создается с помощью операции new (oпeратор 1). Выделяется столько памяти, сколько необходимо для хранения структуры типа Node. В операторах 2 и 3 информационные поля этой структуры left и right заполняются значениями переданных в функцию границ фрагмента массива. Доступ к этим полям выполняется через указатель pv и операцию выбора ->. Новый элемент становится вершиной стека. Поле его указателя должно ссылаться на элемент, помещенный в стек ранее. Эта ссылка создается в операторе 4. Если «заталкиваемый» в стек элемент является первым, то в качестве первого аргумента функции push() надо задать 0. Функция push возвращает указатель на вершину стека. Им всегда является указатель на только что занесенный элемент (оператор 5).
Стеки
Выборка из стека (функция pop) выполняется аналогично.
Сначала из вершины стека
Стеки
Выборка из стека (функция pop) выполняется аналогично.
Сначала из вершины стека
элемент (оператор 6), который станет новой вершиной стека.
Этот указатель является возвращаемым значением функции
(оператор 10). Информационная часть элемента заносится в
переменные 1 и r, которые передаются в вызывающую функцию по
ссылке (операторы 7 и 8). После того как вся информация из элемента
выбрана, его можно удалить (оператор 9). Эти функции можно
применить в любой программе, где требуется стек, просто изменив
поля, составляющие его информационную часть, и соответствующие
параметры.