3-й семестр / Лекции / 6 - Презентация 2 - Дженерики, Абстрактные типы данных, Стек

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

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

MyStack<String> stack = ...;

stack.push(“A”); // [“A”] stack.push(“B”); // [“A”, “B”]

String top = stack.peek(); // “B”

String e = stack.pop(); // [“A”], e = “B” stack.pop(); // []

online.mirea.ru

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

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

Пример использования стека – задача о проверке баланса скобок в арифметическом выражении:

1.Заводим пустой стек S

2.Перебираем все символы строки

3.Если символ является открывающей скобкой (‘(‘, ‘[‘, ‘{‘), то добавляем ее в стек (push)

4.Если символ является закрывающей скобкой, то:

1.Открывающая скобка на вершине стека должна подходить к закрывающей: (), [], {}, если не подходит, то нет баланса

2.Извлекаем символ из стека (pop)

5.После окончания перебора стек должен быть пуст

online.mirea.ru

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

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

Реализация стека на основе массива – ArrayStack:

•массив фиксированной длины, при переполнении будем выбрасывать исключение

•нулевой элемент массива – дно стека, вершина стека будет плавающей:

вершина стека

online.mirea.ru

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

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

public class ArrayStack<E> implements MyStack<E> {

private final E[] elements; private int top = -1;

public ArrayStack(E[] elements) { this.elements = elements;

}

@Override

public void push(E element) { int nextTop = top + 1;

if (nextTop >= elements.length) throw new IllegalStateException("Stack is full: max size is " + elements.length); elements[top = nextTop] = element;

}

@Override public E pop() {

if (isEmpty()) throw new IllegalStateException("Stack is empty: cannot pop"); E result = elements[top];

elements[top] = null; top--;

return result;

}

}

online.mirea.ru

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

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

Для чего нужно присваивание “elements[top] = null” в pop?

MyStack<String> stack = new ArrayStack<>(new String[10]); stack.push(“A”.repeat(1_000_000));

stack.pop();

//Без обнуления ссылка на строку из миллиона символов

//так и будет находиться в массиве до следующего push,

//и сборщик мусора не будет освобождать эту память,

//хотя она по сути уже не нужна

online.mirea.ru

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

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

Из-за ограничения на generics мы не можем вызвать new E[] в конструкторе ArrayStack, и вынуждены передавать массив извне. Это можно обойти с помощью некоторых хаков.

online.mirea.ru

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

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

public class ArrayStack2<E> implements MyStack<E> {

private final Object[] elements;

private int top = -1;

public ArrayStack2(int size) { this.elements = new Object[size];

}

@Override public E pop() {

if (isEmpty()) throw new IllegalStateException("Stack is empty: cannot pop"); E result = (E) elements[top];

elements[top] = null; top--;

return result;

}

}

online.mirea.ru

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

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

В общем случае эта строка:

E result = (E) elements[top]; // Object[] elements

может вызывать ClassCastException, поэтому компилятор выдает для нее предупреждение:

ArrayStack2.java uses unchecked or unsafe operations

Но в нашем случае мы можем гарантировать, что массив elements всегда содержит только элементы типа E, хотя он и объявлен как массив Object, так как мы помещаем в массив элементы только в методе push со значением типа E.

online.mirea.ru