Fila de prioridade

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1309 palavras )
  • Download(s) : 0
  • Publicado : 21 de abril de 2012
Ler documento completo
Amostra do texto
O que é Fila?
É um conjunto ordenado de itens a partir do qual podem-se eliminar itens em uma extremidade(inicio da fila) e adicionar itens na outra extremidade(fim da fila). Fila, diferentemente de pilha que usa o conceito de FILO(First-in, Last-out), usa o conceito FIFO(First-in, First-out), ou seja, o item ou elemento que entrar primeiro, obrigatoriamente, deve sair primeiro. Issoimpossibilita a exclusão/inserção de algum item no meio da fila, caracterizando essa estrutura de dado como uma Lista com Restrição de Acesso.
Em filas podem-se aplicar três operações primitivas:
* insert(q,x): insere item x no fim da fila q. Pode sempre ser executada, uma vez que que não há limites para o número de elementos que uma fila pode ter.
Exemplo:
INICIOFIM

A | D | C | F | B |
(q)

insert(q, A);
insert(q, D);
insert(q, C);
insert(q, F);
insert(q, B);

* x = remove(q): elimina o primeiro elemento da fila q e atribui o valor do item em x. Esta operação só pode ser aplicada se houver pelo menos um item na fila, ou seja, lista não vazia, pois não existe um método para remover um elementode uma fila sem elementos. O resultado da tentativa de exclusão/remoção de um elemento de uma fila vazia é chamado de underflow.
Exemplo:

Fila antes:
INICIO FIM

A | D | C | F | B |
(q)

x = remove(q);
x = remove(q);
x = remove(q);

Fila depois:
INICIO FIM

F | B | | | |(q)

* empty(q): retorna verdadeiro ou falso, dependendo se a fila estiver vazia ou não. Esta operação é sempre aplicável.
Conceito Fila com Prioridade
É uma estrutura de dado que a classificação intrínseca dos elementos determina os resultados de suas operações. Há dois tipos de filas com prioridade.
* Ascendente: itens podem ser inseridos arbitrariamente, mas só pode removido omenor item, ou seja, aquele que tiver a menor chave que sai primeiro. Se aqp for uma fila de prioridade ascendente, a operação de exclusão da fila pqmindelete(aqp) remove o menor item da fila e retorna seu valor.
Exemplo:

pqinsert(aqp,3);
pqinsert(aqp,4);
pqinsert(aqp,2);
INICIO FIM

2 | 3 | 4 | | |
(aqp)
X = pqmindelete(aqp);
X =pqmindelete(aqp);
INICIO FIM

4 | | | | |
(aqp)

* Descendente: segue a mesma linha de pensamento que fila de prioridade ascendente, só que ao invés de remover o menor elemento, se remove o maior ou aquele com a maior chave. A operação de exclusão pqmaxdelete(dqp) para fila de prioridade descendente dpq remove o maior elemento da fila e retorna seu valor.
Exemplo:pqinsert(dqp,3);
pqinsert(dqp,4);
pqinsert(dqp,2);
INICIO FIM

4 | 3 | 2 | | |
(dqp)
X = pqmaxdelete(dqp);
X = pqmaxdelete(dqp);
INICIO FIM

2 | | | | |
(dqp)

As operações pqinsert(apq,x) e pqinsert(dpq,x) são idênticas, em termos lógicos. A operação empty(pq) é aplicável a ambos tipos de fila deprioridade, pois determina se a fila está vazia ou não. As operações de remoção em ambos tipos de filas só são aplicáveis se a fila de prioridade não estiver vazia.
A operação de remoção pode ser aplicada em quanto houver elementos na fila de prioridade, por exemplo, aplicando a operação pqmindelete(apq) em uma fila de prioridade ascendente, a operação recuperará o menor elemento e aplicadanovamente, recuperara o próximo menor elemento, e assim por diante. Inserindo um elemento após uma sequência de remoções, e realizar de novo a operação de remoção, este elemento, no caso de fila de prioridade ascendente, for menor que todos que estão na lista, ele que será removido.
Exemplo:
Tendo a fila,
INICIO FIM

4 | 3 | 2 | 5...
tracking img