Материал: 7 - Презентация - Дженерики, Абстрактные типы данных, Стек, Очередь
Центрдистанционногообучения
Интерфейс Стек в Java
stack: [] push(42) stack: [42] push(66) stack: [42, 66] push(99)
stack: [42, 66, 99] pop -> 99
stack: [42, 66] pop -> 66
21 online.mirea.ru
Центрдистанционногообучения
Применение стеков
•Прямое применение
•история посещений страниц в веб-браузере
•Последовательность отмены операций (undo) в текстовом редакторе
•цепочка вызовов метода в виртуальной машине Java
•Косвенное применение
•Вспомогательная структура данных для алгоритмов
•Компонент других структур данных
22 online.mirea.ru
Стек метода в JVM
•Java Virtual Machine (JVM) отслеживает цепочки вызова активных методов со стеком
•Когда вызывается метод, виртуальная
машина заталкивает в стек фрейм метода, содержащий
•Локальные переменные и возвращаемое значение
•Программный счетчик,
отслеживающий выполнение операторов
•Когда метод заканчивается, то его фрейм извлекается из стека и управление передается методу, на вершине стека
•Это позволяет делать рекурсивные методы
Центрдистанционногообучения
main() { |
|
|
int i = 5; |
bar |
|
foo(i); |
PC = 1 |
|
} |
m = 6 |
|
foo(int j) { |
|
|
foo |
||
int k; |
||
PC = 3 |
||
k = j+1; |
||
j = 5 |
||
bar(k); |
k = 6 |
|
} |
|
|
|
||
bar(int m) { |
main |
|
PC = 2 |
||
… |
i = 5 |
|
} |
|
|
|
23 online.mirea.ru
Центрдистанционногообучения
Стек на основе массива (1/2)
•Простой способ реализации AТД стека с использованием массива
•Мы добавляем элементы слева направо
•Переменная хранит индекс верхнего элемента
Algorithm size() { return t + 1; }
Algorithm pop() { if ( isEmpty() )
throw EmptyStackException; else
t = t - 1; return S[t + 1];
}
S |
… |
|
0 1 2 |
24 |
online.mirea.ru |
t |
Центрдистанционногообучения
Стек на основе массива (2/2)
•Массив для хранения элементов стека может заполнится
•Операция push() вызовет выброс исключения FullStackException
•Ограничение реализации на базе массивов
•Не свойственно по отношению к Stack как ADT
Algorithm push(o)
{
if ( t = S.length - 1)
throw FullStackException; else
{t = t + 1; S[t] = o;
}
}
S
0 1 2
… |
|
25 |
t |
online.mirea.ru |