Sabemos que la pila es un contenedor de datos que es el primero en entrar y el último en salir. Cuando la secuencia de entrada de una pila es una secuencia creciente (como a, b, c, d), y la operación de pila está permitida durante la operación de inserción, la secuencia de salida puede tener muchas formas (como: d, c, b , a o a, c, b, d, etc.). Pero definitivamente no habrá la siguiente secuencia pop: a, d, b, c o d, a, b, c, etc. Suponiendo que la secuencia de entrada es una secuencia creciente, escriba un algoritmo para determinar si la secuencia pop representada por la cadena de entrada es la secuencia pop correcta. Por ejemplo: si la secuencia de caracteres de entrada es dcba, el valor de retorno es verdadero; si la secuencia de caracteres de entrada es adbc, el valor de retorno es falso.
Una pila sencilla:
clase pública SqStack {
tamaño int privado;
datos de objeto privado [];
parte superior privada;
pila cuadrada pública(){
esto(50);
tamaño = 50;
}
SqStack público (tamaño int) {
this.size = tamaño;
datas = nuevo Objeto[tamaño];
arriba = -1;
}
push vacío público (datos del objeto) {
//...
}
objeto público pop(){
//...
}
objeto público getTop(){
//...
}
público booleano está vacío(){
//...
}
}
público estático booleano isStackOutSequence (String str) {
SqStack s=nuevo SqStack();
para(int i=0;i<str.length();i++){
for(int j=i+1;j<str.length();j++){
si(str.charAt(j)<str.charAt(i)){
s.push(str.charAt(j));
}
mientras(!s.isEmpty(){
char c=(Carácter)s.pop();
if(!s.isEmpty()&&c>(Carácter)s.pop())
devolver falso;
}
}
devolver verdadero;