Fila

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1402 palavras )
  • Download(s) : 0
  • Publicado : 18 de junho de 2012
Ler documento completo
Amostra do texto
ESTRUTURA DE DADOS

Ricardo de Almeida (ricalme@hotmail.com)

Agenda
1. 2. 3. 4. 5.

Relembrando... Filas Interface do Tipo Fila Implementação de Fila com Vetor Revisão

Relembrando...
Quais pontos foram vistos no capítulo anterior? • Filas • Interface do Tipo Pilha • Implementação de Pilha com Vetor • Implementação de Pilha com Lista • Exemplos de Uso: Calculadora Pós-Fixada Filas
Filas

Outra estrutura de dados bastante usada em computação é a fila.
Na estrutura de fila, os acessos aos elementos também seguem uma regra. O que diferencia a fila da pilha é a ordem de saída dos elementos: enquanto na pilha “o último que entra é o primeiro que sai”, na fila “o primeiro que entra é o primeiro que sai” (a sigla FIFO – first in, first out – é usada para descrever essaestratégia). A idéia fundamental da fila é que só podemos inserir um novo elemento

no final da fila e só podemos retirar
o elemento do início.

Filas
Filas

A estrutura de fila é uma analogia natural com o conceito de fila
que usamos no nosso dia a dia: quem primeiro entra numa fila é o primeiro a ser atendido (a sair da fila). Um exemplo de utilização em computação é a implementação de umafila de impressão. Se uma impressora é compartilhada por várias máquinas, deve-se adotar uma estratégia para determinar que documento será impresso primeiro. A estratégia mais simples é tratar todas as requisições com a mesma prioridade e imprimir os documentos na ordem em que

foram submetidos – o primeiro submetido é o primeiro a ser
impresso.

Filas
Filas

De modo análogo ao quefizemos com a estrutura de pilha, neste
capítulo discutiremos duas estratégias para a implementação de uma estrutura de fila: usando vetor e usando lista encadeada. Para implementar uma fila, devemos ser capazes de inserir novos elementos em uma extremidade, o fim (último), e retirar elementos da outra extremidade, o início (primeiro).

Filas
Interface do Tipo Fila Antes de discutirmos as duasestratégias de implementação, usando um vetor e usando uma lista encadeada, podemos definir a interface disponibilizada pela estrutura, isto é, definir

quais operações serão implementadas para manipular a fila.
Mais uma vez, para simplificar a exposição, consideraremos uma estrutura que armazena valores reais. Independente da estratégia de implementação, a interface do tipo abstrato (TAD) querepresenta uma estrutura de fila pode ser composta pelas seguintes funções:

Filas
Interface do Tipo Fila Interface do tipo abstrato Fila: fila.h – função fila_cria: • aloca dinamicamente a estrutura da fila.

• inicializa seus campos e retorna seu ponteiro.
– funções fila_insere e fila_retira • inserem e retiram, respectivamente, um valor real na fila. – função fila_vazia • informa se a filaestá ou não vazia.

– função fila_libera
• destrói a fila, liberando toda a memória usada pela estrutura.

Filas
Exemplo 12.1: Implementação da Interface do módulo do TAD Fila:
/* Exemplo 12.1 e 12.2 Arquivo fila.h Interface do módulo - TAD Fila */ /*TAD:Fila */ /* Tipos exportados */ typedef struct fila Fila; /* Função Cria: aloca dinamicamente a estrutura da fila inicializando seus campos*/ Fila* fila_cria (void); /* Função Insere: insere o valor na fila */ void fila_insere (Fila* f, float valor); /* Função Retira: retira o valor na fila */ float fila_retira (Fila* f); /* Função Vazia: Informa se a fila está ou não vazia */ int fila_vazia (Fila* f); /* Função Libera: Destrói a fila, liberando toda a memória usada pela estrutura fila */ void fila_libera (Fila* f); /* FunçãoImprime fila: imprime valores da fila de forma gráfica tanto para vetor quanto para lista */ void fila_imprime (Fila* f);

Filas
Implementação de Fila com Vetor Observem como o processo de inserção e remoção em

extremidades opostas faz com que a fila “ande” no vetor: • inserção dos elementos 1.4, 2.2, 3.5, 4.0

• remoção de dois elementos

Filas
Implementação de Fila com Vetor

Com essa...
tracking img