3-й семестр / Лекции / 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): вставка (вталкивание) нового элемента в стек.

•object pop(): удаляет из стека (выталкивает) и возвращает последний добавленный элемент.

Вспомогательные операции работы со стеком:

•object top(): возвращает последний вставленный элемент, не удаляя его (чтение элемента).

•integer size(): возвращает количество элементов, которые хранятся

встеке.

•boolean isEmpty(): показывает, является ли стек пустым.

Интерфейс для Стека в Java

ВJava есть интерфейс, соответствующий нашему АТД Stack. Требуется импорт для определения класса.

EmptyStackException

Вотличие от встроенного класса Javajava.util.Stack.

public interface Stack { public int size(); public boolean isEmpty(); public Object top()

throws EmptyStackException; public void push(Object o);

public Object pop()

throws EmptyStackException;

}

Исключения при работе со стеком

Попытка выполнения операции с AТД может иногда вызвать состояние ошибки, называемое исключением.

Исключения, как принято говорить, “выбрасывается" с помощью операции, которая не может быть выполнена!

В АТД Stack, операции pop() и top() не могут быть выполнены над элементами, например, если стек пуст.

При попытке (на пустом стеке) выполнить в этом случае операции pop() и top() выбрасывает EmptyStackException.

Интерфейс Стек в Java

import java.util.Stack;

import java.util.EmptyStackException;

class StackExample {

static void showpush(Stack st, int a) { st.push(new Integer(a)); System.out.println("push(" + a + ")"); System.out.println("stack: " + st);

}

static void showpop(Stack st) { System.out.print("pop -> "); Integer a = (Integer) st.pop(); System.out.println(a); System.out.println("stack: " + st);

}

public static void main(String args[]) { Stack st = new Stack(); System.out.println("stack: " + st); showpush(st, 42);

showpush(st, 66); showpush(st, 99); showpop(st); showpop(st); showpop(st);

try {

}

}

Применение стеков

Прямое применение

•история посещений страниц в веб-браузере