Материал: 7 - Презентация - Дженерики, Абстрактные типы данных, Стек, Очередь
Центрдистанционногообучения
Производительность и ограничения
•Производительность
•Пусть n число элементов в стеке
•Используемое пространство O(n)
•Каждая операция занимает время выполнения O(1)
•Ограничения
•Максимальный размер стека должен быть определен заранее и не может быть изменен
•Попытка затолкннуть новый элемент в полный стек вызывает соответствующее исключение переполнение—Overflow.
26 online.mirea.ru
Центрдистанционногообучения
Стек на основе массива в 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;
} 27 online.mirea.ru
Центрдистанционногообучения
Стек на основе связанного списка
•Мы можем реализовать стек в виде односвязного списка
•Верхний элемент (верхушка стека) хранится в первом узле списка
•Используемое пространство - O(n) и каждая операция стека
над ATД занимает время O (1)
nodes
t |
Æ |
|
элементы |
|
Стек |
28 |
online.mirea.ru |
Центрдистанционногообучения
Пример Стек на основе связанного списка (1/4)
•Верхушка стека – заглавный элемент связанного списка.
•Переменная экземпляра сохраняет текущее количество элементов.
•Push():создать новый узел и добавить его в верхнюю часть стека.
•Pop():удалить узел из верхней части стека.
Top – верхушка
стека
Bottom - Дно стека
Sydney |
Rome |
Seattle |
New York |
29 online.mirea.ru
Центрдистанционногообучения
Стек на основе связанного списка (2/4) Класс Node (узел списка):
public class Node<E> { // поклассая |
: |
|
|
private E element; |
|
|
|
private Node<E> next; |
|
|
|
// Создаемузелснулевымиссылкаминасебяслед.узел |
|
|
|
public Node() { this(null, null); } |
|
||
//Создаетузелсзаданнымэлемеиссылкойследатом. |
|
|
|
узел. |
|
|
|
public Node(E e, Node<E> n) { element = e; next = n; } |
|||
// Методыгеттеры |
: |
|
|
public E getElement() { return element; } |
|
||
public Node<E> getNext() { return next; } |
|
||
// Методысеттеры |
: |
|
|
public void setElement(E newElem) { element = newElem; } |
|||
public void setNext(Node<E> newNext) { next = newNext; } |
|||
} |
|
30 |
online.mirea.ru |
|
|
|
|