Разделы презентаций


Стеки

Click to add title in here Click to add title in here Click to add title in here Click to add title in here

Слайды и текст этой презентации

Слайд 1Стеки

Стеки

Слайд 2Click to add title in here
Click to add

title in here
Click to add title in here


Click to add title in here


Стеки



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

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


Коробки

Модель стека

Click to add title in here  Click to add title in here  Click to add

Слайд 3Стеки















Стек предназначен для хранения элементов, доступных естественным путем в вершине

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

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

Слайд 4Стеки

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

операции, добавляющие и удаляющие элементы. Операция 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

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

Стеки            Реализация функций стека В структуре стека

Слайд 5Стеки
Для стека определены всего две операции: занесение элемента и выборка

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

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

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

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

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

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

СтекиДля стека определены всего две операции: занесение элемента и выборка элемента. При выборке элемент удаляется из стека,

Слайд 6Стеки
Удобно оформить занесение и выборку элемента в виде отдельных функций.

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

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

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

Node *first(int d)
{
Node *pv = new Node;
pv->d = d;
pv->p = 0;
return pv;
}
СтекиУдобно оформить занесение и выборку элемента в виде отдельных функций. Функция помещения в стек обычно называется push,

Слайд 7Стеки










Однако можно и не использовать отдельную функцию для занесения первого

элемента в стек, так как если указателю 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
}
СтекиОднако можно и не использовать отдельную функцию для занесения первого элемента в стек, так как если указателю

Слайд 8Стеки
В результате выполнения этой операции некоторой переменной i должно быть

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

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

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

Слайд 9Стеки
Рассмотрим эти функции, самым тщательным образом вникая в детали. Чтобы

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

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

СтекиРассмотрим эти функции, самым тщательным образом вникая в детали. Чтобы занести в стек границы фрагмента, надо передать

Слайд 10Стеки



Выборка из стека (функция pop) выполняется аналогично.
Сначала из вершины

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

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

Слайд 11Стеки

Призентацию подготовил студент группы СИС 11
Дикусар Денис

СтекиПризентацию подготовил студент группы СИС 11Дикусар Денис

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика