FAFIT - Sistemas de Informação - 2º semestre 2013 Estruturas de Dados I - Professor Danilo Exemplo de código para trabalhar com duas filas circulares de 2013-11-28 2013-11-28-exemplo-duas-filas.c

2013-11-28-exemplo-duas-filas.c

/*

Vamos admitir um cenário onde haja duas filas: de entrada e saída. Por exemplo
um banco movimentado onde vc pega a senha para a fila para ser atendido, depois
é atendido e depois entra em outra fila para sair do banco (muito movimentado
com apenas 1 porta rotatória)

Neste cenário vc tem 3 momentos:
1 - está na fila de entrada
2 - está sendo atendido (portanto fora das 2 filas)
3 - está na fila para sair do banco

*/

#include <stdio.h>

#define MAX_F_ENTRADA 20
#define MAX_F_SAIDA 10

// Estrutura da PESSOA
struct ST_Pessoa {
    int
        ordem; // Teremos apenas a ordem que a pessoa chega no banco pra simplificar o exemplo
};
typedef struct ST_Pessoa PESSOA; // o TIPO 'PESSOA'

// Estruturas das filas de entrada e saída
struct ST_FilaEntrada {
    int
        n, // Quantidade de elementos
        ini; // Início
    PESSOA
        vetor[MAX_F_ENTRADA]; // PESSOAs na fila
};
typedef struct ST_FilaEntrada F_ENTRADA;
struct ST_FilaSaida {
    int
        n, // Quantidade de elementos
        ini; // Início
    PESSOA
        vetor[MAX_F_SAIDA]; // PESSOAs na fila
};
typedef struct ST_FilaSaida F_SAIDA;

// Funções
int menu ();
PESSOA criarPessoa (int * contador);
// Observe que as funções para tratar as filas repetem
F_ENTRADA criarFilaEntrada ();
int filaEntradaVazia (F_ENTRADA * fila);
int filaEntradaCheia (F_ENTRADA * fila);
void filaEntradaInsere (F_ENTRADA * fila, PESSOA pessoa);
PESSOA filaEntradaRetira (F_ENTRADA * fila);
void filaEntradaExibe (F_ENTRADA * fila);
F_SAIDA criarFilaSaida ();
int filaSaidaVazia (F_SAIDA * fila);
int filaSaidaCheia (F_SAIDA * fila);
void filaSaidaInsere (F_SAIDA * fila, PESSOA pessoa);
PESSOA filaSaidaRetira (F_SAIDA * fila);
void filaSaidaExibe (F_SAIDA * fila);

// Programa principal
int main () {
    int
        opcao,
        contador = 0; // Contador global de pessoas que entram no banco
    // Tem que inicializar essas coisas pra não dar falha de segmentação
    // Eu esqueci e tava quebrando a cabeça, por isso comentei -.-
    F_ENTRADA
        filaEntrada = criarFilaEntrada();
    F_SAIDA
        filaSaida = criarFilaSaida();
    do {
        opcao = menu();
        switch (opcao) {
            case 1:
                // Só vai adicionar a pessoa se a fila de entrada não estiver
                // cheia...
                if (filaEntradaCheia(&filaEntrada)) {
                    printf("\n\n\tA fila de entrada está cheia.\n\n");
                } else {
                    PESSOA
                        pessoa = criarPessoa(&contador);
                    filaEntradaInsere(&filaEntrada, pessoa);
                }
                break;
            case 2:
                // Só vai realizar o atendimento se tiver pessoas na fila de
                // entrada (óbvio!) e se a fila de saída tiver lugar sobrando
                if (filaEntradaVazia(&filaEntrada)) {
                    printf("\n\n\tA fila de entrada está vazia.\n\n");
                } else if (filaSaidaCheia(&filaSaida)) {
                    printf("\n\n\tA fila de saída está cheia.\n\n");
                } else {
                    // Aqui está o segredo...
                    // Para realizarmos o atendimento, precisamos retirar a
                    // pessoa da fila de entrada. Após esse momento, ela não
                    // estará em nenhuma das duas filas :'(
                    // Por isso a CHAVE de trabalhar com 2 filas é fazer com que
                    // a função que retira um elemento da fila, retorne este
                    // elemento para trabalharmos com ele (até porque uma
                    // pessoa não vai passar ocasionalmente na frente de um
                    // banco e pensar "nossa, acho que vou entrar na fila do
                    // banco neste lindo dia"... se ela vai ao banco, é porque
                    // ela tem uma tarefa a realizar). Então aqui temos 3 etapas
                    // ou momentos:
                    // I - retiramos a pessoa da fila
                    PESSOA
                        pessoa = filaEntradaRetira(&filaEntrada);
                    // II - Agora temos uma pessoa FORA das filas e
                    // trabalharemos nela como quisermos. Sei lá, fazemos um
                    // depósito ou saque ou damos bom dia... sei lá.
                    // III - Depois de termos atendido a pessoa, simplesmente a
                    // colocamos na fila de saída do banco.
                    filaSaidaInsere(&filaSaida, pessoa);
                    // E pronto.
                }
                break;
            case 3:
                // Remove a pessoa da fila de saída (sai do banco)
                if (filaSaidaVazia(&filaSaida)) {
                    printf("\n\n\tA fila de saída está vazia.\n\n");
                } else {
                    // Apesar de a função retornar uma PESSOA, não vou passar a
                    // saída dela para nenhuma variável... afinal não me
                    // interessa o que a pessoa vai fazer depois que saiu do
                    // banco. :)
                    filaSaidaRetira(&filaSaida);
                }
                break;
            case 4:
                filaEntradaExibe(&filaEntrada);
                filaSaidaExibe(&filaSaida);
                break;
        }
    } while (opcao != 0);
}

