Tad fila

ˆ FACULDADE DE CIENCIAS E TECNOLOGIA DA UNIVERSIDADE DE COIMBRA
´ DEPARTAMENTO DE MATEMATICA

T. A. D. FILA RELAT´RIO O

1

INTRODUCAO ¸˜

1

1

Introdu¸ao c˜

Podemos definir uma fila como sendo uma lista ordenada na qual as inser¸˜es s˜o feitas co a num extremo, que designamos por cauda ou “fim” da fila, ao passo que as elimina¸˜es co s˜o feitas no outro extremo, designado por cabe¸a ou frente da fila. a c As opera¸˜es b´sicas numa fila s˜o: co a a Inserir - que insere um elemento no fim da fila. Remover - que apaga o elemento da frente da fila. A figura que se segue ilustra o modelo abstracto de uma fila. frente
'

Fila F

fim
'

F.remover()

F.inserir()

Uma fila ´ uma estrutura do tipo FIFO (first in first out), isto ´, “o primeiro e e elemento a entrar ´ o primeiro a sair”. Um TAD fila ´ uma estrutura de dados que e e cont´m uma colec¸˜o de dados seguindo a pol´ e ca ıtica do FIFO, e ainda um conjunto de opera¸˜es gerais que, para al´m das opera¸˜es principais j´ referidas, engloba ainda um co e co a conjunto de outras opera¸˜es auxiliares, tais como: co • frente • fim • vazia • cheia • tamanho • listar que mais ` frente trataremos com maior pormenor. a O objecto fila ´, pois, uma instancia¸˜o de uma classe espec´ e ca ıfica que generaliza os m´todos necess´rios para manipular um objecto fila. e a Em POO existem v´rias aproxima¸˜es para implemetar a classe Fila, sendo que a co estas diferem estre si, basicamente na forma como os dados est˜o alocados e como os a elementos est˜o relacionados entre si. a

2

Objectivos

Os objectivos principais deste trabalho s˜o a implementa¸˜o do TAD Fila em POO a ca e de um programa que permita demonstrar e testar a classe Fila implementada. Tal como j´ foi referido, v´rias s˜o as implementa¸˜es poss´ a a a co ıveis para esta classe, e portanto proposemo-nos a explorar uma delas n˜o deixando, contudo, de fazer referˆncia a oua e tras, igualmente poss´ ıveis. Pretende-se com este trabalho a aplica¸˜o de