Implementando um Pilha com JavaScript

Olá pessoal! Neste artigo vou falar de um assunto que está presente nos primeiros semestre de quase todos os cursos superiores da área de TI, estrutura de dados, mais precisamente sobre pilha. Vou apresentar uma simples aplicação em JavaScript que demonstra o funcionamento de uma pilha.

Estrutura de Dados

Algoritmos manipulam dados, quando estes dados estão organizados (dispostos) de forma coerente caracterizam uma estrutura de dados. Estruturas de dados e algoritmos são cadeiras fundamentais de cursos como ciência da computação, sendo utilizados nas mais diversas áreas e com os mais diferentes propósitos.

A organização e os métodos que manipulam determinada estrutura que lhe conferem singularidade. A escolha de uma estrutura de dados apropriada pode tornar um problema complicado em um de solução trivial. O estudo das estruturas de dados está em constante desenvolvimento (assim como o de algoritmos), apesar disso existem estruturas clássicas que têm se mostrado padrões.

Pilha

A forma mais geral de uma lista permite a inserção ou eliminação de um elemento em qualquer posição na lista. Se restringirmos a ocorrência de inserção e eliminação a uma extremidade da lista, por exemplo, extremidades superiores, então temos uma estrutura de dados chamada de pilha.

Utilizando a terminologia de pilhas, operações de inserção e eliminação são comumente citadas como operações "push" e "pop", respectivamente. O único elemento diretamente acessível de uma pilha é seu elemento superior. O elemento menos acessível é seu elemento inferior.

Desde que as operações de inserção e eliminação são executadas na mesma extremidade da pilha (por exemplo, na extremidade superior), os elementos podem ser removidos somente na ordem oposta a que foram inseridos.

Um exemplo comum de pilha, que permite a seleção de seu elemento superior, é a pilha de pratos num restaurante. Os pratos em pilha fazem com que a pessoa tenha acesso ao prato superior, a remoção de um prato superior faz com que a pessoa tenha acesso ao próximo prato, se colocado um novo prato na pilha, esse será o primeiro a sair, como mostra a figura abaixo.

As duas operações mais comuns associadas a uma pilha são:

Push: insere um elemento NOVO no alto da pilha.
Pop: retira o elemento superior da pilha

Então vamos ao que interessa.

Aplicação

A página abaixo é a página que terá todas as funções JavaScript apresentadas a seguir e os componentes do formulário. A DIV chamada de conteúdo é utilizada para mostrar todas as informações sobre a pilha, informações essas que serão geradas por uma função JavaScript chamada "mostrarPilha()".

O componente hidden com nome de "pilha" armazenará todos os elementos da pilha separados por ponto-e-vírgula. O componente chamado de "elemento" é uma caixa de texto para escrever o elemento que deseja inserir na pilha. Os botões "Inserir" e "Retirar" servem respectivamente para adicionar um novo elemento e excluir o elemento superior da pilha.

Este interessante fenômeno é conhecido como LIFO. LIFO é um acrônimo para a expressão inglesa Last In, First Out que, em português significa último a entrar, primeiro a sair e será observado na aplicação a ser discutida logo a seguir. A função apresentada a seguir, está presente no método onFocus() da tag body da pagina apresentada acima. Essa função apenas limpa e seta o componente "elemento" sempre a pagina atualizar, ou seja, sempre que o usuário clicar em "inserir" ou "retirar" elemento da pilha.

Na linha 3 da próxima figura é declarada uma variável qtdElementos que indica o elemento superior da pilha. Para uma pilha vazia, a variável qtdElementos tem valor zero. A variável é incrementada de "um" quando se introduz um novo elemento na pilha e é diminuído de "um" toda vez que um elemento é eliminado da pilha. O primeiro passo do algoritmo é verificar a ocorrência de uma situação de estouro de capacidade. A função "estouro_pilha()" verifica se a pilha está vazia quando se quer eliminar um elemento, ou verifica se a pilha está cheia, quando se quer inserir um novo elemento. Caso algum desses testes for verdadeiro a função retornara falso e um aviso aparece pro usuário, no nosso caso a pilha estará cheia quando o valor de qtdElementos for igual a 10. A função "estouro_pilha()" será chamada sempre quando as duas outras funções "popElemento()" e "pushElemento()" forem chamadas.

A função "verificaPontoVirgula()" apresentada abaixo será utilizada na chamada da função "pushElemento()". Esta função verifica a existência do caractere ponto-e-vírgula no valor digitado pelo usuário. Se o usuário digita ponto-e-vírgula no campo, o aplicativo vai entender que são dois elementos e não um.

A função abaixo "pushElemento()" é chamada quando o usuário clicar no botão "Inserir". O primeiro teste é chamar a função "estouro_pilha" para verificar se a operação pode ser realizada, a função já foi apresentada anteriormente.

O segundo teste verifica se o valor digitado contem ponto-e-vírgula chamando a função "verificaPontoVirgula()", se tiver ponto-e-vírgula a função retornará falsa.

O terceiro teste é pra verificar se é o primeiro elemento da pilha. O componente "pilha" ira armazenar todos os elementos da pilha separados por ponto-e-vírgula, como por exemplo: "7;3;9;2;6". O primeiro elemento armazenara na pilha sem o ponto-e-vírgula, como por exemplo: "7", a partir do segundo elemento, será realizado uma concatenação, e ficaria assim: "7;3".

Depois de inserido o elemento, a variável qtdElementos é incrementado de "um" e chama a função "mostrarPilha()" que será apresenta mais adiante.

A função abaixo "popElemento()" é chamada quando o usuário clicar no botão "Retirar". O primeiro teste é chamar a função "estouro_pilha()" para verificar se a operação pode ser realizada.

É criada então uma variável na linha 6 chamada de "str" que recebe o valor do componente "pilha", depois é criado um array chamado "pilha" na linha 7, esse array recebe da variável "str" criada na linha 6, pegando os elementos separados por ponto-e-vírgula.

Depois é realizado um FOR percorrendo todos os elementos do array até o ultimo elemento menos "um", esse ultimo elemento ficará de fora, será retirado da pilha. No final a variável qtdElemento é diminuído de "um" e chamada a função "mostrarPilha()".

A ultima função a ser apresentada é a "mostrarPilha()", essa função vai mostrar todos os elementos armazenados na pilha.

É criada uma variável na linha 4 chamada "str" que recebe o componente pilha com todos os elementos separados por ponto-e-vírgula.

Na linha 5 é criada outra variável chamada "retorno". O conteúdo da variável retorno consiste de uma linha com a informação de quantos elementos estão na pilha, depois é apresentado uma tabela com duas linhas e 11 colunas. Na linha "um" é mostrado a posição de 1 a 10 e na linha "dois" é mostrado os elementos que estão em cada posição.

No fim da função, a variável de retorno é passada para a DIV conteúdo apresentada no inicio desse artigo.

Clique aqui para fazer o downloads do arquivo.

Espero que tenham gostado um abraço a todos e até a próxima!

Bibliografia

TREMBLAY Jean-Paul & BUNT Richard B. Ciência dos computadores. Makron Books, São Paulo.

Desenvolvimento - Javascript

Leia também