Fila Dinâmica

Completando a lista dinâmica e a pilha dinâmica, vejamos esta estrutura dinâmica, a fila, explorando o potencial de alocação sob demana da memória de um computador.

Lembrando: A fila é uma lista com restrição de entrada e saída, assim, só podemos retirar elementos de quem chegou primeiro (início), e os novos elementos devem ser inseridos no final.

Para isso, ao codificarmos um exemplo, precisaremos de dois ponteiros: um que aponta para o início da fila e outro para o final. Podemos criar uma estrutura (struct) para controlar estes ponteiros.

Ainda assim será necessário ter uma estrutura com o elemento e o ponteiro para o próximo elemento.

Vejamos através de imagens e vídeos a representação gráfica desta estrutura de dados:

Exemplos by: http://mda.codeplex.com/

Agora que já esta dominado este conceito, segue um breve exemplo de codificação de uma fila em C:

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

struct Item
{
    int numero;
    struct Item *proximo;
};

struct Fila
{
    Item *inicio;
    Item *fim;
};

void Inicializar(Fila **fila)
{
    // -> Recebe a fila por referencia
    //    para inicializá-la
    *fila = (Fila *) malloc(sizeof(Fila));
    (*fila)->inicio = NULL;
    (*fila)->fim = NULL;
}

int EstaVazia(Fila *fila)
{
    return fila->inicio == NULL;
}

void Inserir(Fila *fila, int elemento)
{
    Item *novo;
    novo = (Item *)malloc(sizeof(Item));  

    // -> Verifica se a memória foi alocada com sucesso
    if (novo != NULL)
    {
        novo->numero = elemento;
        novo->proximo = NULL;

        if(EstaVazia(fila))
        {
            // -> Primeiro Item da Fila.
            fila->inicio = novo;
            fila->fim = novo;
        }
        else
        {
            // -> Ultimo item da Fila
            fila->fim->proximo = novo;
            fila->fim=novo;
        }
    }
}

void Retirar(Fila *fila)
{
    Item *item;

    if(!EstaVazia(fila))
    {
        item = fila->inicio;
        fila->inicio = item->proximo;
        free(item);

        // -> Se a fila acabou devemos atualizar o final
        if (fila->inicio == NULL)
            fila->fim = NULL;
    }
}

void MostrarFila(Fila *fila)
{
    int i = 0;
    Item *item;
    printf("\n\n Listando...\n\n");
    printf("---------------------------------\n");

    if (EstaVazia(fila))
    {
        printf ("A Fila esta vazia!\n");
    }
    else
    {      
        item = fila->inicio;

        while(item != NULL)
        {
            i++;
            printf("[%i] -> %i\n", i, item->numero);
            item = item->proximo;
        }
    }

    printf("---------------------------------\n");
}

void Menu()
{
    printf( "Digite a sua escolha: \n"
        "    1 enfileirar elemento \n"
        "    2 retirar da fila \n"
        "    3 para finalizar \n"
        "? ");
}

void main()
{   
    Fila *fila = NULL;
    int opcao;
    int numero;

    Inicializar(&fila);
    Menu();
    scanf("%i", &opcao);

    while (opcao != 3)
    {

        switch (opcao)
        {
            case 1:
                printf( "Digite um numero: ");
                scanf("\n%i", &numero);

                Inserir(fila, numero);
                MostrarFila(fila);

                break;
            case 2:
                Retirar(fila);
                MostrarFila(fila);

                break;

            default:
                printf( "Escolha invalida.\n\n");
                Menu();
                break;
        }

        scanf("%i", &opcao);   
    }

    system("pause");
}

Também é uma estrutura simples, alguns acham ela mais complexa que a pilha, por conta de lidar com dois ponteiros: o inicio e o fim. - Mas como encapsulamos estes ponteiros em uma estrutura, fica fácil manter e compreender o código.

Devemos ficar atento:

• Devemos inserir os elementos no final da fila. Se for o primeiro elemento os dois ponteiros devem apontar para ele, caso contrário, o ponteiro “próximo” do ultimo elemento deve apontar para este novo elemento.
• Removemos elemento sempre do início da fila, se removermos todos, o ponteiro do último também deve ser “zerado”, se não, o ponteiro do inicio deve ser o “proximo” do item inicial atual.

Um pouco confuso, por isso testem.

E para diversão fica:

• Implemente a fila com uma estrutura de aluno, que tenha RA (inteiro), Nome (char de 50).

Obrigado e bons estudos :D