// Menu, isso aqui é tranquilo...
int menu () {
    int
        opcao;
    do {
        printf(
            "\n\n\n"
            "1 - inserir pessoa na fila de entrada\n"
            "2 - atender pessoa na frente da fila de entrada\n"
            "3 - registrar a saída da pessoa na frente da fila de saída\n"
            "4 - exibir filas\n"
            "0 - sair\n\n"
            "Informe sua opção: "
            );
        scanf("%d", &opcao);
        getchar();
        if (opcao < 0 || opcao > 4) {
            printf("\n\n\tOpção incorreta!\n\n");
        }
    } while (opcao < 0 || opcao > 4);
}

// Cria uma PESSOA
PESSOA criarPessoa (int * contador) {
    PESSOA
        pessoa;
    // Cada pessoa que entra vai receber um identificador, por isso a função recebe o contador
    pessoa.ordem = *contador;
    // Incrementa o valor de contador para numerar a próxima pessoa na sequência
    *contador += 1;
    // Retorna a pessoa
    return pessoa;
}

// Cria uma F_ENTRADA
F_ENTRADA criarFilaEntrada () {
    F_ENTRADA
        fila;
    // É preciso iniciar os valores da fila
    fila.n = 0;
    fila.ini = 0;
    return fila;
}

// Verifica se a F_ENTRADA está vazia
int filaEntradaVazia (F_ENTRADA * fila) {
    return fila->n == 0;
}

// Verifica se a F_ENTRADA está cheia
int filaEntradaCheia (F_ENTRADA * fila) {
    return fila->n == MAX_F_ENTRADA;
}

// Insere uma PESSOA na F_ENTRADA
// Observe que PESSOA é passado como valor, e não ponteiro
void filaEntradaInsere (F_ENTRADA * fila, PESSOA pessoa) {
    int
        fim = (fila->ini + fila->n) % MAX_F_ENTRADA;
    fila->vetor[fim] = pessoa;
    fila->n += 1;
}

// Retira um PESSOA da F_SAIDA
// Observe que a função nos fornece (retorna) a PESSOA que está sendo retirada
PESSOA filaEntradaRetira (F_ENTRADA * fila) {
    PESSOA
        pessoa = fila->vetor[fila->ini];
    fila->ini = (fila->ini + 1) % MAX_F_ENTRADA;
    fila->n -= 1;
    return pessoa;
}

// Exibe a F_ENTRADA
void filaEntradaExibe (F_ENTRADA * fila) {
    int
        a1,
        pos;
    printf(
        "\n\n"
        "Fila de Entrada\n"
        );
    for (a1 = 0, pos = fila->ini; a1 < fila->n; a1 += 1, pos = (pos + 1) % MAX_F_ENTRADA) {
        printf("Pessoa #%d\n", fila->vetor[pos].ordem);
    }
}

// Cria uma F_SAIDA
F_SAIDA criarFilaSaida () {
    F_SAIDA
        fila;
    // É preciso iniciar os valores da fila
    fila.n = 0;
    fila.ini = 0;
    return fila;
}

// Verifica se a F_SAIDA está vazia
int filaSaidaVazia (F_SAIDA * fila) {
    return fila->n == 0;
}

// Verifica se a F_SAIDA está cheia
int filaSaidaCheia (F_SAIDA * fila) {
    return fila->n == MAX_F_SAIDA;
}

// Insere uma PESSOA na F_SAIDA
// Observe que PESSOA é passado como valor, e não ponteiro
void filaSaidaInsere (F_SAIDA * fila, PESSOA pessoa) {
    int
        fim = (fila->ini + fila->n) % MAX_F_SAIDA;
    fila->vetor[fim] = pessoa;
    fila->n += 1;
}

// Retira um PESSOA da F_SAIDA
// Observe que a função nos fornece (retorna) a PESSOA que está sendo retirada
PESSOA filaSaidaRetira (F_SAIDA * fila) {
    PESSOA
        pessoa = fila->vetor[fila->ini];
    fila->ini = (fila->ini + 1) % MAX_F_SAIDA;
    fila->n -= 1;
    return pessoa;
}

// Exibe a F_SAIDA
void filaSaidaExibe (F_SAIDA * fila) {
    int
        a1,
        pos;
    printf(
        "\n\n"
        "Fila de Saída\n"
        );
    for (a1 = 0, pos = fila->ini; a1 < fila->n; a1 += 1, pos = (pos + 1) % MAX_F_SAIDA) {
        printf("Pessoa #%d\n", fila->vetor[pos].ordem);
    }
}