Материал: 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)
private static boolean match(char open, char close) {
return (open == '(' && close == ')') || (open == '[' && close == ']') || (open == '{' && close == '}');
}
public static boolean hasBalance(String str) { MyStack<Character> stack = ...;
for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i);
if (ch == '(' || ch == '[' || ch == '{') { stack.push(ch);
} else if (ch == ')' || ch == ']' || ch == '}') { if (stack.isEmpty())
return false;
|
char open = stack.pop(); |
|
if (!match(open, ch)) |
|
return false; |
|
} |
|
} |
|
return stack.isEmpty(); |
} |
online.mirea.ru |
Центр дистанционного обучения
Абстрактные типы данных (ADT)
Реализация стека на основе массива – ArrayStack:
•массив фиксированной длины, при переполнении будем выбрасывать исключение
•нулевой элемент массива – дно стека, вершина стека будет плавающей:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
|
|
|
|
|
|
|
‘(‘ |
‘(‘ |
‘[‘ |
‘{‘ |
‘(‘ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
вершина стека
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