Filas em C - Como Programar (Tutorial de C sobre Queue - Estrutura de Dados)

Neste Tutorial de C de nossa apostila online, vamos falar sobre uma importante estrutura de dados dinâmica, que é a fila.

Junto com as listas encadeadas e as pilhas em C, formam o conjunto de estrutura de dados mais importantes e usados.

• Download do curso: Apostila C Progressivo

Curso de Programação em C, online e com CERTIFICADO! Clique e Obtenha o seu!

Filas em C - Tutorial de Queue

As filas (queue, em inglês) são um tipo de estrutura dinâmica de dados onde os elementos (ou nós) estão arranjados em lista que obedece as seguintes regras:
- Ao inserir um nó, ele vai para a última posição da estrutura
- Ao retirar um nó, é tirado o primeiro elemento da estrutura

Este tipo de estrutura de dados é dita ser FIFO (First in, first out), ou seja, o primeiro elemento a entrar na estrutura é o primeiro a sair.

O nome fila, por si só, já é auto-explicativo.
Imagine uma fila de banco. A primeira pessoa que chegou na fila, é a que vai ser atendida primeiro.
E se chegar mais alguém? Ela vai demorar mais pra ser atendida.
E se chegar uma outra? Ela será a última a ser atendida, pois quem está na sua frente é atendido antes.

Ou seja, sempre que inserimos elementos nessa fila, inserimos ao final.
E sempre que retiramos, estamos tirando o primeiro elemento da fila (o mais antigo), pois o que está na frente que vai sair antes.

Resumindo: inserimos ao fim, e retiramos do começo.
Diferente das pilhas em C (stack), onde colocamos no fim e retiramos do fim.

Simples, não?
Vamos entender agora a lógica para programar uma fila em C, do zero.

Filas em C - Como Programar a Estrutura de Dados

Função main(), opcao() e menu()

Ok, agora que já sabemos o que é uma fila e como funciona, vamos começar a implementar essa estrutura de dados em C, partindo do zero, apenas baseado no que sabemos da definição de FIFO.

Inicialmente criamos uma struct chamada Node, que é vai criar os nós de nossa estrutura de dados.
Vamos colocar nela um inteiro, o "num" para armazenar um valor qualquer inserido pelo usuário.
Obrigatoriamente, temos que inserir nessa struct um ponteiro de seu próprio tipo.

Vamos chamar esse ponteiro de "prox" pois ele vai servir para apontar para o próximo nó da estrutura.
Caso esse ponteiro aponte para NULL, é porque seu nó é o último da fila ou a fila está vazia.

De resto, a função principal main() simplesmente fica chamando (em um looping do while) a função menu(), que simplesmente exibe as opções possíveis para se trabalhar com a fila em C.

Depois que o usuário escolhe o que fazer, sua escolha é enviada para a função opcao(), que usa um teste condicional do tipo switch para invocar a função correta.

Função aloca() e inicia()

Inicialmente, criamos um ponteiro para a struct Node, é o "FILA", e ele é a representação de nossa estrutura de dados do tipo fila.
Seu inteiro não importa, a função deste ponteiro é definida pelo seu ponteiro "prox".

O vetor "prox" aponta pro primeiro elemento da fila, e caso ele não exista, a fila está vazia e "prox" aponta para NULL.
Fazemos isso na função inicia(), que inicializa a fila fazendo: FILA->prox = NULL

Devemos sempre lembrar de alocar memória para cada nó de nossa fila, o que é feito pela função aloca().

Função vazia()

No decorrer de nosso programa sobre estrutura de dados do tipo fila, muitas vezes será necessário checar se a fila está vazia ou não.

Isso é feito de uma maneira bem simples: checando o ponteiro "prox" da struct "FILA".
Se apontar pra NULL, a fila está vazia. Do contrário, tem pelo menos um elemento na fila.

Função insere()

Antes de mais nada, vamos usar a função aloca() para reservar um espaço em memória para o novo nó, o "novo". Como este novo nó será o último da fila, seu ponteiro "prox" deve apontar para NULL.
Esta foi a primeira parte do processo de se adicionar um elemento em uma fila.

A segunda parte é adicionar este novo nó ao final da fila, e para tal, devemos achar o último nó da fila.
Primeiro checamos se a fila está vazia, pois se tiver, basta colocar no novo nó em FILA->prox

Caso não esteja, criamos um ponteiro "tmp" que vai apontar para todos os elementos da fila em busca do último. Ele começa no primeiro elemento, que está em "FILA->prox".
Se "tmp->prox" apontar para NULL, o ponteiro aponta para o último da fila.
Senão, devemos seguir adiante com o ponteiro (tmp = tmp->prox) até acharmos o último elemento.

Achando, colocamos lá o novo nó, o "novo".
A variável inteira "tam" é para definir o tamanho da fila (número de nós). Usaremos este inteiro na função "exibe()", que vai exibir os elementos da fila.

Função retira()

Vamos agora retirar um elemento da fila.
E segunda a lógica deste tipo de estrutura de dados, vamos retirar o primeiro nó.

Antes de tudo, checamos se a fila não está vazia.
Se estiver, trabalho feito, pois não precisaremos retirar nó algum da estrutura de dados.

Caso a fila não esteja vazia, precisamos identificar o primeiro elemento e o segundo (na verdade, não é obrigado que exista um segundo elemento). O que precisamos fazer é que "FILA->prox" não aponte mais para o primeiro elemento, e sim para o segundo.

Vamos usar um ponteiro "tmp" para apontar para o primeiro elemento da fila: tmp = FILA->prox
Se "tmp" aponta para o primeiro elemento, então "tmp->prox" aponta para o segundo elemento ou NULL, caso a fila só tenha um nó.

