Материал: 7 - Презентация - Дженерики, Абстрактные типы данных, Стек, Очередь
Центрдистанционногообучения
Стек на основе связанного списка (3/4)
public class NodeStack<E> implements Stack<E> {
protected Node<E> top; |
//ссылканазаглавное |
звено |
|
protected int size; |
//количествоэлементов |
стеке |
|
// конструируемпустекой
public NodeStack() { |
|
|
|
top = null; |
|
|
|
size = 0; |
|
|
|
} |
|
|
|
public int size() { return |
size; } |
|
|
public boolean isEmpty() |
{ |
|
|
if (top == |
null) return |
true; |
|
return |
false; } |
31 |
online.mirea.ru |
Центрдистанционногообучения
Стек на основе связанного списка (4/4)
public void push(E elem) {
// создаеми привязывем новыйузел
Node<E> v = new Node<E>(elem, top);
top = v; size++; }
public E top() throws EmptyStackException {
if (isEmpty()) throw new EmptyStackException("Stack is empty.");
return top.getElement(); } public E pop() throws EmptyStackException {
if (isEmpty()) throw new EmptyStackException("Stack is empty.");
E temp = top.getElement();
top = top.getNext(); // отделяембыверхнимший
узел
size--; return temp; }
32 online.mirea.ru
Центрдистанционногообучения
Стек на основе связанного списка (5/4)
•Каждый из методов интерфейса Stack требует постоянного времени.
•сложность O (n), где n число элементов в стеке.
•Нет проблемы с переполнением, как в массиве на основе стека.
33 online.mirea.ru
Центрдистанционногообучения
Пример: Сопоставление скобок
•Каждая открывающая скобка “(”, “{”, или “[” должна иметь закрывающую пару, в соответствии с ее типом “)”, “}”, или “[”
•правильно: ( )(( )){([( )])}
•правильно: (( )( )){([( )])}
•неправильно: )(( )){([( )])}
•неправильно: ({[ ])}
•неправильно: (
34 online.mirea.ru
Алгоритм сопоставленияЦентрдискобоктанционнобучения го
Algorithm ParenMatch(X,n):
{Ввод: Какой либо массив X из n токенов, каждый из которых является либо символом скобок (группирующим символом), переменная, арифметический оператор, или число
Вывод: true- тогда и только тогда, когда все группы символов в X соответствуют Let S be an empty stack;
for ( i=0; i < n; i++)
if ( X[i] является открывающим группирующим символом) S.push(X[i]);
else if ( X[i]является закрывающим группирующим символом)
{
if ( S.isEmpty() ) |
|
return false; |
// ничего не соответствует |
if ( S.pop() не соответствует X[i] ) |
|
return false; |
// неправильный тип |
}
if ( S.isEmpty() )
return true; |
// каждый символ соответствует |
|
|
else |
|
|
|
return false; |
// некоторые символы не соответствуют } |
35 |
online.mirea.ru |