912530 Aula 10 Fila

Programa¸c˜ao de Computadores II
Prof. Kleber Jacques F. de Souza
PUC Minas

Aula 10 - Fila

Prof. Kleber Jacques F. de Souza

Programa¸c˜ ao de Computadores II

Agenda

1

Fila

2

Propriedade e Aplica¸c˜ oes das Filas

3

TAD Fila

4

Implementa¸c˜ao de Filas por meio de Apontadores

Prof. Kleber Jacques F. de Souza

Programa¸c˜ ao de Computadores II

Fila
Uma lista linear em que todas as inser¸c˜ oes s˜ao realizadas em um extremo da lista, e todas as retiradas e, geralmente, os acessos s˜ao realizados no outro extremo da lista.
O modelo intuitivo de uma fila ´e o de uma fila de espera em que as pessoas no in´ıcio da fila s˜ao servidas primeiro e as pessoas que chegam entram no fim da fila.
S˜ao chamadas listas FIFO (“First-In”, “First-Out”).
Existe uma ordem linear para filas que ´e a “ordem de chegada”. S˜ao utilizadas quando desejamos processar itens de acordo com a ordem “primeiro-que-chega, primeiro-atendido”.
Sistemas operacionais utilizam filas para regular a ordem na qual tarefas devem receber processamento e recursos devem ser alocados a processos
Prof. Kleber Jacques F. de Souza

Programa¸c˜ ao de Computadores II

TAD Fila

Conjunto de opera¸c˜ oes: 1
2

3
4

5

FFVazia(Fila). Faz a Fila ficar vazia.
Vazia(Fila). Retorna true se a fila est´a vazia; caso contr´ario, retorna false.
Enfileira(x, Fila). Insere o item x no final da Fila.
Desenfileira(Fila, x). Retorna o item x no inicio da Fila, retirando-o da Fila.
Tamanho(Fila). Esta fun¸c˜ao retorna o n´ umero de itens da
Fila.

Existem v´arias op¸c˜ oes de estruturas de dados que podem ser usadas para representar Filas.
As duas representa¸c˜ oes mais utilizadas s˜ao as implementa¸c˜oes por meio de arranjos e de apontadores

Prof. Kleber Jacques F. de Souza

Programa¸c˜ ao de Computadores II

Implementa¸c˜ao de Filas por meio de Apontadores
H´a uma c´elula cabe¸ca que facilita a implementa¸c˜ao das opera¸c˜oes Enfileira e Desenfileira quando a fila est´a vazia.
Quando a fila est´a vazia, os