Материал: 6 - Презентация 2 - Дженерики, Абстрактные типы данных, Стек

Центр дистанционного обучения

Абстрактные типы данных (ADT)

Интерфейс java.util.List задает абстрактный тип данных “список”. Список – это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза.

У этого интерфейса есть несколько конкретных реализаций, например:

•ArrayList – список на основе динамического массива

•LinkedList – список на основе двусвязного списка

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