我們知道棧是一種先進後出的資料容器。當一個堆疊的輸入序列是遞增序列(例如a,b,c,d),並且在進棧操作時,允許退棧操作,則輸出的序列可能有多種形式(例如:d,c,b, a或a,c,b,d等)。但卻肯定不會出現如下出棧序列:a,d,b,c或d,a,b,c等。在輸入序列為遞增序列的假設下,請寫一個演算法判斷輸入的字串表示的出棧序列是否為正確的出棧序列。例如:輸入的字元序列為dcba,則傳回值為true;若輸入的字元序列為adbc,則傳回的值為false。
一個簡單的堆疊:
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;