Filas

O que são as Estruturas de Dados do tipo Fila?

A fila representa um conjunto dinâmico, cujos elementos são inseridos e retirados de acordo com o seguinte protocolo: o primeiro elemento que entra no conjunto é o primeiro que sai, assim como uma fila de pessoas em um banco.

Fonte: Shutterstock.

Deseja ouvir este material?

Áudio disponível no material digital.

Praticar para Aprender

Para colocarmos em prática os conhecimentos a serem aprendidos, vamos analisar a seguinte situação: você acaba de ser contratado pelo setor de TI (Tecnologia de Informação) de um grande banco. Ao chegar no trabalho, seu supervisor lhe apresenta um problema pelo qual a agência está passando no momento.

A legislação em vigor requer que os bancos iniciem o atendimento a um cliente em no máximo 20 (vinte) minutos após a entrada do cliente na fila da agência. No banco em que você trabalha, a fila é única e há apenas um caixa ativo. Sabe-se ainda que um caixa não pode atender a mais de um cliente ao mesmo tempo. Para simplificar a solução do problema, seu chefe disse que, por enquanto, você pode ignorar o problema dos clientes prioritários, tais como idosos e gestantes.

Seu desafio será criar um programa que receberá o número de clientes e, para cada cliente, duas informações: o momento de entrada do cliente na fila e a duração do atendimento daquele cliente. De posse dessas informações, seu programa deve determinar o número de clientes que esperarão mais de 20 minutos para ter seu atendimento iniciado.

Suponha que 5 clientes procurarão a agência para atendimento. A seguir, é apresentado o momento em que cada cliente entrará na fila e o tempo necessário para atendê-lo, respectivamente.

Cliente 1: 0 e 10
Cliente 2: 0 e 10
Cliente 3: 1 e 10
Cliente 4: 2 e 10
Cliente 5: 30 e 10

Com base nesses dados, podemos ver, por exemplo, que os clientes 1 e 2 entrarão na fila da agência ao mesmo tempo e cada um tomará 10 minutos do caixa para ser atendido. A resposta esperada para o seu programa, neste caso, é 1. Ou seja, apenas um cliente terá que ficar esperando mais do que 20 minutos para ser atendido.

conceito-chave

Chegamos ao final de mais uma unidade. Até aqui, você aprendeu os recursos necessários para desenvolver soluções para problemas na linguagem de programação C. Lembre-se de que o mais importante não é se ater aos detalhes da linguagem de programação, mas aos conceitos fundamentais dos algoritmos, tais como atribuição, condicionais e laços, entre outros. É por meio deles que os problemas são efetivamente resolvidos. A linguagem nada mais é do que uma ferramenta para concretizar essa solução.

Fila

Nesta última seção, estudaremos a Estrutura de Dados conhecida como fila. A fila representa um conjunto dinâmico, cujos elementos são inseridos e retirados de acordo com o seguinte protocolo: o primeiro elemento que entra no conjunto é o primeiro que sai. Esse protocolo é amplamente conhecido como FIFO, do inglês First in, First out (primeiro a entrar, primeiro a sair). Ou seja, é possível inserir um elemento na fila a qualquer momento, mas somente o elemento que está na fila há mais tempo pode ser removido a qualquer momento. O nome fila deriva-se da metáfora de uma fila de pessoas em banco ou em um parque de diversões (GOODRICH; TAMASSIA, 2013).

A fila é outra estrutura de dados fundamental, que tem sido utilizada em diversos tipos de aplicações, desde comerciais (como em sistemas que controlam a chamada de pessoas para atendimento em um banco) até sistemas operacionais (uma das políticas mais simples de escalonamento de processos em um sistema operacional é baseada em uma fila simples).

As principais operações que devem estar presentes em uma ED do tipo fila são:

• criar(): cria e retorna uma fila vazia.
• enfileirar(f, item): também conhecida como enqueue, enfileira o elemento “item” no final da fila “f”.
• desenfileirar(f): também conhecida como dequeue, desenfileira o elemento do início da fila “f” e o retorna.
• inicio(f): retorna o elemento do início da fila “f”, sem retirá-lo dela.
• tamanho(f): retorna a quantidade de elementos existentes na fila “f”.
• vazia(f): retorna se a fila “f” está vazia ou não.
• liberar(f): desaloca a memória ocupada pela fila “f”.

