579761 Aula 06 ED Filas

Ernani Andrade Leite [e-mail]  Prof. Ernani Leite, Msc.

Estruturas de Dados

1

Aula 06 – Estruturas de Dados
•
•

Assunto: Filas.
Objetivos:
- Apresentar os conceitos elementares de Filas e sua aplicação no cotidiano;
- Aplicação de algoritmos em situações do dia-a-dia;
- Elaborar programas usando Filas.

•

Roteiro:
1. Introdução.
2. Definições e Conceitos.
3. Implementação de Filas com Ponteiros
4. Operando Filas.
5. Exercícios.
2

TAD Fila (1/2)
Uma fila é uma lista linear em que todas as inserções são realizadas em um extremo da lista, e todas as retiradas e geralmente os acessos são realizados no outro extremo da lista.
O modelo intuitivo de uma fila é o de uma fila de espera em que as pessoas no início da fila são servidas primeiro e as pessoas que chegam entram no fim da fila. Por esta razão as filas são chamadas de listas
FIFO, termo formado a partir de “First-In, First-Out”.
Existe uma ordem linear para filas que é a “ordem de chegada”.
Filas são 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. TAD Fila (2/2)
Um possível conjunto de operações, definido sobre um tipo abstrato de dados Fila, é definido a seguir.
1. FazFilaVazia(Fila). Faz a fila ficar vazia.
2. FilaVazia(Fila). Esta função retorna 1 (true) se a fila está vazia; senão retorna 0 (false).
3. Enfileira(x, Fila). Insere o item x no final da fila.
4. Desenfileira(Fila, x). Retira o item x que está no início da fila.
5. ImprimeFila(Fila). Imprime os itens da fila (obedecendo a ordem de chegada).
Como no caso do tipo abstrato de dados Lista, existem várias opções de estruturas de dados que podem ser usadas para representar filas. As duas representações mais utilizadas são as implementações através de arranjos (vetores) e de apontadores.

Implementação de Filas através de Arranjos