Agora vamos fazer a ligação entre o ponteiro base (FILA) e o segundo elemento (ou NULL) da fila:
FILA->prox = tmp->prox

Pronto. Tiramos o primeiro elemento da jogada, pois se ninguém aponta para ele, ele não faz mais parte da estrutura de dados.
Interessante, não?

Note que declaramos a função "retira()" como sendo do tipo struct Node, pois é uma boa prática retornar o nó que retiramos, pois geralmente retiramos ele da estrutura para fazer algo, trabalhar em cima dele. Depois que retornamos ele pra função "opcao()" liberamos o espaço que havia sido alocado para ele.

Função exibe()

Esta função serve somente para mostrar os números ("num") existentes em cada nó, para você poder adicionar, retirar e ver o que vai acontecendo com a fila.
Ou seja, esta função tem mais propósitos didáticos, pra você ver as coisas realmente funcionamento na sua frente, como devem funcionar.

Basicamente pegamos um ponteiro "tmp" e fazemos ele apontar para cada um dos nós, exibindo o número. Para saber o tanto de nós existentes e a ordem, usamos a variável "tam" que é incrementada quando adicionamos nó na fila (função insere) e decrementada quando tiramos elementos da estrutura de dados (função retira).

Função libera()

Esta função simplesmente tem por objetivo ir em cada nó e liberar a memória alocada.
Para tal, usamos dois ponteiros.

Um ponteiro aponta para um nó ("atual"), e o outro ponteiro aponta para o nó seguinte ("proxNode").
Liberamos o primeiro ponteiro, ou seja, aquele nó deixa de existir.
Se tivéssemos só este ponteiro, nos perderíamos na fila.

Porém, o ponteiro que aponta para o nó seguinte da fila serve pra isso, pois agora temos o ponteiro para o próximo elemento da fila "proxNode").
Agora damos um passo pra frente, fazendo um ponteiro apontar para este próximo elemento ("atual = proxNode"), e o ponteiro próximo, para uma posição a frente ("proxNode = proxNode->prox").

E repetimos o processo até que o nó atual seja NULL (fim da fila).

Fila em C - Código Fonte Completo

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

struct Node{
 int num;
 struct Node *prox;
};
typedef struct Node node;

int tam;

int menu(void);
void opcao(node *FILA, int op);
void inicia(node *FILA);
int vazia(node *FILA);
node *aloca();
void insere(node *FILA);
node *retira(node *FILA);
void exibe(node *FILA);
void libera(node *FILA);


int main(void)
{
 node *FILA = (node *) malloc(sizeof(node));
 if(!FILA){
  printf("Sem memoria disponivel!\n");
  exit(1);
 }else{
 inicia(FILA);
 int opt;

 do{
  opt=menu();
  opcao(FILA,opt);
 }while(opt);

 free(FILA);
 return 0;
 }
}


int menu(void)
{
 int opt;

 printf("Escolha a opcao\n");
 printf("0. Sair\n");
 printf("1. Zerar fila\n");
 printf("2. Exibir fila\n");
 printf("3. Adicionar Elemento na Fila\n");
 printf("4. Retirar Elemento da Fila\n");
 printf("Opcao: "); scanf("%d", &opt);

 return opt;
}

void opcao(node *FILA, int op)
{
 node *tmp;
 switch(op){
  case 0:
   libera(FILA);
   break;

  case 1:
   libera(FILA);
   inicia(FILA);
   break;

  case 2:
   exibe(FILA);
   break;

  case 3:
   insere(FILA);
   break;

  case 4:
   tmp= retira(FILA);
   if(tmp != NULL){
    printf("Retirado: %3d\n\n", tmp->num);
    libera(tmp);
   }
   break;

  default:
   printf("Comando invalido\n\n");
 }
}

void inicia(node *FILA)
{
 FILA->prox = NULL;
 tam=0;
}

int vazia(node *FILA)
{
 if(FILA->prox == NULL)
  return 1;
 else
  return 0;
}

node *aloca()
{
 node *novo=(node *) malloc(sizeof(node));
 if(!novo){
  printf("Sem memoria disponivel!\n");
  exit(1);
 }else{
  printf("Novo elemento: "); scanf("%d", &novo->num);
  return novo;
 }
}

void insere(node *FILA)
{
 node *novo=aloca();
 novo->prox = NULL;

 if(vazia(FILA))
  FILA->prox=novo;
 else{
  node *tmp = FILA->prox;

  while(tmp->prox != NULL)
   tmp = tmp->prox;

  tmp->prox = novo;
 }
 tam++;
}


node *retira(node *FILA)
{
 if(FILA->prox == NULL){
  printf("Fila ja esta vazia\n");
  return NULL;
 }else{
  node *tmp = FILA->prox;
  FILA->prox = tmp->prox;
  tam--;
  return tmp;
 }

}


void exibe(node *FILA)
{
 if(vazia(FILA)){
  printf("Fila vazia!\n\n");
  return ;
 }

 node *tmp;
 tmp = FILA->prox;
 printf("Fila :");
 while( tmp != NULL){
  printf("%5d", tmp->num);
  tmp = tmp->prox;
 }
 printf("\n        ");
 int count;
 for(count=0 ; count < tam ; count++)
  printf("  ^  ");
 printf("\nOrdem:");
 for(count=0 ; count < tam ; count++)
  printf("%5d", count+1);


 printf("\n\n");
}

void libera(node *FILA)
{
 if(!vazia(FILA)){
  node *proxNode,
     *atual;

  atual = FILA->prox;
  while(atual != NULL){
   proxNode = atual->prox;
   free(atual);
   atual = proxNode;
  }
 }
}