🗊Презентация Стеки и очереди

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Стеки и очереди, слайд №1Стеки и очереди, слайд №2Стеки и очереди, слайд №3Стеки и очереди, слайд №4Стеки и очереди, слайд №5Стеки и очереди, слайд №6Стеки и очереди, слайд №7Стеки и очереди, слайд №8Стеки и очереди, слайд №9Стеки и очереди, слайд №10Стеки и очереди, слайд №11Стеки и очереди, слайд №12Стеки и очереди, слайд №13Стеки и очереди, слайд №14Стеки и очереди, слайд №15Стеки и очереди, слайд №16Стеки и очереди, слайд №17Стеки и очереди, слайд №18Стеки и очереди, слайд №19Стеки и очереди, слайд №20Стеки и очереди, слайд №21Стеки и очереди, слайд №22Стеки и очереди, слайд №23Стеки и очереди, слайд №24Стеки и очереди, слайд №25Стеки и очереди, слайд №26Стеки и очереди, слайд №27Стеки и очереди, слайд №28Стеки и очереди, слайд №29
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Стеки и очереди. Доклад-сообщение содержит 29 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Стеки и очереди Фундаментальные структуры данных Значения: коллекции объектов Операции: вставка, удаление, итерации, проверка на пустоту
Описание слайда:
Стеки и очереди Фундаментальные структуры данных Значения: коллекции объектов Операции: вставка, удаление, итерации, проверка на пустоту

Слайд 2


Стеки
Описание слайда:
Стеки

Слайд 3


Стек. Связный список Хранить указатель на первый элемент связного списка; вставку/удаление делать с вершины стека
Описание слайда:
Стек. Связный список Хранить указатель на первый элемент связного списка; вставку/удаление делать с вершины стека

Слайд 4


Изъять элемент из стека. Реализация с помощью связного списка
Описание слайда:
Изъять элемент из стека. Реализация с помощью связного списка

Слайд 5


Добавить элемент в стек. Реализация с помощью связного списка
Описание слайда:
Добавить элемент в стек. Реализация с помощью связного списка

Слайд 6


Стек. Реализация на Java
Описание слайда:
Стек. Реализация на Java

Слайд 7


Стек. Производительность реализации с помощью связного списка Каждая операция производится за время равное константе Стек из N элементов испольщует ~ 40N байт
Описание слайда:
Стек. Производительность реализации с помощью связного списка Каждая операция производится за время равное константе Стек из N элементов испольщует ~ 40N байт

Слайд 8


Стек. Реализация с помощью массива Массив s[] для хранения N элементов стека push(): добавит новый элемент в s[N] pop(): изъять элемент из s[N-1]
Описание слайда:
Стек. Реализация с помощью массива Массив s[] для хранения N элементов стека push(): добавит новый элемент в s[N] pop(): изъять элемент из s[N-1]

Слайд 9


Стек. Реализация с помощью массива
Описание слайда:
Стек. Реализация с помощью массива

Слайд 10


Стек. Некоторые соображения Переполнение и изъятие из пустого стека Изъятие из пустого стека: исключительная ситуация Переполнение: изменить размер массива null: свободное место в массиве Бесхозные ссылки: хранение ссылок на объекты, когда они больше не нужны
Описание слайда:
Стек. Некоторые соображения Переполнение и изъятие из пустого стека Изъятие из пустого стека: исключительная ситуация Переполнение: изменить размер массива null: свободное место в массиве Бесхозные ссылки: хранение ссылок на объекты, когда они больше не нужны

Слайд 11


Изменение размера массива
Описание слайда:
Изменение размера массива

Слайд 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


Стек: изменение размера массива Если массив полон, то создать новый массив в два раза больше и копировать элементы
Описание слайда:
Стек: изменение размера массива Если массив полон, то создать новый массив в два раза больше и копировать элементы

Слайд 14


