Материал: 7
•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 {
}
}
Применение стеков
Прямое применение
•история посещений страниц в веб-браузере
• |
Последовательность отмены операций (undo) |
в текстовом |
редакторе |
|
|
•цепочка вызовов метода в виртуальной машине Java
•Косвенное применение
•Вспомогательная структура данных для алгоритмов
•Компонент других структур данных
Стек метода в JVM
Java Virtual Machine (JVM) отслеживает цепочки вызова активных методов со стеком.
Когда вызывается метод, виртуальная машина заталкивает в стек фрейм метода, содержащий.
•Локальные переменные и возвращаемое значение
•Программный счетчик, отслеживающий выполнение операторов
•Когда метод заканчивается, то его фрейм извлекается из стека и управление передается методу, на вершине стека
Это позволяет делать рекурсивные методы.
main() {
int i = 5; foo(i);
}
foo(int j) { int k; k = j+1; bar(k);
}
bar(int m) {
…
}
Стек на основе массива (1/2)
Простой способ реализации AТД стека с использованием массива. Мы добавляем элементы слева направо.
Переменная хранит индекс верхнего элемента.
Algorithm size() { return t + 1; }
Algorithm pop()
{if ( isEmpty() )
throw EmptyStackException; else
t = t - 1; return S[t + 1];
}
Массив для хранения элементов стека может заполнится. Операция push() вызовет выброс исключения FullStackException.
•Ограничение реализации на базе массивов
•Не свойственно по отношению к Stack как ADT
Algorithm push(o)
{
if ( t = S.length - 1)
throw FullStackException;
else
{ t = t + 1; S[t] = o;
}
}
Производительность и ограничения
Производительность
•Пусть n число элементов в стеке
•Используемое пространство O(n)
•Каждая операция занимает время выполнения O(1) Ограничения
•Максимальный размер стека должен быть определен заранее и не может быть изменен
•Попытка затолкннуть новый элемент в полный стек вызывает соответствующее исключение переполнение—Overflow.
Стек на основе массива в Java
public class ArrayStack implements Stack {
//содержит элементы стека private Object S[ ];
//индекс верхнего элемента private int top = -1;
//конструктор
public ArrayStack(int capacity) { S = new Object[capacity]);
}
public Object pop()
throws EmptyStackException { if isEmpty()
throw new EmptyStackException (“Empty stack: cannot pop”);
Object temp = S[top]; // облегчает сбор мусора
S[top] = null; top = top – 1; return temp;
}
Стек на основе связанного списка
Мы можем реализовать стек в виде односвязного списка. Верхний элемент (верхушка стека) хранится в первом узле списка.
Используемое пространство - O(n) и каждая операция стека над ATД занимает время O (1).
Пример Стек на основе связанного списка (1/4)
Верхушка стека – заглавный элемент связанного списка. Переменная экземпляра сохраняет текущее количество элементов. Push():создать новый узел и добавить его в верхнюю часть стека. Pop():удалить узел из верхней части стека.
public class Node<E> { // поля класса: private E element;
private Node<E> next;