Контейнеры, очереди и стеки

1.

Контейнеры, очереди и стеки

2.

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

3.

Клиент, реализация, интерфейс
Разделяйте интерфейс и реализацию
Пример: стек, очередь, контейнер, очередь с
приоритетом, символьная таблица...
Преимущества
Клиент не знает деталей реализации => клиент
может выбирать из множества реализаций
Реализация не знает деталей клиентского
приложения => разные клиенты могут повторно
использовать одну реализацию
Создание: модульность, повторно используемые
библиотеки

4.

Стеки

5.

API стека
API. Стек для строк
Вывод элементов в обратном порядке

6.

Стек. Клиент
Прочитать строку
Если строка равна «-», то изъять элемент из
стека и вывести его
Иначе, занести строку в стек

7.

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

8.

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

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

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

19.

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

20.

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

21.

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

22.

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

23.

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

24.

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

25.

Очередь

26.

API очереди

27.

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

28.

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

29.

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

30.

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

31.

Коллекции

32.

Стек
Реализовано: StackOfStrings
Нужно реализовать: StackOfUrls, StackOfInts,
StackOfVans...
Подход 1. Реализовать класс Stack для
каждого типа данных
Переписывать код утомительно и
возможны ошибки

33.

Стек
Реализовано: StackOfStrings
Нужно реализовать: StackOfUrls, StackOfInts,
StackOfVans...
Подход 2. Реализовать стек для объектов типа
Object
Приведение типов нужно делать клиенту
Ошибки приведения типов: ошибки во время
выполнения (не совпадение типов)

34.

Стек
Реализовано: StackOfStrings
Нужно реализовать: StackOfUrls, StackOfInts,
StackOfVans...
Подход 3. Коллекции
Приведение типов не нужно делать клиенту
Ошибки приведения типов: ошибки во время
компиляции, а не выполнения
Руководящий принцип: ошибки во время
компиляции намного лучше, чем ошибки во время
выполнения

35.

Стек. Коллекции. Связный список

36.

Стек. Коллекции. Массив

37.

Стек. Коллекции. Массив

38.

Стек. Коллекции. Массив

39.

Коллекции: автоупаковка
Упаковка типов
Каждый примитивный тип упаковывается в
ссылочный тип
Пример: Integer обертка для int
Автоупаковка. Автоматическое приведение
примитивного типа и его обертки
Клиент должен иметь возможность использовать

40.

Итераторы

41.

Итерации
Поддерживают итерации в стеке без раскрытия
информации о реализации стека
Реализация Java. Реализованы в интерфейсе

42.

Итераторы
Что такое Iterable?
Метод, который возвращает
Iterator.
Что такое Iterator?
Содержит методы hasNext() и
next().
Зачем структурам данных
Iterable?

43.

Итераторы стека: связный список

44.

Итераторы стека: массив

45.

API контейнеров
Добавляем элементы в контейнер и итерируем
(порядок не важен)
Реализация. Стек (без pop) или очередь (без dequeue)

46.

Применение очередей, контейнеров и стеков

47.

Применение стека

48.

Вычисление арифметических
выражений
Цель. Вычислить выражение в
инфиксной форме
Двустековый алгоритм Дейкстры
Значение: занести в стек
значений
Оператор: занести в стек
оператор
Левая скобка: игнорируем
Правая скобка: выталкиваем
оператор и два значения,

49.

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