3-й семестр / Лекции / 6 - Презентация 2 - Дженерики, Абстрактные типы данных, Стек
.pdf
Центр дистанционного обучения
Generics – готовые классы
public interface List<E> {
int size();
void add(E elem);
void add(int index, E elem); E get(int index);
E set(int index, E elem); E remove(int index);
}
public class ArrayList<E> implements List<E> {
}
online.mirea.ru
Центр дистанционного обучения
Generics – готовые классы
List<String> list = new ArrayList<>();
list.add(“String 1”); list.add(“String 2”);
// [“String 1”, “String 2”]
String removed = list.remove(0);
// [“String 2”]
list.set(0, “String 2 revised”);
//[“String 2 revised”] list.add(0, “String 0”);
//[“String 0”, “String 2 revised”]
online.mirea.ru
Центр дистанционного обучения
Generics – готовые классы
Конвенция кода Java об именах типовых параметров:
•<E> для элемента коллекции
•<T> для обобщенного типа
•<K, V> ключ и значение
Традиционно из одной буквы, но это не обязательно.
online.mirea.ru
Центр дистанционного обучения
Абстрактные типы данных (ADT)
Абстрактные типы данных – определяются своим поведением
– набором доступных операций (в отличие от описания их реализации).
В ООП абстрактный тип данных определяется набором методов.
online.mirea.ru
Центр дистанционного обучения
Абстрактные типы данных (ADT)
Абстрактный тип данных ≠ абстрактный класс. Пример ADT на основе конкретного класса:
public class ComplexNumber {
static ComplexNumber fromXY(double x, double y) { ... } static ComplexNumber fromPolar(double r, double phi) { ... } ComplexNumber add(ComplexNumber that) { ... }
...
}
Внутри класс ComplexNumber может быть представлен и в декартовых, и в полярных координатах. Для конечного
пользователя класса это неважно.
online.mirea.ru
Центр дистанционного обучения
Абстрактные типы данных (ADT)
Интерфейс java.util.List задает абстрактный тип данных “список”. Список – это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
size=7 |
|
|
|
|
|
|
|
|
||
“A” |
“B” |
“A” |
“C” |
“D” |
“B” |
“E” |
||
|
||||||||
|
|
|
|
|
|
|
|
У этого интерфейса есть несколько конкретных реализаций, например:
•ArrayList – список на основе динамического массива
•LinkedList – список на основе двусвязного списка
online.mirea.ru
Центр дистанционного обучения
Что такое Стек?
37
online.mirea.ru
Центр дистанционного обучения
Структура данных Стек
Стеком ( в переводе с английского – stack – стопка; stack — стопка; читается как стэк) называется линейная динамическая структура данных, добавление и исключение элементов в которую и производится с одного конца, называемого вершиной стека.
Стек работает по принципу LIFO (Last-In, First-Out) -
"поступивший последним, обслуживается первым».
Магазин пистолета, очередь в кассу, лоток принтера с бумагой, игра “Ханойские башни” — простые примеры стека.
online.mirea.ru
Центр дистанционного обучения
Абстрактные типы данных (ADT)
Абстрактный тип данных “стек” – задается операциями:
•push(e) – поместить элемент e на вершину стека
•e = pop() – удалить элемент с вершины стека и вернуть его значение
•e = peek() – получить элемент с вершины стека без удаления
•size() – размер стека
•isEmpty() – проверка, является ли пустым
online.mirea.ru
Центр дистанционного обучения
Абстрактные типы данных (ADT)
ADT “стек” можно определить интерфейсом:
public interface MyStack<E> { void push(E element);
E pop();
E peek(); int size();
default boolean isEmpty() { return size() == 0; }
}
online.mirea.ru