Professor Ulisses Vasconcelos Estrutura de dados Aula 03 - Filas

Professor Ulisses Vasconcelos

Estrutura de dadosAula 03 - Filas


FILAConceito InserçãoRemoção


FILA - Conceitos Fila: É uma lista linear na qual todas as

inserções são feitas num extremo da lista (a parte de trás) e todas as eliminações, e normalmente todos os acessos, são feitos no outro extremo da lista (parte da frente).

Inserção e remoção baseado em fifo: O primeiro a entrar é o primeiro a sair e o ultimo a entrar é também o ultimo a sair (First-In / First-Out)

Estrutura dinâmica: Comprimento variável O único elemento que se tem acesso é o

elemento que está na frente


FILA - ConceitosFila de vetores - Insere Vetores possuem um espaço

limitado para armazenamento de dados.

Necessitamos definir um espaço grande o suficiente para a nossa fila.

Necessitamos de um indicador de qual elemento do vetor é o atual fim da fim (ultimo).

Incluímos sempre no fim.

-120554

1289

01234

24

5

Filacheia

Filavazia

posição doúltimo

início da fila


FILA - ConceitosFila de vetores - RetiraProcedimento:

Testamos se há elementos.

Decrementamos o fim da fila (último).

Salvamos o primeiro elemento em variável aux.

Empuramos tudo para a frente.

5420554128924

554128924

20

início da filaposição doúltimo


FILA - Conceitos Funcionamento de fila utilizando vetores -

Declaração da filaconst m = 50;

type tipo_nodo=integer;fila=record primeiro:byte;

ultimo:byte; elem:array[1..m] of tipo_nodo;

end;

m

0 Primeiro

Ultimo

1

2

3

m


FILA - Conceitos Funcionamento de fila utilizando

vetores - Inicialização da filaprocedure cria_fila(var

f:fila); begin f.primeiro:=0; f.ultimo:=-1; end;

-1

0 Primeiro

Ultimo


Fila - Conceitos Inserção em fila de vertorProcedure push(var :fila;i:tipo_nodo); begin if f.ultimo=m then writeln(‘fila cheia’); else begin f.ultimo:=f.ultimo+1; f.elem[f.ultimo]:=i; end; end;

-1

0

Ultimo

Primeiro

M é uma contante com o valor máximo do vetor (4)

elem

0

1


FILA - Conceitos Exclusão em fila de vetorfunction pop(var f:fila):byte; begin if f.ultimo<f.primeiro then writeln(‘fila vazia’) else begin f.primeiro:=f.primeiro+1; end; end;

m

1

Ultimo

1

2

3

m

Primeiro2


FILA - Ponteiros Declaraçãoapontador =

^celula;celula = recorditem:integer;prox:apontador;end;tipofila=recordfrente:apontador;tras:apontador;end;

Célula

Item

Próx

imo

fren

te

traz

célulaRef. 0

célulaRef. 1

Ref. 0 Ref. 1


FILA - Ponteiros Inicializaçãoprocedure iniciafila(var

fila:tipofila);varaux:apontador;beginnew (aux);fila.frente:=aux;fila.tras:=fila.frente;fila.tras^.prox :=nil;end;

Fren

te

Traz

aux Ref. 0

Item

Próx

imoRef. 0

Ref. 0 Ref. 0

NIL


FILA - PonteirosVerifica fila vaziafunction vazia(fila:tipofila):boolean;

beginvazia:=fila.frente = fila.tras;end;


FILA - Ponteiros Inserçãoprocedure inserir(x:integer;var

fila:tipofila);var aux:apontador;beginnew (aux);fila.tras^.prox:=aux;aux^.prox := nil;aux^.item :=x;fila.tras := aux;end;

Fren

te

Traz

Item

Próx

imoRef. 0

Ref. 0 Ref. 0

NIL

Item

Próx

imoRef. 1

aux: Ref. 1

Ref. 1

NIL

Valor passado por parâmetro: 5

5

Ref. 1


FILA - Ponteiros Exclusãoprocedure retirar(var fila:tipofila);

varaux:apontador;begin aux:=fila.frente^.prox; fila.frente^.prox := aux^.prox; if (fila.frente^.prox = nil ) then

fila.tras := fila.frente; dispose(aux);end;

Fren

te

Traz

Item

Próx

imo

Ref. 0

Ref. 0 Ref. 1

Ref. 1

5

Item

Próx

imoRef. 1

NIL

aux: Ref. 1

NIL

Ref. 0

Documents

Professor Ulisses Vasconcelos Estrutura de dados Aula 03 - Filas