O Quadro 4.3 apresenta uma série de operações e seus efeitos sobre uma fila inicialmente vazia. Considere que o elemento mais à direita do conjunto de dados representa o final da fila e o elemento mais à esquerda, o início da fila (de onde os elementos são removidos).

Assim como no caso das EDs lista e pilha, podemos implementar uma fila de pelo menos duas formas: utilizando vetores ou utilizando estruturas ligadas (ou encadeadas). Nesta seção, será apresentada a implementação por meio de estruturas ligadas.

Observe a ilustração de uma fila ligada, na Figura 4.8.

Uma fila ligada consiste em uma sequência de elementos denominados nós (representados por retângulos com uma seta em uma de suas extremidades na Figura 4.8). Cada nó contém uma informação (valor que aparece dentro do retângulo, na Figura 4.8) e um ponteiro para o próximo nó da fila (seta na extremidade direita do retângulo). O último nó da fila aponta para NULL, representando que não existe um próximo nó na fila. A fila, propriamente dita, é representada por dois ponteiros, um para o primeiro nó da fila, chamado de Inicio na Figura 4.8, e outro para o último nó da fila, chamado Fim da mesma figura.

E por que dois ponteiros? A resposta é que, diferentemente da lista simplesmente ligada e da pilha ligada, na fila os elementos são manipulados em ambas as extremidades. Por isso, é necessário um ponteiro para o início e outro para o final da fila, permitindo, assim, a manipulação dos elementos sem a necessidade de percorrer toda a estrutura de dados.

Fila ligada

Chegou a hora de implementarmos nossa primeira fila ligada. Assim como fizemos nas seções anteriores, vamos começar criando algumas structs: uma para representar cada nó da nossa fila ligada e outra para representar a fila propriamente dita. Mas, antes disso, vamos importar todas as bibliotecas que usaremos nos códigos desta seção. Cada biblioteca dessas já foi usada e comentada ao longo do livro.

#include <stdio.h>  // para operações de entrada e saída
#include <stdlib.h>  // para alocação dinâmica de memória
#include <stdbool.h> // para uso do tipo de dados “bool”
#include <stdbool.h>  // para uso da instrução “assert”

Feito isso, agora podemos observar o conteúdo das structs criadas para a fila.

struct No {
  int info;
  struct No* proximo;
};

struct Fila {
  struct No* inicio;
  struct No* fim;
  int tamanho;
};

A struct “No” é idêntica à que foi criada para a lista simplesmente ligada e para a pilha, vistas nas seções 1 e 2 desta unidade. A struct “Fila” também é bastante similar, diferenciando apenas o nome da estrutura e o nome dos ponteiros para a struct “No”, que aqui se chamam “inicio” e “fim”, indicando que eles apontam para o primeiro e para o último nós da fila.

Assim como fizemos com as EDs lista e pilha, partiremos agora para a implementação das funções da fila, uma a uma, comentando cada uma delas ao longo do texto. O Código 4.29 apresenta o código da função “criar”.

struct Fila* criar() {
    struct Fila* nova_fila = (struct Fila*) malloc(sizeof(struct Fila));
    if (nova_fila != NULL) {
        nova_fila->inicio = NULL;
        nova_fila->fim = NULL;
        nova_fila->tamanho = 0;
    }
    return nova_fila;
}

O que essa função faz é instanciar dinamicamente uma variável do tipo struct “Fila” na memória (linha 2) e configurar os valores de seus campos. Antes, porém, de configurar os valores dos campos da struct “Fila”, é preciso testar se a memória foi corretamente alocada para a fila (linha 3). Os campos “inicio” e “fim”, que são ponteiros, devem apontar para NULL, uma vez que estamos criando uma fila vazia (linhas 4 e 5). Analogamente, o campo “tamanho” deve ser inicializado com o valor igual a 0 (zero) – linha 6. Feito isso, deve-se retornar o endereço da memória alocado para a variável do tipo “Fila” (linha 8). Com isso, nós já somos capazes de criar uma fila vazia na memória do computador.

Passemos, então para a implementação das duas funções mais importantes da fila, a saber “enfileirar” e “desenfileirar”. O código dessas funções pode ser visualizado no Código 4.30 a seguir:

