Universidade Federal do AmazonasInstituto de Ciências Exatas e Tecnologia

Algoritmos e Estrutura De Dados IIProf. Lady Daiana de Oliveira Pinto

Acadêmicos: Andrei RodriguesLuciano CavalcanteMaikon MonteiroRay Frank FernandesRuan Silva

FILASEstática e Dinâmica

3

Conceitos e FundamentosFILAS

É uma estrutura de dados na qual todas as remoções são feitas em uma extremidade chamada frente e todas as inserções são feitas em uma extremidade chamada fim (ré), são conhecidas também como estrutura FIFO (First in, first out), o primeiro a ser inserido é o primeiro a ser removido.

4

A fila é simplesmente uma lista linear de informações , que é acessada na ordem primeiro a entrar, primeiro a sair.

Sendo assim, o primeiro item a entrar será o primeiro a ser retirado, o segundo a entrar será o segundo a ser retirado e assim por diante.

FILAS

Como funcionam?

5

Pra que servem? Tanto a estática quanto a dinâmica possuem a

mesma finalidade (Organizar elementos, impondo uma sequência/ prioridade lógica).

FILAS

Eliminações no início

Inserções no final.

Exemplo...

6

FILAS

Exemplo da fila de um banco

CAIXA

AB

C G

D

E

F

O problema apresenta desordem

Quem será atendido primeiro?

Qual seria a melhor solução?

7

FILAS

Solução... Organizar os elementos, impondo uma

prioridade no atendimento.CAIXA

EA B C D F G1 ᴼ

2 ᴼ

3 ᴼ

4 ᴼ

5 ᴼ

6 ᴼ

7 ᴼ

Assim o primeiro a entrar será o primeiro a sair (FIFO)

8

FILAS

Outro exemplo

As filas nos permitem realizar diversos tipos de operações:Inserir Elementos;Buscar Elementos;Remover Elementos;Listar Elementos Inseridos.

FILAS

Operações disponíveis em filas

0 1 2 3 4Elemento digitado

Inserir Elementos:A função inserir permite adicionar um novo

elemento a uma fila existente.

FILAS

Buscar Elementos:A função “busca elemento” permite ao usuário verificar

se um determinado elemento existe ou não na fila. A função deve retornar verdadeiro caso o elemento exista, ou falso caso não seja encontrado.

0 1 2 3 4Elemento digitado

Verdadeiro: v[1]

falso

FILAS

Remover Elementos:A função “remove elemento” elimina primeiro elemento

da fila. Em seguida a fila é reordenada passando-se os elementos posteriores para frente.

0 1 2 3 4Elemento digitado

Removido: v[0]

FILAS

Listar Elementos inseridos:A função que lista os elementos inseridos imprime na tela os elementos que a fila possui. Caso a fila esteja vazia, a função deve retornar uma mensagem de erro do tipo “fila vazia.”.

0 1 2 3 4IMPRIMINDO

FILAS

Observação:A inicialização da fila é algo que ocorre de forma

automática no inicio do programa.

FILAS

15

FILASAlgoritimos // Grupo: Maikon, Andrey, Ray Frank, Luciano e Ruan

#include<stdio.h>#include<stdlib.h>void inserir(void), listar(void), remover(void), pesquisa(void);int pesquisar(int p);int *M;int cont=0;main(){ int cod; M=malloc(5*sizeof(int)); for(;;){system("cls"); printf("\n\t .....FILA.....\n\n"); printf(" cod.\n"); printf(" 1-> Inserir\n"); printf(" 2-> listar\n"); printf(" 3-> Pesquisar\n"); printf(" 4-> Remover\n"); printf(" 5-> sair\n\n"); do{ printf(" digite o codigo:"); scanf("%d",&cod);}while(cod<1 || cod>5); switch(cod){ case 1:inserir();break; case 2:listar();break; case 3:pesquisa();break; case 4:remover();break; case 5:{free(M); exit(0);} }}}

// inserir os números!! void inserir(void) { int s, k; system("cls"); if(cont==5){ printf("\n >>> Fila cheia! <<<\n\n"); system("PAUSE"); return;} printf(" digite o numero:"); scanf("%d",&s); k=pesquisar(s); if(k!=0){printf("\n Numero existe! tente novamente!\n\n"); system("PAUSE"); return inserir();} cont++; M[cont]=s;} //pesquisar se há o número desejado!! int pesquisar(int p) {int a; for(a=1;a<6;a++){ if(p==M[a]) return a;} return 0; }

16

//função de pesquisa void pesquisa(void){ int h; system("cls"); printf("\n digite o numero:"); scanf("%d",&h); h=pesquisar(h); if(h!=0)printf("\n Numero Existe!\n\n\n"); else printf("\n Numero nao Existe!\n\n\n"); system("pause");} //remover numeros! void remover(void) {int b; system("cls"); if(cont==0){ printf("\n Fila Vazia!\n\n"); system("PAUSE"); return;} for(b=1;b<=cont;b++) M[b]=M[b+1]; cont--;}

// listar os numeros que estao na fila! void listar(void) {int a; system("cls"); if(cont==0){ printf("\n Fila Vazia!\n\n"); system("PAUSE"); return;} printf("\n numeros da Fila!!\n"); for(a=1;a<=cont;a++) printf(" %d\n",M[a]); printf("\n\n"); system("PAUSE");return;}

FILASAlgoritimos

Algoritmos: Teoria e prática. Tradução da Segunda edição Americana. Editora Campus, 2002.  MONTENEGRO, F. & PACHECO, R., Orientação a Objetos em C++, Ciência Moderna, 1994.

 STROUSTRUP, B., A Linguagem de Programação C++, Bookman, 3a edição, 2001.

 SIPSER, M. Introdução a Teoria da Computação, Thomson, 2007.

CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L. Algoritmos – Teoria e Prática, Editora Campus, 2002.

17

Referências Bibliográficas

18

FIM!Obrigado pela atenção!