Pilha e Fila

Introdução

Com base nos conceitos introdutórios de array e lista, podemos derivar desses conjuntos outros modelos de estruturas de dados, como pilha e fila. Tais modelos são parecidos em alguns aspectos mas divergem em outros. Nesse artigo pretendo mostrá-los, bem como a diferença de cada um, os casos de uso e um código para exemplificar o tipo pilha.

Pilha

Pilha é uma estrutura de dados simples. Sua principal ideia é que os elementos sejam acessados a partir do topo, assim, a cada inserção, o novo elemento passa a ser o topo e só temos acesso a ele. Dessa forma, os elementos de uma pilha são retirados na ordem inversa a que foram inseridos: o primeiro que sai é o último que entrou (LIFO - Last in, first out). Sua implementação pode ser um vetor, se tivermos a informação do número de elementos que serão armazenados, caso contrário, usa-se uma lista encadeada.

Fila

A fila é outra estrutura de dados que possui regras para inserção ou deleção. Nela, é possível inserir elementos no final da fila e retirar do início desta (FIFO - First in, first out). Assim como a pilha, a fila pode ser implementada como um vetor ou como uma lista encadeada, a partir da informação da quantidade de elementos que irão conter.

Diferença entre pilha e fila

A principal diferença entre essas estruturas se dá pela forma como são inseridos e removidos os dados. A pilha é uma estrutura LIFO (Last in, first out), isso significa que o primeiro elemento a entrar é o último a sair, o que acontece de forma contrária na fila, que é FIFO (first in, first out), em que o primeiro elemento a entrar em uma fila obrigatoriamente também será o primeiro a sair.

Casos de uso de pilha e fila

Pilha: Mecanismo de desfazer/refazer de um editor de texto. Quando é feito um comando de desfazer algo em um texto, esse elemento desfeito fica guardado no topo de uma pilha, jogando os outros comandos para baixo, de modo que ao acionar o comando de refazer, ele busca tal elemento que está no topo da fila para ser refeito. Assim, o último que entrou é o primeiro a sair.

Fila: Controle de páginas para impressão. Quando imprime-se um documento com 100 páginas, é possível perceber que essa impressão é feita na ordem das páginas, ou seja, de 1 ao 100, sendo a primeira página do documento o começo da impressão. Nesse sentido, é aplicado o conceito de primeiro a entrar e primeiro a sair.

Implementação de uma pilha em código JavaScript

Esse pequeno trecho de código simboliza uma pilha e as principais operações feitas nela. Os elementos inseridos na pilha dentro da iteração foram colocados um após o outro, sendo o número 10 o último desses elementos. Quando foram chamadas as funções de remoção, percebe-se a partir da representação final que os elementos foram removidos a partir do último adicionado, assim aplicando os conceitos de uma pilha.

Conclusão

Pilha e fila são duas estruturas de dados interessantes que possuem conceitos simples de entender. Seu entendimento é facilmente obtido partindo de analogias que podem ser feitas com conceitos na vida real. Uma fila de um banco com pessoas que chegam primeiro e saindo primeiro ou uma pilha de pratos que são removidos começando pelo último adicionado são alguns dos exemplos que possibilitam essa compreensão. Dentro da computação, seus usos são amplamente feito sendo aplicado em vários conceitos.