Listas Especializadas: Fila

Quando você vai em um Cinema, pode ser que você enfrente uma fila, não é verdade? Nas filas, o última que entrar na fila, será o último a comprar o ingresso e/ou entrar no cinema.

E é exatamente assim que a estrutura de Fila funciona em um programa. Trata-se de uma lista onde é imposta uma política de acesso:

• Todo elemento tem que ser inserido no final da lista.
• Todo elemento que for excluído, deve ser excluído do início da lista.

As pilhas são definidas em Inglês como Queue, ou FIFO (First In First Out =  Primeiro que Entra é o Primeiro que Sai).

Para compreender sua aplicação na informática imagine a seguinte situação: Seu computador executa várias tarefas “ao mesmo tempo” (escutar música, navegar na Internet etc.) com um único processador. Para dar conta de tudo isso o processador escalona as tarefas, ou seja, processa um pouco uma tarefa, depois um pouco uma outra tarefa e assim por diante. Para decidir a ordem da tarefa que será processada, o processador organiza as tarefas em filas, por “ordem de chegada”.

O esquema de imagens abaixo, representa o funcionamento de uma fila:

Estruturalmente os dados se comportam assim:

Já deu para perceber que temos que criar uma estrutura que controle o início e final da fila, além de ter uma inserção e exclusão de elementos diferenciada. Acompanhe uma implementação básica em C:

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

const int MAX = 100;

struct Aluno
{
    int ra;
    char nome[50];
};

struct Fila{
    Aluno dados[MAX];
    int inicio;
    int fim;
};

void IniciarFila(Fila &fila)
{
    fila.inicio = 0;
    fila.fim = 0;
}

bool FilaEstaVazia(Fila &fila)
{
    int resultado = fila.fim - fila.inicio;
    return resultado == 0;
}

bool FilaEstaCheia (Fila &fila)
{
    return fila.fim == MAX;
}

bool Enfileirar(Fila &fila, Aluno &aluno)
{
    if (!FilaEstaCheia(fila))   
    {
        fila.dados[fila.fim] = aluno;
        fila.fim++;
        return true;
    }
    else
    {
        return false;
    }
}

void Retirar(Fila &fila, Aluno &alunoRetirado)
{
    alunoRetirado = fila.dados[fila.inicio];
    fila.inicio++;
}    

void Listar(Fila fila)
{
    printf("\nListando...\n");

    while (!FilaEstaVazia(fila))
    {
        Aluno alunoRetirado;
        Retirar(fila, alunoRetirado);
        printf("\n%i - %s", alunoRetirado.ra, alunoRetirado.nome);
    }

    getch();
}

void main()
{
    char opcao;
    Fila fila;

    // -> Inicializando a Fila.
    IniciarFila(fila);

    do
    {
        system("cls");
        printf("Escolha a opcao desejada:");
        printf("\n 1- Enfileirar um Aluno");
        printf("\n 2- Retirar um Aluno da Fila");
        printf("\n 3- Listar todos os elementos da Fila");
        printf("\n 0- Sair do programa\n");
        printf("\n Opcao: ");

        opcao = getchar();

        switch(opcao)
        {
            case '1':
                Aluno aluno;

                printf(" \nDigite um nome para o Aluno: ");
                scanf("%s", &aluno.nome);

                printf(" \nDigite um RA para o Aluno: ");
                scanf("%i", &aluno.ra);

                Enfileirar(fila, aluno);

                break;
            case '2':
                Aluno alunoRetirado;
                Retirar(fila, alunoRetirado);
                printf(" \nAluno %i - %s retirado", alunoRetirado.ra, alunoRetirado.nome);
                getch();

                break;
            case '3':
                Listar(fila);

                break;
            case '0':
                return;
        }
    } while(opcao != 0);
}

Acompanhe o resultado das movimentações na fila:

Vamos para a diversão:

1) Implemente o exemplo dado anteriormente usando ponteiros.

2) Implemente uma função que retorne o número de posições livres da fila, para as duas implementações (referência e ponteiros).

3) Implemente uma função que localize um dado específico (cujo nome for igual a...) para as duas implementações da fila (referência e ponteiros). A função deve retornar na tela a posição do dado no vetor bem como as informações armazenadas sobre ele.

Espero que gostem :)