Материал: 7
Титульный лист материалов по дисциплине
ДИСЦИПЛИНА Программирование на Java
полное название дисциплины без аббревиатуры
ИНСТИТУТ Информационных технологий
КАФЕДРА ИППО
полное название кафедры
ГРУППА/Ы
номер групп/ы, для которых предназначены материалы
ВИД УЧЕБНОГО лекция
МАТЕРИАЛА лекция; материал к практическим занятиям; контрольно-измерительные материалы к практическим занятиям; руководство к КР/КП, практикам
ПРЕПОДАВАТЕЛЬ Зорина Наталья Валентиновна
фамилия, имя, отчество
СЕМЕСТР
указать номер семестра обучения
Тема №7: Введение в обобщенные типы данных. Абстрактные типы данных и использование контейнерных классов в Java
Содержание
1.Абстрактные типы данных: стек и очередь
2.Дженерики и параметризованные типы.
3.Стек как абстрактный тип данных: реализация стека на основе простого массива и на основе обобщенного связанного списка.
4.Очередь как абстрактный тип данных: реализация очереди на основе простого массива и на основе обобщенного связанного списка.
5.Дек как абстрактный тип данных: реализация дека.
6.Интерфейс стека в Java.
Дженерики
В JDK введены так называемые обобщенные или параметризованные типы – generics или по-другому обобщенные типы.
Параметризованных (generic) классы и методы, позволяют использовать более гибкую и в то же время достаточно строгую типизацию, что особенно важно при работе с коллекциями.
Использование параметризации позволяет создавать классы, интерфейсы и методы, в которых тип обрабатываемых данных задается как параметр.
Дженерики или обобщенные типы позволяют вам абстрагироваться от использования конкретных типов.
Вы можете создать класс с таким общим типом и предоставить информацию об определенном типе во время создания экземпляра объекта типа класс.
Компилятор сможет выполнить необходимую проверку типов во время компиляции.
Конвенция кода Java об именах для формальных типов
Например:
•<E> для элемента коллекции;
•<T> для обобщенного типа;
•<K, V> ключ и значение.
•<N> для чисел
•S,U,V, и т.д. для второго, третьего, четвертого типа параметра
Дженерики являются способом определить, какие типы допустимы в вашем классе или функции.
// старый способ
List myIntList1 = new LinkedList(); // 1 myIntList1.add(new Integer(0)); // 2
Integer x1 = (Integer) myIntList1.iterator().next(); // 3
// с generics
List<Integer> myIntList2 = new LinkedList<Integer>(); // 1’ myIntList2.add(new Integer(0)); // 2’
Integer x2 = myIntList2.iterator().next(); // 3’
Пример 1 – Определение обобщенных типов:
public interface List<E> { void add(E x); Iterator<E> iterator();
}
public interface Iterator<E> { E next();
boolean hasNext();
}
public interface Map<K,V> { V put(K key, V value);
}
Пример 2 –определение (собственных) универсальных или обобщенных типов:
public class GenericClass<T> { private T obj;
public void setObj(T t) {obj = t;} public T getObj() {return obj;} public void print() {
System.out.println(obj);
}
}
Main:
GenericClass<Integer> g = new GenericClass<Integer>(); g.setObj(5); // автоупаковка
int i = g.getObj(); // автораспаковкаg.print();
Абстрактные типы данныхконтейнеры
Что такое Стек?
Стеком (в переводе с английского – stack – стопка; stack — стопка; читается как стэк) называется линейная динамическая структура данных, добавление и исключение элементов в которую и производится с одного конца, называемого вершиной стека.
Стек работает по принципу LIFO (Last-In, First-Out) - "поступивший последним, обслуживается первым».
Примеры Стека Примеры применения стека — любая рекурсивная задача (“так, старую
итерацию пока отложу в стопку, а сейчас надо обрабатывать новую итерацию!“), например, перебор маршрутов исследовательского робота в пещере неизвестной конфигурации.
Самые первые калькуляторы были напрямую сделаны как стеки. Вместо “2+2” нужно было вводить “2 2 +”. Первые два элемента (“операнды”) клались в стек, пока не будет введён плюс (“оператор”).
Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
Основными операциями над стеками являются:
•добавление элемента - push()
•удаление элемента - pop()
Абстрактные типы данных (АТД) или структуры данных
Абстрактный тип данных (ADT) является абстракцией структуры данных. АТД определяет:
•Хранение данных
•Операции выполняемые над данными
•Условия возникновения ошибок, связанных с выполнением
операций
Пример: AТД для моделирования фондовой биржи Данные это заказы на покупку / продажу. Поддерживаются операции
•Заказ на покупку(акций)
•Заказ на продажу(акций)
•Отмена заказа(заказ)
Условия возникновения ошибок:
•Купить / продать несуществующие акции
•Отменить несуществующий заказ
ATД стек
В АТД Стеке можно хранить произвольные объекты хранит произвольные объекты.
Вставки и удаления следуют за последним элементом в LIFO. Основные операции работы со стеком:
•push(object): вставка (вталкивание) нового элемента в стек.