Com estes importantes métodos explicados, vamos dar uma olhada no que a implementação final da nossa classe de Pilha:
push e pop métodos aparecer exatamente como esperamos (lines13–32). Podemos usar o nosso método push para criar um inicializador personalizado com alguns valores variádicos (linhas 7-11). Além disso, podemos verificar uma pilha vazia, verificando se o nosso rootNode tem um valor (linhas 34-36) e tem um método básico de impressão que itera através da nossa lista, desde que seja capaz de aceder aos nós através da próxima propriedade (linhas 38-44).
Um teste básico de nossa pilha de funcionalidade parece que este:
Saber como implementar uma pilha é uma coisa, mas ainda mais importante é o reconhecimento de situações para as quais uma pilha é bem adequado. Nesta próxima secção analisaremos três desses casos.Caso De Utilização 1: Ordem inversa
porque a ordem de uma pilha é fixa, ordem inversa pode ser alcançada muito facilmente por estourar elementos de uma pilha e imediatamente para outra. Nada de mexer nos índices de troca!
caso de uso 2: Testar a simetria
outro bom caso de uso para pilhas é testar a simetria. No exemplo abaixo, estamos testando uma cadeia de parênteses para garantir que cada bracket de Fecho é a contraparte correta de um bracket de abertura anterior.
começamos por verificar que a contagem de caracteres é divisível por dois, uma vez que um número ímpar de caracteres seria imediatamente assimétrico (linha 6). Em seguida, verificamos que temos entrada válida, definindo um conjunto de caracteres ilegais e, em seguida, verificando que a nossa string de entrada tem uma gama nula de caracteres ilegais (linhas 7-8). Para verificar os nossos parêntesis de fecho e abertura são uma correspondência, nós colocá-los em um dicionário como pares chave-valor (linha 10). Em outras situações você pode ser capaz de calcular o valor inverso sem ter que armazenar pares em um dicionário. Depois temos a nossa pilha (linha 11). O propósito da nossa pilha neste caso é armazenar Suportes de abertura. À medida que iteramos através de nossa String podemos verificar se nosso personagem é um suporte de abertura testando se é uma chave em nosso dicionário. Se for, empurramo-lo para a nossa pilha. Assim que encontrarmos o nosso primeiro suporte fechado, sabemos que estamos a trabalhar na segunda metade do nosso padrão, por isso ajustamos o nosso primeiro booleano para falso (linha 12). Se encontrarmos mais Suportes de abertura depois deste ponto, podemos verificar o booleano e indicar um teste falhado. Para cada bracket de Fecho, nós saltamos o último bracket de abertura e verificar se eles são um par de chave-valor correto. Mais uma vez, só precisamos iterar através da cadeia uma vez, então estamos recebendo muito valor de um algoritmo linear.
usar o caso 3: desfazer os comandos
finalmente, vamos usar uma pilha em conjunto com o padrão de comandos, para criar um histórico de desfazer. Para começar, vamos dar uma olhada em um simples objeto de conta bancária. Tem um saldo e um limite de descoberto e alguns métodos simples de depósito e retirada de fundos:
em vez de chamar os métodos de depósito e levantamento diretamente, podemos armazenar as informações relevantes em um comando. No excerto abaixo, especificamos que tipo de ação queremos realizar com uma propriedade do enum (depósito ou levantamento) e uma quantia . Também armazenamos um booleano para indicar se o comando foi capaz de ser executado (linhas 4-11). Observe que se o pedido de retirada exceder o limite de descoberto, nada acontecerá à conta bancária e o booleano sucedido permanecerá falso, caso contrário, tornar-se-á verdadeiro uma vez que o comando tenha concluído (linhas 18-26). Temos dois métodos para invocar ou anular o comando, cada um tendo uma conta bancária como argumento (linhas 18 & 28). Estes métodos levam a conta bancária e chamam os seus métodos de instância que vimos no trecho anterior.
voltando à conta bancária, podemos agora introduzir a nossa propriedade de comando, que foi inicializada com o nosso tipo de conta bancária (linha 47). Marcamos os nossos métodos de depósito e levantamento como filtragem para que eles só possam ser acessados pelo nosso BankAccountCommand (linhas 62 & 66). Agora temos dois métodos expostos: process (comando:) e undoLastCommand (). O primeiro aceita um comando como uma entrada, executa-o com a conta bancária como a entrada, e, em seguida, empurra o comando para a pilha. Enquanto isso, o método undoLastCommand, remove o último comando da pilha e executa um desfazer (linhas 51-60).
este é um padrão muito simples, e um que é muito poderoso. As aplicações possíveis são infinitas e fazem para uma experiência de usuário satisfatória.
E agora vamos ver o padrão em ação:
Enrole
neste artigo, exploramos o conceito de uma pilha LIFO comportamento. Nós implementamos nossa própria pilha usando uma lista duplamente ligada e demonstramos como ela aloca e desaloca a memória à medida que o tamanho da pilha muda. Nós também olhamos para três casos de uso comum para pilhas: inversão, teste de simetria e ruína. Cada uma destas três situações aparece inúmeras vezes em projetos do mundo real. Espero que pensem numa pilha como uma estrutura adequada para lidar com essas necessidades. Como sempre, obrigado por ler!