우리는 스택이 먼저 들어오고 나중에 나오는 데이터 컨테이너라는 것을 알고 있습니다. 스택의 입력 시퀀스가 증가 시퀀스(예: 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 {
개인 정수 크기;
개인 Object[] 데이터;
개인 정수 상단;
공개 SqStack(){
이(50);
크기 = 50;
}
공개 SqStack(정수 크기) {
this.size = 크기;
데이터 = 새 객체[크기];
상단 = -1;
}
public void push(객체 데이터){
//...
}
공개 객체 팝(){
//...
}
공개 객체 getTop(){
//...
}
공개 부울 isEmpty(){
//...
}
}
공개 정적 부울 isStackOutSequence(String str){
SqStack s=새 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));
}
동안(!s.isEmpty(){
char c=(문자)s.pop();
if(!s.isEmpty()&&c>(문자)s.pop())
거짓을 반환;
}
}
사실을 반환;