• Fila Dinâmica com Prioridade
    (FIFO)

  • INFO:
  • Prioridade:

  • HUB

  • 1/1

Informações da Estrutura
Estrutura de Dados

NoFila

{

  proximo : NoFila;

  info : String;

  prioridade : inteiro;

}

EstruturaFila

{

  inicio : NoFila;

  fim : NoFila;

}

Descrição
"Uma fila é um conjunto ordenado de itens a partir do qual podem-se eliminar itens numa extremidade (chamada início da fila) e no qual podem-se inserir itens na outra extremidade (chamada fim da fila)."
"A fila de prioridade é uma estrutura de dados na qual a classificação intrínseca dos elementos determina os resultados de suas operações básicas." (Tenenbaum)

Mais informações
Implementação: Realizada por meio de uma lista encadeada de registros (em C, struct), onde cada elemento é inserido ordenadamente por meio do campo que classifica sua prioridade.

Regras: Dependendo da aplicação o elemento com maior prioridade deve sair primeiro, e quando dois elementos possui a mesma prioridade, respeita-se a regra da fila (FIFO), o primeiro a entrar é o primeiro a sair.

Aplicação: Utilizado em algoritmos de busca em Grafos, sistemas distribuídos, operações internas de sistemas operacionais, algoritmos de política de cache, entre outros.

Requisitos para aplicação: A aplicação não envolve recuperação de elementos diferentes do primeiro que foi inserido, e deve existir uma relação entre cada valor que o campo de prioridade do elemento pode representar, ou seja, deve ser possível determinar se um elemento possui maior ou menor (ou igual) que outro elemento.

Em relação a outras formas de implementação de Fila
  • Vantagem: Armazena somente o número necessário de elementos.
  • Desvantagem: Mais complexa de ser implementada.
FUNÇÃO
Insere ou Enqueue(INFO,Prioridade)

novo,leitor,anterior : NoFila;

novo := alocar();

novo.info := INFO;

novo.prioridade := Prioridade;

novo.proximo := nulo;

leitor := Fila.inicio;

 

Enquanto leitor != nulo e leitor.prioridade >= PRIORIDADE então

INICIO

anterior := leitor;

leitor := leitor.proximo;

FIM

 

Se leitor != nulo então

INICIO

Se anterior == nulo então

INICIO

novo.proximo := Fila.inicio;

Fila.inicio := novo;

FIM

Senão

INICIO

novo.proximo := leitor;

anterior.proximo := novo;

FIM

FIM

Senão

INICIO

Se anterior == nulo então

Fila.inicio := novo;

Senão

Fila.fim.proximo := novo;

Fila.fim := novo;

FIM

FUNÇÃO
Remove() ou Dequeue() ou Shift()
RETORNA
Retorna a primeira posição

Se Fila.fim != nulo então

INICIO

rem,retorno : NoFila;

rem := Fila.inicio;

retorno := Fila.inicio.info;

Fila.inicio := Fila.inicio.proximo;

 

Se Fila.inicio == nulo então

Fila.fim := nulo

 

Liberar(rem);

Retornar retorno;

FIM

Retornar nulo;

FUNÇÃO
Busca(INFO)
RETORNA
Retorna a posição de saída

leitor : NoFila;

posicao : inteiro;

leitor := Fila.ini;

posicao := 0;

 

Enquanto leitor != null então

INICIO

Se leitor.info == INFO então

Retornar posicao;

leitor := leitor.proximo;

posicao := posicao + 1;

FIM

Retornar -1;

Última animação

Nenhuma animação disponível para revisar!

Executando animação ...

Aguarde encerrar !

Última animação que foi executada:

# Descrição
Entradas Programadas

Configurações

Entradas

Limpar entrada ao final da animação

Chance de gerar número negativo na entrada aleatória:

50%

Estrutura

Ocultar Ponteiros Nulos

Impedir inserção de valores repetidos

Mostrar Descritores

Cor do componente primário

Cor do componente secundário

Código

Usar delimitador em chaves

Contar linhas brancas

Configurações serão salvas para este navegador
Histórico
    • #
    • INFO
    • Vazio
Principal
Menu das Estruturas

  • Pseudo-código

  • Informações da Estrutura

  • Entradas Programadas

  • Rever Passos

  • Histórico

Fila Dinâmica com Prioridade(FIFO)

  • Vazio
Logo

Estruturas

Listas

Sem ordenação

Simples

Dupla

Com ordenação

Simples

Dupla

Estática

Cruzada

Filas

Estáticas

Simples

Circular

Dinâmicas

Normal

Com Prioridade

Circular

Pilhas

Estáticas

Simples

Múltipla

Dinâmicas

Simples

Hashing

Sem Tratamento

Simples

Com Tratamento

Listas Encadeadas

Área de Overflow

Árvores

Balanceadas

AVL

Rubro-Negra

B

Não Balanceadas

Binária

Trie

Patricia
Histórico

Lista Ordenada Simples

Lista Ordenada Estática

Lista Ordenada Dupla

Lista Sem Ordenação Simples

Lista Sem Ordeneção Dupla

Lista Cruzada

Fila Estática

Fila Estática Circular

Fila com Prioridade

Fila Dinâmica

Fila Circular

Pilha Estática

Pilha Múltipla

Pilha Dinâmica

Hash sem Tratamento

Hash com Tratamento

Hash com Overflow

Árvore AVL

Árvore B

Árvore RubroNegra

Árvore Binária

Árvore Trie

Árvore Patricia

Estrutura não encontrada