スタックは先入れ後出しのデータ コンテナーであることがわかっています。スタックの入力シーケンスが増加シーケンス (a、b、c、d など) であり、プッシュ操作中にスタック操作が許可されている場合、出力シーケンスはさまざまな形式 (d、c、b など) を持つ可能性があります。 、a または a、c、b、d など）。しかし、次のようなポップ シーケンスは絶対に存在しません: a、d、b、c または d、a、b、c など。入力シーケンスが増加シーケンスであるという仮定の下で、入力文字列によって表されるポップ シーケンスが正しいポップ シーケンスであるかどうかを判断するアルゴリズムを作成してください。たとえば、入力文字シーケンスが dcba の場合、戻り値は true になり、入力文字シーケンスが adbc の場合、戻り値は false になります。
単純なスタック:
パブリック クラス SqStack {
プライベート int サイズ;
プライベート Object[] データ。
プライベート int トップ;
public SqStack(){
これ(50);
サイズ = 50;
}
public SqStack(int サイズ) {
this.size = サイズ;
データ = 新しいオブジェクト[サイズ];
トップ = -1;
}
public void Push(オブジェクトデータ){
//...
}
パブリックオブジェクトpop(){
//...
}
パブリック オブジェクト getTop(){
//...
}
パブリックブール値 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=(キャラクター)s.pop();
if(!s.isEmpty()&&c>(キャラクター)s.pop())
false を返します。
}
}
true を返します。