We know that the stack is a first-in, last-out data container. When the input sequence of a stack is an increasing sequence (such as a, b, c, d), and the stack operation is allowed during the push operation, the output sequence may have many forms (such as: d, c, b, a or a, c, b, d, etc.). But there will definitely not be the following pop sequence: a, d, b, c or d, a, b, c, etc. Under the assumption that the input sequence is an increasing sequence, please write an algorithm to determine whether the pop sequence represented by the input string is the correct pop sequence. For example: if the input character sequence is dcba, the return value is true; if the input character sequence is adbc, the return value is false.
A simple stack:
public class SqStack {
private int size;
private Object[] datas;
private int top;
public SqStack(){
this(50);
size = 50;
}
public SqStack(int size) {
this.size = size;
datas = new Object[size];
top = -1;
}
public void push(Object data){
//...
}
public Object pop(){
//...
}
public Object getTop(){
//...
}
public boolean isEmpty(){
//...
}
}
public static boolean 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=(Character)s.pop();
if(!s.isEmpty()&&c>(Character)s.pop())
return false;
}
}
return true;