Fila

ESTRUTURA DE DADOS

Ricardo de Almeida ([e-mail])

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 essa estraté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 uma fila 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 que fizemos 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 duas