Wir wissen, dass der Stapel ein First-in-Last-out-Datencontainer ist. Wenn die Eingabesequenz eines Stapels eine aufsteigende Sequenz ist (z. B. a, b, c, d) und die Stapeloperation während der Push-Operation zulässig ist, kann die Ausgabesequenz viele Formen haben (z. B. d, c, b). , a oder a, c, b, d usw.). Aber die folgende Pop-Sequenz wird es definitiv nicht geben: a, d, b, c oder d, a, b, c usw. Unter der Annahme, dass die Eingabesequenz eine aufsteigende Sequenz ist, schreiben Sie bitte einen Algorithmus, um zu bestimmen, ob die durch die Eingabezeichenfolge dargestellte Popsequenz die richtige Popsequenz ist. Beispiel: Wenn die Eingabezeichenfolge dcba ist, ist der Rückgabewert wahr; wenn die Eingabezeichenfolge adbc ist, ist der Rückgabewert falsch.
Ein einfacher Stapel:
öffentliche Klasse SqStack {
private int-Größe;
private Object[]-Daten;
private int top;
öffentlicher SqStack(){
dies(50);
Größe = 50;
}
public SqStack(int size) {
this.size = Größe;
datas = neues Objekt[Größe];
oben = -1;
}
public void push(Objektdaten){
//......
}
öffentliches Objekt pop(){
//......
}
öffentliches Objekt getTop(){
//......
}
öffentlicher boolescher Wert isEmpty(){
//......
}
}
öffentlicher statischer boolescher Wert isStackOutSequence(String str){
SqStack s=new 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=(Charakter)s.pop();
if(!s.isEmpty()&&c>(Character)s.pop())
return false;
}
}
return true;