terça-feira, 14 de julho de 2015

Algoritmos - Pilhas e Filas

Estruturas básicas de dados, como pilhas e filas são usadas em uma grande quantidade de aplicações. O uso adequado das estruturas de dados é que faz a diferença entre algoritmos eficientes e e ineficientes.

Pilhas - LIFO (Last In First Out)

Do mesmo contexto de pilha, é um conjunto de objetos que são inseridos e removidos de acordo com o princípio descrito no título (o último a entrar é o primeiro a sair). Objetos podem ser inseridos em uma pilha a qualquer momento, mas apenas o que foi inserido mais recentemente pode ser removido. 

O nome "pilha" é derivado da metáfora de pilha de pratos de um dispositivo automático de entrega de pratos de uma lanchonete. Neste caso, as operações fundamentais envolvem empilhar() e desempilhar() pratos da pilha.

Exemplo prático: Navegadores para Internet armazenam endereços dos locais recentemente visitados em uma pilha. Cada vez que o usuário visita uma nova página, seu endereço é "empilhado" na pilha de endereços. A partir de então, o navegador permite que o usuário "desempilhe" os endereços usando o botão "voltar", retornando a páginas previamente visitadas.

Filas - FIFO (First In First Out)

Consiste em um conjunto de objetos que são inseridos e removidos de acordo com o princípio descrito no título (o primeiro que entra é o primeiro que sai). Ou seja, os elementos podem ser inseridos a qualquer momento, mas apenas o elemento que está a mais tempo na fila pode ser removido. Normalmente dizemos que os elementos entram na fila pelo fim e são removidos pela frente.


Fonte (livro): Projeto de Algoritmos: Fundamentos, análise e exemplos da internet. Michael T. Goodrich e Roberto Tamassia.

Nenhum comentário:

Postar um comentário