next up previous contents
Next: Manipulação de listas em Up: Listas ligadas Previous: Manipulação de lista   Sumário

Filas e pilhas

Filas e pilhas são estruturas usualmente implementadas através de listas, retringindo a política de manipulação dos elementos da lista.

Uma fila (queue) tipicamente estabelece uma política FIFO -- first in, first out -- de acesso aos dados. Em outras palavras, a ordem estabelecida na lista é a ordem de inserção. No momento de retirar um nó da lista, o nó mais antigo (o primeiro que entrou) é o primeiro a ser retirado.

Como as políticas de inserção e remoção são pré-definidas, para esse tipo de estrutura as operações são descritas de forma genérica, INSERT e REMOVE. Há duas possibilidades para implementar as operações de uma fila usando os procedimentos descritos para listas:

  1. restringir a inserção ao procedimento INSERT e a remoção ao procedimento REMOVELAST, ou

  2. restringir a inserção ao procedimento APPEND e a remoção ao procedimento REMOVEFIRST.

Uma estrutura de pilha (stack), por outro lado, estabelece uma política LIFO -- last in, first out. Uma estrutura de pilha também oferece basicamente duas operações de manipulação, PUSH, para inserção no topo da pilha, e POP, para retirada do topo da pilha.

Embora também fosse possível implementar uma pilha através de lista usando os procedimentos que acrescentam e removem os nós no final da lista, por razões óbvias de desempenho uma pilha é usualmente implementada usando os procedimentos INSERT e REMOVEFIRST, que não requerem a varredura da lista para estabelecer essa política de manipulação de dados.


next up previous contents
Next: Manipulação de listas em Up: Listas ligadas Previous: Manipulação de lista   Sumário
Ivan L. M. Ricarte 2003-02-14