Стек: амортизированная стоимость добавления в стек Стоимость добавления первых N элементов: N + (2 + 4 + 8 + … + N) ~ 3N
Описание слайда:
Стек: амортизированная стоимость добавления в стек Стоимость добавления первых N элементов: N + (2 + 4 + 8 + … + N) ~ 3N

Слайд 15


Стек: изменение размера массива Как изменять размер массива? Первый подход push(): увеличивать размер массива s[] в два раза, когда массив полон pop(): уменьшать размер массива s[] в два раза, когда массив на половину пуст Худший случай дорог Представим push-pop-push-pop-..., когда массив полон Сложность каждой операции пропорциональна N
Описание слайда:
Стек: изменение размера массива Как изменять размер массива? Первый подход push(): увеличивать размер массива s[] в два раза, когда массив полон pop(): уменьшать размер массива s[] в два раза, когда массив на половину пуст Худший случай дорог Представим push-pop-push-pop-..., когда массив полон Сложность каждой операции пропорциональна N

Слайд 16


Стек: изменение размера массива Эффективный подход push(): увеличивать размер массива s[] в два раза, когда массив полон pop(): уменьшать размер массива s[] в два раза, когда массив заполнен на четверть
Описание слайда:
Стек: изменение размера массива Эффективный подход push(): увеличивать размер массива s[] в два раза, когда массив полон pop(): уменьшать размер массива s[] в два раза, когда массив заполнен на четверть

Слайд 17


Стек: изменение размера массива
Описание слайда:
Стек: изменение размера массива

Слайд 18


Стек: амортизированный анализ Предположение. Начиная с пустого стека, последовательность из M push/pop операций занимает время пропорциональное M
Описание слайда:
Стек: амортизированный анализ Предположение. Начиная с пустого стека, последовательность из M push/pop операций занимает время пропорциональное M

Слайд 19


Стек: использование памяти Предположение. Используется от ~ 8N до ~ 32N байт для стека из N элементов ~ 8N когда стек полон ~ 32N когда стек заполнен на четверть
Описание слайда:
Стек: использование памяти Предположение. Используется от ~ 8N до ~ 32N байт для стека из N элементов ~ 8N когда стек полон ~ 32N когда стек заполнен на четверть

Слайд 20


Реализация стек: массив и связный список Компромисс. Сделать две реализации стека и дать возможность клиенту выбрать. Связный список Каждая операция занимает константное время в худшем случае Использует дополнительное время и память для организации ссылок Массив Каждая операция занимает константное амортизированное время Занимает меньше памяти
Описание слайда:
Реализация стек: массив и связный список Компромисс. Сделать две реализации стека и дать возможность клиенту выбрать. Связный список Каждая операция занимает константное время в худшем случае Использует дополнительное время и память для организации ссылок Массив Каждая операция занимает константное амортизированное время Занимает меньше памяти

Слайд 21


Очередь
Описание слайда:
Очередь

Слайд 22


Очередь: связный список Хранить указатели на первый и последний элемент; вставка/удаление элементов происходит с противоположных концов
Описание слайда:
Очередь: связный список Хранить указатели на первый и последний элемент; вставка/удаление элементов происходит с противоположных концов

Слайд 23


Очередь: удаление элемента Аналогична операции pop() для стека
Описание слайда:
Очередь: удаление элемента Аналогична операции pop() для стека

Слайд 24


Очередь: вставка элемента
Описание слайда:
Очередь: вставка элемента

Слайд 25


Очередь: реализация на Java
Описание слайда:
Очередь: реализация на Java

Слайд 26


Применение очередей, контейнеров и стеков
Описание слайда:
Применение очередей, контейнеров и стеков

Слайд 27


Применение стека
Описание слайда:
Применение стека

Слайд 28


Вычисление арифметических выражений Цель. Вычислить выражение в инфиксной форме
Описание слайда:
Вычисление арифметических выражений Цель. Вычислить выражение в инфиксной форме

Слайд 29


Вычисление арифметических выражений
Описание слайда:
Вычисление арифметических выражений

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию