Мы знаем, что стек — это контейнер данных, который поступает первым и уходит последним. Когда входная последовательность стека представляет собой возрастающую последовательность (например, a, b, c, d), а операция стека разрешена во время операции push, выходная последовательность может иметь множество форм (например: d, c, b , а или а, в, б, г и т. д.). Но следующей поп-последовательности: a, d, b, c или d, a, b, c и т. д. точно не будет. Предполагая, что входная последовательность является возрастающей последовательностью, напишите алгоритм, определяющий, является ли поп-последовательность, представленная входной строкой, правильной поп-последовательностью. Например: если входная последовательность символов — dcba, возвращаемое значение — true, если входная последовательность символов — adbc, возвращаемое значение — false;
Простой стек:
общественный класс SqStack {
частный размер int;
данные частного объекта[];
частный int top;
общественный SqStack() {
это(50);
размер = 50;
}
общественный SqStack (размер int) {
this.size = размер;
данные = новый объект [размер];
верх = -1;
}
public void push (данные объекта) {
//...
}
общественный объект поп () {
//...
}
общедоступный объект getTop(){
//...
}
общедоступное логическое значение isEmpty(){
//...
}
}
public static boolean isStackOutSequence(String str){
SqStack s = новый SqStack();
for(int i=0;i<str.length();i++){
for(int j=i+1;j<str.length();j++){
если (str.charAt(j)<str.charAt(i)){
s.push(str.charAt(j));
}
while(!s.isEmpty(){
char c=(Character)s.pop();
if(!s.isEmpty()&&c>(Character)s.pop())
вернуть ложь;
}
}
вернуть истину;