Implementação de Fila em C com Alocação Dinâmica

Filas - FIFO (First-In, First-Out)

São estruturas de dados do tipo FIFO (first-in first-out), onde o primeiro elemento a ser inserido, será o primeiro a ser retirado, ou seja, adiciona-se itens no fim e remove-se do início.

Operações com Fila:

Todas as operações em uma fila podem ser imaginadas como as que ocorrem numa fila de pessoas num banco, exceto que os elementos não se movem na fila, conforme o primeiro elemento é retirado. Isto seria muito custoso para o computador. O que se faz na realidade é indicar quem é o primeiro.

• Criar fila (informar a capacidade no caso de implementação sequencial - vetor);
• push() (enqueue) - o elemento é o parâmetro nesta operação;
• pop() (dequeue);
• Mostrar a fila (todos os elementos);
• Verificar se a fila está vazia (isEmpty);
• Verificar se a fila está cheia (isFull - implementação sequencial - vetor).

Proposta de algoritmo em C

#include #include

#define N 5

struct fila{ int t; //t carregará o tamanho o número de elementos na fila int ini; // ini marcará o início (elemento a ser retirado da fila) int vet[N]; //vet[N] é o vetor que representa os elementos na fila };

//Cria a Fila struct fila *cria(){ struct fila *f=( struct fila*)malloc(sizeof(struct fila)); if (f==NULL){ printf("Falha na alocação de memória"); system("pause"); exit(1); // Sair do programa caso falhe a alocação de memória } f->t=0; f->ini=0; return f; }

//Insere elementos na Fila int push (struct fila *f, float v) { if(f->t==N){ printf("Capacidade da fila esgotada.\n"); return 0; } f->vet[f->t]=v;
/*Algoritmo Fila com vetor e alocação dinâmica – Prof. Wagner Santos
fonte: http://www.cos.ufrj.br/~rfarias/cos121/filas.htm 2 */
f->t++; }

//Exclui na Fila int pop(struct fila *f){ int v; if(f->t == 0){ printf("fila vazia.\n"); return -1; } v=f->vet[f->ini]; f->ini++; return v; }

//Mostra elementos da Fila na tela int exibe(struct fila *f){ if(f->t == 0){ printf("fila vazia.\n"); system("pause"); return 0; } printf("Conteúdo da fila\n"); int i; for(i=f->ini;it;i++) if(f->vet[i]!=0){ printf("%d",f->vet[i]); printf("\t"); } printf("\n"); system("pause"); }

//Libera Fila da Alocação dinâmica void fila_libera(struct fila *f){ free(f); }

//Função para mostrar menu na tela. void menu(){ system("cls"); printf("Escolha uma das opções do menu: \n"); printf("1. Insere na fila\n"); printf("2. Exclui da fila \n"); printf("3. Exibe elementos da fila\n"); printf("4. Finaliza a fila\n"); }

/*Algoritmo Fila com vetor e alocação dinâmica – Prof. Wagner Santos
fonte: http://www.cos.ufrj.br/~rfarias/cos121/filas.htm 3 */

int main(){ struct fila *f; f = cria(); int op, item;

do{ menu(); scanf("%d", &op); switch (op){ case 1 : //insere printf("Entre com o valor para a Fila: "); scanf("%d", &item); insere(f,item); break; case 2 : //retira printf("Elemento retirado foi %d\n",retira(fi)); break; case 3 : //mostra exibe(f); break; } printf("\n"); system("pause"); } while(op!=4); return 0; }