Publicidade cabeçário

segunda-feira, 29 de abril de 2013

Estrutura de Dados - Fila (FIFO)


Uma fila é uma estrutura de dados que admite inserção de novos elementos e remoção de elementos antigos.  Mais especificamente, uma  fila  é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há menos tempo.
Exemplo de FIFO
fonte da imagem: bdfatec.blogspot.com.br


Em outras palavras, o primeiro objeto inserido na fila é o primeiro a ser removido. Essa política é conhecida pela sigla FIFO (= First-In-First-Out). Agora se você quiser que o primeiro elemento a ser inserido (empilhado), seja o último elemento a ser removido clique aqui e veja <<PILHA(FILO)>>




Um exemplo de aplicação para filas, é a fila de processos de um sistema operacional. Nela, é estabelecido um tempo t que será usado por cada um dos processos. Se durante a execução de um processo o tempo passa de 0 a t, este é posto na fila e o processo seguinte é executado. Se o processo seguinte não terminar de ser executado no tempo t, ele é posto na fila e o processo subsequente é executado, e assim por diante até todos os processos serem executados.
Em termos de controle de estoque, refere-se a um método de armazenamento onde os itens são consumidos por ordem de chegada.

Situação problema


Nós iremos montar um menu com os seguintes itens:

1 - Criar Fila Vazia
2 - Inserir um nó na Fila
3 - Testar se a Fila está vazia ou não
4 - Exibir valor do último nó
5 - Exibir valor do primeiro nó
6 - Eliminar um nó
7 - Exibir toda a Fila
8 - Exibir a quantidade de elementos da Fila
0 - Sair



#include<conio.h>
#include<stdio.h>
#include<windows.h>

struct noFila{
       int valor;
       noFila *prox;
       } *inicio,*fim;

Aqui estamos importando as bibliotecas e criando nossa "fila"


void criarFilaVazia(){
     inicio = fim = NULL;
     printf("\n\t Fila criada com sucesso!!!");
     }// fim criarFilaVazia

void inserirFila(){
     int val;
     
     printf("\n\t Digite um valor.:");
     scanf("%d",&val);
     noFila *novo = (noFila*)malloc(sizeof(noFila));
     novo->valor = val;
     novo->prox = NULL;
     if(inicio == NULL){
        inicio = fim = novo;
               }else{
                     fim -> prox = novo;
                     fim = novo;
                     }//fim if
     }// fim inserirFila
     
void testeFilavazia(){
     if(inicio-> prox == NULL ) printf("\n\t A lista está vazia");
     else printf("\n\t A lista NAO está vazia");
     }//fim testeFilavazia

void imprimeUltimo(){
     printf("\n\t O ultimo valor da FILA e %d",fim->valor);
     }//fim imprimeUltimo

void imprimePrimeiro(){
     printf("\n\t O ultimo valor da FILA e %d",inicio->valor);
     }//fim imprimePrimeiro

void eliminarNo(){
     noFila *aux;
     if(inicio->prox != NULL){
                 aux = inicio->prox;
                 free(inicio);
                 inicio = aux;    
                     }else free(inicio);
     printf("\n\t No eliminado com sucesso!!");
     }//fim eliminarNo

void exibirFila(){
     noFila *aux;
     int i=0;
     
     aux = inicio;
     if(inicio->prox == NULL)printf("\n\t A lista está vazia");
     else{
     while(aux != NULL){
                     i++;
                     printf("\n\t %d - elemento = %d",i,aux->valor);
                     aux = aux->prox;
                     }//fim while
       }//fim if
     }// fim exibirFila
     
void exibirTamanho(){
     noFila *aux;
     int i=0;
      while(aux != NULL){
                     i++;
                     aux = aux->prox;
                     }//fim while
     printf("\n\t A Fila tem %d elementos",i);               
     }// fim exibirTamanho

Aqui estamos criando todos os métodos ( funções) do menu.


int main(){
    int nOpc; 
do{
printf("----------------------- Menu --------------------------------");
printf("\n\n\t1 - Criar Fila Vazia");
printf("\n\t2 - Inserir um nó na Fila");
printf("\n\t3 - Testar se a Fila está vazia ou não");
printf("\n\t4 - Exibir valor do último nó");
printf("\n\t5 - Exibir valor do primeiro nó");
printf("\n\t6 - Eliminar um nó");
printf("\n\t7 - Exibir toda a Fila");
printf("\n\t8 - Exibir a quantidade de elementos da Fila");
printf("\n\t0 - Sair");

printf("\n\nDigite a opcao desejada: ");
scanf("%d",&nOpc);

switch (nOpc){
case 0:
                 printf("\n\nObrigado por utilizar o programa\n\n Pressione ENTER para sair...");
                 break;
            case 1:
criarFilaVazia();
printf("\n\nPressione ENTER para continuar...\n\n");
break;
case 2:
        inserirFila();
printf("\n\nPressione ENTER para continuar...\n\n");
break;
case 3:
    testeFilavazia();
printf("\n\nPressione ENTER para continuar...\n\n");
break;
case 4: 
                 imprimeUltimo();
                 printf("\n\nPressione ENTER para continuar...\n\n");
                 break;
            case 5:
                 imprimePrimeiro();
                 printf("\n\nPressione ENTER para continuar...\n\n");
                 break;
            case 6:
                 eliminarNo();
                 printf("\n\nPressione ENTER para continuar...\n\n");
                 break;
            case 7:
                 exibirFila();
                 printf("\n\nPressione ENTER para continuar...\n\n");
                 break;
            case 8:
                 exibirTamanho();
                 printf("\n\nPressione ENTER para continuar...\n\n");
                 break;
            default:
                printf("\n\nOpcao Invalida \n");  
                break;  
} // fim switch
getch();
system("cls");
       }while(nOpc != 0);
    }//fim main

Agora estamos montando nosso main com o menu propriamente, daqui será "chamado" os métodos.


Menu com a FILA
fonte da imagem: bdfatec.blogspot.com.br




fonte: < Prof. Jean Daniel - Estrutura de Dados
          < Filas >
          < FIFO >
adaptado: arroyo, gabriel


Gostou do blog? Então segue =D 
Gostou da postagem? Então comenta ;DDD 
Fique por dentro das atualizações