No blog anterior, introduzi a lista a seguir. A lista é a estrutura mais simples, mas se você deseja lidar com algumas estruturas mais complexas, a lista parece muito simples, por isso precisamos de alguma estrutura de dados semelhantes à lista, mas mais complexa - a pilha. A pilha é uma estrutura de dados eficiente, porque os dados só podem ser adicionados ou excluídos na parte superior da pilha; portanto, essa operação é muito rápida e fácil de implementar.
1: Operação na pilha.
Uma pilha é uma lista especial. Os elementos da pilha só podem ser acessados através de uma extremidade da lista, e essa extremidade é a parte superior da pilha. Por exemplo, ao lavar a louça em um restaurante, você só pode lavar o prato superior primeiro. Depois de lavar a louça, você só pode encaixar o topo da pilha de pratos. A pilha é chamada de estrutura de dados "tardio na primeira saída" (LIFO).
Como a pilha possui as características do back-in, o primeiro elemento que não está na parte superior da pilha não pode ser acessado. Para obter elementos com pilha baixa, o elemento acima deve ser removido primeiro. As duas operações principais que podemos fazer com a pilha são empurrar um elemento para a pilha e colocar um elemento na pilha. Ao entrar na pilha, podemos usar o método do método push () e, quando o colocamos, podemos usar o método pop (). Embora o método pop () possa acessar os elementos na parte superior da pilha, depois de chamar o método, os elementos na parte superior da pilha são excluídos permanentemente da pilha. Outro método que usamos é o Peek (), que retorna apenas o elemento superior da pilha sem excluí -la.
Os diagramas de coluna reais da entrada da pilha e a saída da pilha são os seguintes:
push (), pop () e Peek () são os três métodos principais da pilha, mas a pilha possui outros métodos e propriedades. do seguinte modo:
claro (): limpe todos os elementos na pilha.
comprimento (): registre o número de elementos na pilha.
Dois: A implementação da pilha é a seguinte:
Podemos começar implementando o método da classe de pilha primeiro; do seguinte modo:
A cópia do código é a seguinte:
function stack () {
this.datastore = [];
this.top = 0;
}
Como acima: o DataStore salva todos os elementos na pilha. A variável top registra a posição na parte superior da pilha e é inicializada para 0. Isso significa que a posição inicial da matriz correspondente na parte superior da pilha é 0, se algum elemento for empurrado para dentro da pilha. O valor dessa variável mudará de acordo.
Também temos os seguintes métodos: push (), pop (), peek (), clear (), comprimento ();
1. Método push (); Ao empurrar um novo elemento para a pilha, ele precisa ser salvo na matriz correspondente à parte superior variável e, em seguida, o valor superior é aumentado em 1, para que aponte para a próxima posição na matriz. O seguinte código:
A cópia do código é a seguinte:
função push (element) {
this.datastore [this.top ++] = elemento;
}
2. O método pop () é oposto ao método push () - retorna o elemento superior e deduz o valor superior em 1. O seguinte código:
A cópia do código é a seguinte:
função pop () {
retornar this.datastore [-this.top];
}
3. O método Peek () retorna o elemento na posição 1 top-1 da matriz, ou seja, o elemento 1 top-1 da pilha;
A cópia do código é a seguinte:
função peek () {
retornar this.datastore [this.top - 1];
}
4. Método de comprimento () Às vezes, precisamos saber quantos elementos existem na pilha. Podemos retornar o número de elementos na pilha retornando o valor superior variável, conforme mostrado no código a seguir:
A cópia do código é a seguinte:
função comprimento () {
retornar este.top;
}
5. Clear (); Às vezes, queremos limpar a pilha e definimos o valor superior da variável como 0; O seguinte código:
A cópia do código é a seguinte:
function clear () {
this.top = 0;
}
Todos os códigos abaixo:
A cópia do código é a seguinte:
function stack () {
this.datastore = [];
this.top = 0;
}
Stack.prototype = {
// Pressione um novo elemento na pilha
push: function (element) {
this.datastore [this.top ++] = elemento;
},
// Acesse o elemento superior da pilha, o elemento superior da pilha é excluído permanentemente
pop: function () {
retornar this.datastore [-this.top];
},
// retorna o elemento na posição Top-1 na matriz, ou seja, o elemento superior da pilha
Peek: function () {
retornar this.datastore [this.top - 1];
},
// quantos elementos são armazenados na pilha
comprimento: function () {
retornar este.top;
},
// Limpe a pilha
claro: function () {
this.top = 0;
}
};
Exemplos de demos são os seguintes:
var Stack = new Stack ();
Stack.push ("A");
Stack.push ("B");
Stack.push ("C");
console.log (Stack.Length ()); // 3
console.log (Stack.peek ()); // c
var pop = Stack.pop ();
console.log (estourado); // 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
Abaixo, podemos implementar uma definição recursiva de uma função fatorial; Por exemplo, 5! Fatorial 5! = 5 * 4 * 3 * 2 * 1;
O seguinte código:
A cópia do código é a seguinte:
Função da função (n) {
var s = new Stack ();
while (n> 1) {
s.push (n--);
}
var produto var = 1;
while (s.length ()> 0) {
produto *= s.pop ();
}
produto de retorno;
}
console.log (fato (5));
O código acima significa: Primeiro passe o número 5 para a função, use um loop de tempo e antes de diminuir 1 de cada vez, pressione () da função que você usa na pilha até que a variável n seja menor que 1. Em seguida, defina um produto variável; Determine se é maior que 0 pelo método LIMPE () da pilha e cada vez que o método do produto* = s.pop () é executado, o método POP () retorna o elemento superior da pilha e exclui o elemento da pilha. Portanto, cada vez que você executa, exclua um elemento até S.Length () <= 0. SO PRODUTO = 5*4*3*2*1. etc.