En el blog anterior, presenté la siguiente lista. La lista es la estructura más simple, pero si desea lidiar con algunas estructuras más complejas, la lista parece demasiado simple, por lo que necesitamos alguna estructura de datos similar a la lista pero más compleja: la pila. La pila es una estructura de datos eficiente, porque los datos solo se pueden agregar o eliminar en la parte superior de la pila, por lo que esta operación es muy rápida y fácil de implementar.
1: Operación en la pila.
Una pila es una lista especial. Los elementos en la pila solo se pueden acceder a través de un extremo de la lista, y este final es la parte superior de la pila. Por ejemplo, al lavar los platos en un restaurante, solo puede lavar el plato superior primero. Después de lavar los platos, solo puedes asaltar la parte superior de la pila de platos. La pila se denomina estructura de datos "al final de la salida" (LIFO).
Dado que la pila tiene las características de invertir, primero, no se puede acceder a ningún elemento que no esté en la parte superior de la pila. Para obtener elementos con pila baja, el elemento anterior debe eliminarse primero. Las dos operaciones principales que podemos hacer con la pila son empujar un elemento a la pila y colocar un elemento en la pila. Al ingresar a la pila, podemos usar el método Push () del método, y cuando lo ponemos, podemos usar el método pop (). Aunque el método pop () puede acceder a los elementos en la parte superior de la pila, después de llamar al método, los elementos en la parte superior de la pila se eliminan permanentemente de la pila. Otro método que usamos es Peek (), que devuelve solo el elemento superior de la pila sin eliminarlo.
Los diagramas de columna reales de entrada de pila y salida de pila son los siguientes:
Push (), Pop () y Peek () son los tres métodos principales de la pila, pero la pila tiene otros métodos y propiedades. como sigue:
Clear (): Borre todos los elementos en la pila.
Longitud (): Registre el número de elementos en la pila.
Dos: la implementación de la pila es la siguiente:
Podemos comenzar implementando primero el método de clase de pila; como sigue:
La copia del código es la siguiente:
function stack () {
this.datastore = [];
this.top = 0;
}
Como se indicó anteriormente: DataStore guarda todos los elementos en la pila. La variable superior registra la posición en la parte superior de la pila y se inicializa a 0. Significa que la posición inicial de la matriz correspondiente en la parte superior de la pila es 0, si algún elemento se empuja a la pila. El valor de esta variable cambiará en consecuencia.
También tenemos los siguientes métodos: push (), pop (), peek (), clear (), longitud ();
1. Método Push (); Al empujar un nuevo elemento a la pila, debe guardarlo en la matriz correspondiente a la parte superior variable, y luego el valor superior aumenta en 1, de modo que apunta a la siguiente posición en la matriz. El siguiente código:
La copia del código es la siguiente:
función push (elemento) {
this.datastore [this.top ++] = elemento;
}
2. El método pop () es opuesto al método push (): devuelve el elemento superior y deduce el valor superior por 1. El siguiente código:
La copia del código es la siguiente:
función pop () {
devuelve this.datastore [-this.top];
}
3. El método PEEK () devuelve el elemento en la posición superior-1 de la matriz, es decir, el elemento TOP-1 de la pila;
La copia del código es la siguiente:
function peek () {
devuelve this.datastore [this.top - 1];
}
4. Método de longitud () A veces necesitamos saber cuántos elementos hay en la pila. Podemos devolver el número de elementos en la pila devolviendo el valor superior de la variable, como se muestra en el siguiente código:
La copia del código es la siguiente:
longitud de función () {
devolver esto.top;
}
5. Claro (); A veces queremos borrar la pila, y establecemos el valor superior de la variable en 0; el siguiente código:
La copia del código es la siguiente:
función clear () {
this.top = 0;
}
Todos los códigos a continuación:
La copia del código es la siguiente:
function stack () {
this.datastore = [];
this.top = 0;
}
Stack.prototype = {
// presione un nuevo elemento en la pila
push: function (elemento) {
this.datastore [this.top ++] = elemento;
},
// Acceda al elemento superior de la pila, el elemento superior de la pila se elimina permanentemente
pop: function () {
devuelve this.datastore [-this.top];
},
// Devuelve el elemento en la posición Top-1 en la matriz, es decir, el elemento superior de la pila
peek: function () {
devuelve this.datastore [this.top - 1];
},
// cuántos elementos se almacenan en la pila
longitud: function () {
devolver esto.top;
},
// borrar la pila
claro: function () {
this.top = 0;
}
};
Los ejemplos de demostraciones son los siguientes:
Var Stack = new Stack ();
stack.push ("a");
stack.push ("b");
stack.push ("c");
console.log (stack.length ()); // 3
console.log (stack.peek ()); // C
var popped = stack.pop ();
console.log (estampado); // C
console.log (stack.peek ()); // b
stack.push ("d");
console.log (stack.peek ()); // d
stack.clear ();
console.log (stack.length ()); // 0
console.log (stack.peek ()); // indefinido
A continuación podemos implementar una definición recursiva de una función factorial; Por ejemplo, 5! Factorial 5! = 5 * 4 * 3 * 2 * 1;
El siguiente código:
La copia del código es la siguiente:
Hecho de la función (n) {
var s = nuevo stack ();
while (n> 1) {
s.push (n--);
}
Producto var = 1;
while (s.length ()> 0) {
producto *= s.pop ();
}
producto de devolución;
}
console.log (hecho (5));
El código anterior significa: Primero pase el número 5 a la función, use un bucle de tiempo y antes de disminuir 1 cada vez, presione () de la función que usa a la pila hasta que la variable N sea inferior a 1. Luego defina un producto variable; Determine si es mayor que 0 por el método de longitud () de la pila, y cada vez que se ejecuta el producto* = s.pop (), el método pop () devuelve el elemento superior de la pila y elimina el elemento de la pila. Entonces, cada vez que ejecute, elimine un elemento hasta que s.length () <= 0. entonces producto = 5*4*3*2*1. etc.