Стеки и очереди - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

Стеки

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Стек. Реализация на Java

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Изменение размера массива

Слайд 12

Описание слайда:

Стек: изменение размера массива Проблема. От клиента требуется указывать размер стека Как увеличивать и уменьшать размер массива? Первый подход push(): увеличивать размер массива s[] на 1 pop(): уменьшать размер массива s[] на 1 Стоимость Требуется копировать все элементы в новый массив Сложность вставки первых N элементов 1+2+3+...+N ~ N2/2

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

Стек: изменение размера массива

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

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