void enfileirar(struct Fila* f, int item) {
    assert(f != NULL);    
    struct No* novo_no = (struct No*) malloc(sizeof(struct No));
    if (novo_no != NULL) {
       novo_no->info = item;
       novo_no->proximo = NULL;

	if (f->fim != NULL) {
            f->fim->proximo = novo_no;   
      } else {        
           f->inicio = novo_no;
      }
      f->fim = novo_no;
      f->tamanho++;
    }
}

int desenfileirar(struct Fila* f) {
    assert(f != NULL);    
    assert(f->inicio != NULL);
    struct No* aux = f->inicio;
    int elemento = aux->info;
    f->inicio = aux->proximo;
    if (f->inicio == NULL) {
        f->fim = NULL;    
    }
    f->tamanho--; 
    free(aux);
    return elemento;    
}

Para a função “enfileirar”, inicialmente é feita uma verificação para garantir que o ponteiro passado por parâmetro não é nulo (linha 2). Logo após, é criado um novo nó dinamicamente e seu endereço de memória é armazenado na variável “novo_no” (linha 3). Antes de continuar com a execução da função, verifica-se ainda se o novo nó foi alocado corretamente na memória do computador (linha 4). Caso sim, das linhas 5 a 15 realiza-se a inserção do novo nó no final da fila. Para isso, inicialmente, os campos “info” e “proximo” do novo nó são inicializados. Depois, verifica-se se o ponteiro “fim” da fila é igual a NULL. Isso é importante, pois caso o ponteiro “fim” seja diferente de nulo, isso significa que a fila não está vazia. Nesse caso, deve-se atualizar o ponteiro próximo do último nó para que ele aponte para o novo nó (linha 9). Caso contrário, a fila está vazia e trata-se da inserção do primeiro nó. Assim sendo, deve-se atualizar também o ponteiro início da fila para que ele aponte para o novo nó (linha 11). Logo após, o ponteiro “fim e o campo “tamanho” da fila são atualizados.

No caso da função “desenfileirar”, além de verificar se o ponteiro passado por parâmetro para a função não é nulo (linha 19), também verificamos se a fila não está vazia (linha 20), o que impediria a remoção de um nó dela. Logo após, cria-se um ponteiro auxiliar, denominado “aux”, que aponta para o início da fila (linha 21). Esse ponteiro será usado posteriormente para a correta desalocação da memória do nó removido, por meio da função “free” (linha 28). Com o ponteiro “aux” em mãos, fazemos com que o ponteiro “inicio” da fila aponte para o elemento da fila. Caso não haja outros elementos na fila, então o ponteiro “inicio” apontará para NULL. Assim, na linha 24 é verificado se isso acontece e, caso sim, o ponteiro “fim” também deve ser apontar para NULL, uma vez que a fila ficou vazia. Por fim, campo “tamanho” é decrementado (linha 27), a memória apontada pelo nó “aux” é desalocada (linha 28) e o valor do nó removido é retornado (linha 29).

No Código 4.31 serão apresentadas as demais funções da ED fila, a saber: “vazia”, “inicio”, “tamanho” e “liberar”.

bool vazia(struct Fila* f) {
    assert(f != NULL);        
    return (f->inicio == NULL);    
}

int tamanho(struct Fila* f) {
    assert(f != NULL);        
    return f->tamanho;    
}

int inicio(struct Fila* f) {
    assert(f != NULL);     
    assert(f->inicio != NULL);         
    return f->inicio->info;    
}

void liberar(struct Fila* f) {
    assert(f != NULL);     
    while(f->inicio != NULL) {
        desenfileirar(f); 
    }
    free(f);    
}

As funções apresentadas no Código 4.31 verificam se o ponteiro para a fila, passado por parâmetro, não é igual a NULL (linhas 2, 7, 12 e 18). Além disso, a função “inicio” verifica também se a fila não está vazia, pois não é possível retornar a informação do primeiro nó de uma fila vazia (linha 13). O restante das funções são bastante parecidas com as funções similares das EDs lista e pilha. Dois destaques a serem feitos aqui estão nas linhas 3 e 14. Na linha 3, a função “vazia” retorna o resultado da avaliação da expressão f->inicio == NULL. Essa é uma forma simplificada de escrever o código a seguir:

