Nous savons que la pile est un conteneur de données premier entré, dernier sorti. Lorsque la séquence d'entrée d'une pile est une séquence croissante (telle que a, b, c, d) et que l'opération de pile est autorisée pendant l'opération de poussée, la séquence de sortie peut avoir plusieurs formes (telles que : d, c, b , a ou a, c, b, d, etc.). Mais il n’y aura certainement pas la séquence pop suivante : a, d, b, c ou d, a, b, c, etc. En supposant que la séquence d'entrée est une séquence croissante, veuillez écrire un algorithme pour déterminer si la séquence pop représentée par la chaîne d'entrée est la séquence pop correcte. Par exemple : si la séquence de caractères d'entrée est dcba, la valeur de retour est vraie ; si la séquence de caractères d'entrée est adbc, la valeur de retour est fausse.
Une pile simple :
classe publique SqStack {
taille entière privée ;
données privées Object[] ;
haut int privé ;
public SqStack(){
ceci(50);
taille = 50 ;
}
public SqStack (taille int) {
this.size = taille ;
datas = nouvel objet[taille] ;
haut = -1 ;
}
public void push (données d'objet) {
//...
}
Objet public pop(){
//...
}
Objet public getTop(){
//...
}
public booléen isEmpty(){
//...
}
}
public statique booléen isStackOutSequence(String str){
SqStack s=nouveau SqStack();
pour(int i=0;i<str.length();i++){
pour(int j=i+1;j<str.length();j++){
si(str.charAt(j)<str.charAt(i)){
s.push(str.charAt(j));
}
while(!s.isEmpty(){
char c=(Caractère)s.pop();
if(!s.isEmpty()&&c>(Character)s.pop())
renvoie faux ;
}
}
renvoie vrai ;