Sabemos que a pilha é um contêiner de dados do tipo primeiro a entrar e último a sair. Quando a sequência de entrada de uma pilha é uma sequência crescente (como a, b, c, d), e a operação de pilha é permitida durante a operação push, a sequência de saída pode ter vários formatos (como: d, c, b , a ou a, c, b, d, etc.). Mas definitivamente não haverá a seguinte sequência pop: a, d, b, c ou d, a, b, c, etc. Supondo que a sequência de entrada seja uma sequência crescente, escreva um algoritmo para determinar se a sequência pop representada pela string de entrada é a sequência pop correta. Por exemplo: se a sequência de caracteres de entrada for dcba, o valor de retorno será verdadeiro; se a sequência de caracteres de entrada for adbc, o valor de retorno será falso.
Uma pilha simples:
classe pública SqStack {
tamanho interno privado;
dados de objeto privado[];
privado int superior;
públicoSqStack(){
isto(50);
tamanho = 50;
}
public SqStack(tamanho interno) {
este.tamanho = tamanho;
dados = novo objeto[tamanho];
topo = -1;
}
public void push(dados do objeto){
//...
}
objeto público pop(){
//...
}
objeto público getTop(){
//...
}
booleano público isEmpty(){
//...
}
}
público estático booleano isStackOutSequence(String str){
SqStack s = novo SqStack();
for(int i=0;i<str.length();i++){
for(int j=i+1;j<str.length();j++){
if(str.charAt(j)<str.charAt(i)){
s.push(str.charAt(j));
}
while(!s.isEmpty(){
char c=(personagem)s.pop();
if(!s.isEmpty()&&c>(Caracter)s.pop())
retornar falso;
}
}
retornar verdadeiro;