if (f->inicio == NULL) {
  return true;
else {
  return false;
} 

Na linha 14, tem-se o acesso à informação de um nó da seguinte forma: f->inicio->info. Essa é uma forma simplificada (e mais eficiente, pois não se utiliza variáveis auxiliares) do código a seguir:

struct No* aux = f->inicio;
return aux->info;

 O código completo da ED fila pode ser encontrado a seguir, na ferramenta Paiza.io.

Exemplificando 

A seguir, no Código 4.32 é apresentado o código da função “main”, que faz uso do código da ED fila, criado anteriormente. Analise esse código e pense em qual seria a sua saída.

int main() {
    struct Fila* minha_fila = criar();
    enfileirar(minha_fila, 1);
    enfileirar(minha_fila, 2);
    enfileirar(minha_fila, 3);
    printf("Tamanho: %d ", tamanho(minha_fila));

    printf("\nMinha fila: [%d ", desenfileirar(minha_fila));
    printf("%d ", desenfileirar(minha_fila));
    printf("%d]", desenfileirar(minha_fila));

    printf("\nEstá vazia (1 - Sim, 0 - Não)? %d ", vazia(minha_fila));

    liberar(minha_fila);

    return 0;
}

Nesse código é criada uma fila vazia (linha 2), na qual são enfileirados os elementos 1, 2 e 3 (linhas 3 a 5). Após, é impresso na tela o tamanho da fila (linha 6), usando a função “tamanho”. Nas linhas 8 a 10, os três elementos anteriormente inseridos na fila são desenfileirados e impressos na tela. Por fim, a situação da fila (se está vazia ou não) é impressa e a fila é liberada da memória do computador (linha 14). Assim, a saída do código anterior é:

Tamanho: 3 
Minha fila: [1 2 3]
Está vazia (1 - Sim, 0 - Não)? 1

return aux->info;

 Você pode testar o código a seguir, utilizando a ferramenta Paiza.io.

Roteiro para o professor

Caro professor, mais uma vez vamos usar a ferramenta Visualgo ([s. d.]). Peça aos alunos que acessem o menu QUEUE para visualizar as animações para a fila ligada. Do lado inferior direito da ferramenta há um quadro com o trecho de código correspondente à operação realizada sobre a ED. Um detalhe importante é que o código não está escrito na linguagem C.

Como atividade, peça aos alunos que, em grupo, tentem relacionar cada expressão do código exibido na ferramenta para as funções “enfileirar” e “desenfileirar”, com o código. Isso permitirá que os alunos fixem melhor o conteúdo das funções apresentadas.

Faça valer a pena

void desenfileirar_se_igual(struct Fila* f, int n) {
    assert(f != NULL);    
    assert(f->inicio != NULL);
    struct No* aux = f->inicio;
    int elemento = aux->info;

    if (_____________) {
        f->inicio = aux->proximo;
        if (f->inicio == NULL) {
            _____________;    
        }
        f->tamanho--; 
        free(aux);
    }
}

Referências

AULA 31 – Fila: Definição. [S. l.], 3 nov. 2013. 1 vídeo (3 min. 43 s.). Publicado pelo canal Linguagem C Programação Descomplicada. Disponível em: https://bit.ly/3tariXs. Acesso em: 19 jan. 2021.

BEGIN, T.; BRANDWAJN, A. Solutions to Queueing Systems. [S. l.], jan. 2015. Disponível em: https://bit.ly/2YqB8q0. Acesso em: 19 jan. 2021.

BIANCHI, F. Estrutura de Dados e Técnicas de Programação. Grupo GEN, 2014. 9788595152588. Disponível em: https://bit.ly/39r5pLy. Acesso em: 18 jan. 2021.

GOODRICH, M. T.; TAMASSIA, R. Estruturas de dados & algoritmos em java. 5. ed. Porto Alegre: Bookman Editora, 2013.

UNIVERSITY OF SAN FRANCISCO. Queue (Linked List Implementation). USF Computer Science, [s. d.]. Disponível em: https://bit.ly/3ovsGAj. Acesso em: 19 jan. 2021.

VISUALGO. Linked list. Visuago.net, [s. d.]. Disponível em: https://visualgo.net/en/list. Acesso em: 19 jan. 2021.