Стек. LIFO
Очередь. FIFO
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Стеки и очереди презентация
Содержание
- 1. Стеки и очереди
- 2. Стеки
- 3. Стек. Связный список Хранить указатель на первый
- 4. Изъять элемент из стека. Реализация с помощью связного списка
- 5. Добавить элемент в стек. Реализация с помощью связного списка
- 6. Стек. Реализация на Java
- 7. Стек. Производительность реализации с помощью связного списка
- 8. Стек. Реализация с помощью массива Массив s[]
- 9. Стек. Реализация с помощью массива
- 10. Стек. Некоторые соображения Переполнение и изъятие из
- 11. Изменение размера массива
- 12. Стек: изменение размера массива Проблема. От клиента
- 13. Стек: изменение размера массива Если массив полон,
- 14. Стек: амортизированная стоимость добавления в стек Стоимость
- 15. Стек: изменение размера массива Как изменять размер
- 16. Стек: изменение размера массива Эффективный подход push():
- 17. Стек: изменение размера массива
- 18. Стек: амортизированный анализ Предположение. Начиная с пустого
- 19. Стек: использование памяти Предположение. Используется от ~
- 20. Реализация стек: массив и связный список Компромисс.
- 21. Очередь
- 22. Очередь: связный список Хранить указатели на первый
- 23. Очередь: удаление элемента Аналогична операции pop() для стека
- 24. Очередь: вставка элемента
- 25. Очередь: реализация на Java
- 26. Применение очередей, контейнеров и стеков
- 27. Применение стека
- 28. Вычисление арифметических выражений Цель. Вычислить выражение в
- 29. Вычисление арифметических выражений
Стеки
Слайд 1Стеки и очереди
Фундаментальные структуры данных
Значения: коллекции объектов
Операции: вставка, удаление, итерации, проверка
на пустоту
Слайд 3Стек. Связный список
Хранить указатель на первый элемент связного списка; вставку/удаление делать
с вершины стека
Слайд 7Стек. Производительность реализации с помощью связного списка
Каждая операция производится за время
равное константе
Стек из N элементов испольщует ~ 40N байт
Стек из N элементов испольщует ~ 40N байт
Замечание: здесь учитывается сколько занимает сам стек. Память, которую занимают строки нужно учитывать отдельно.
Слайд 8Стек. Реализация с помощью массива
Массив s[] для хранения N элементов стека
push():
добавит новый элемент в s[N]
pop(): изъять элемент из s[N-1]
pop(): изъять элемент из s[N-1]
Дефект. Переполнение массива
Слайд 10Стек. Некоторые соображения
Переполнение и изъятие из пустого стека
Изъятие из пустого стека:
исключительная ситуация
Переполнение: изменить размер массива
null: свободное место в массиве
Бесхозные ссылки: хранение ссылок на объекты, когда они больше не нужны
Переполнение: изменить размер массива
null: свободное место в массиве
Бесхозные ссылки: хранение ссылок на объекты, когда они больше не нужны
Слайд 12Стек: изменение размера массива
Проблема. От клиента требуется указывать размер стека
Как увеличивать
и уменьшать размер массива?
Первый подход
push(): увеличивать размер массива s[] на 1
pop(): уменьшать размер массива s[] на 1
Стоимость
Требуется копировать все элементы в новый массив
Сложность вставки первых N элементов 1+2+3+...+N ~ N2/2
Первый подход
push(): увеличивать размер массива s[] на 1
pop(): уменьшать размер массива s[] на 1
Стоимость
Требуется копировать все элементы в новый массив
Сложность вставки первых N элементов 1+2+3+...+N ~ N2/2
Слайд 13Стек: изменение размера массива
Если массив полон, то создать новый массив в
два раза больше и копировать элементы
Стоимость. Сложность вставки первых N элементов пропорциональна N
Слайд 14Стек: амортизированная стоимость добавления в стек
Стоимость добавления первых N элементов: N
+ (2 + 4 + 8 + … + N) ~ 3N
Слайд 15Стек: изменение размера массива
Как изменять размер массива?
Первый подход
push(): увеличивать размер массива
s[] в два раза, когда массив полон
pop(): уменьшать размер массива s[] в два раза, когда массив на половину пуст
Худший случай дорог
Представим push-pop-push-pop-..., когда массив полон
Сложность каждой операции пропорциональна N
pop(): уменьшать размер массива s[] в два раза, когда массив на половину пуст
Худший случай дорог
Представим push-pop-push-pop-..., когда массив полон
Сложность каждой операции пропорциональна N
Слайд 16Стек: изменение размера массива
Эффективный подход
push(): увеличивать размер массива s[] в два
раза, когда массив полон
pop(): уменьшать размер массива s[] в два раза, когда массив заполнен на четверть
pop(): уменьшать размер массива s[] в два раза, когда массив заполнен на четверть
Массив заполнен от 25% до 100%
Слайд 18Стек: амортизированный анализ
Предположение. Начиная с пустого стека, последовательность из M push/pop
операций занимает время пропорциональное M
Слайд 19Стек: использование памяти
Предположение. Используется от ~ 8N до ~ 32N байт
для стека из N элементов
~ 8N когда стек полон
~ 32N когда стек заполнен на четверть
~ 8N когда стек полон
~ 32N когда стек заполнен на четверть
Учитывается память, занимаемая самим стеком, но не данными
Слайд 20Реализация стек: массив и связный список
Компромисс. Сделать две реализации стека и
дать возможность клиенту выбрать.
Связный список
Каждая операция занимает константное время в худшем случае
Использует дополнительное время и память для организации ссылок
Массив
Каждая операция занимает константное амортизированное время
Занимает меньше памяти
Связный список
Каждая операция занимает константное время в худшем случае
Использует дополнительное время и память для организации ссылок
Массив
Каждая операция занимает константное амортизированное время
Занимает меньше памяти
Слайд 22Очередь: связный список
Хранить указатели на первый и последний элемент; вставка/удаление элементов
происходит с противоположных концов
Слайд 28Вычисление арифметических выражений
Цель. Вычислить выражение в инфиксной форме
Двустековый алгоритм Дейкстры
Значение: занести
в стек значений
Оператор: занести в стек оператор
Левая скобка: игнорируем
Правая скобка: выталкиваем оператор и два значения, выполняем операцию и заносим в стек значений
Где используется?
Интерпретатор
Оператор: занести в стек оператор
Левая скобка: игнорируем
Правая скобка: выталкиваем оператор и два значения, выполняем операцию и заносим в стек значений
Где используется?
Интерпретатор
