Filas

Filas

Uma fila é um conjunto ordenado de itens, na qual itens podem ser extraídos de uma extremidade (início da fila) e novos itens podem ser inseridos na outra extremidade (final da fila) .

Como os elementos são inseridos por uma extremidade e extraídos pela outra, este tipo de fila é chamado de lista FIFO (First In First Out), ou primeiro que entra é o primeiro que sai.

Na figura, A foi o primeiro elemento inserido na fila, será portanto o primeiro a sair. Novos elementos são inseridos no final da fila, ou seja, depois do elemento C. Se A for removido da fila, B passará a ser o primeiro da fila, ou o próximo a sair.

Uma pilha é uma lista LIFO (Last In First Out), ou último que entra é o primeiro que sai.

Operações primitivas com filas

As operações primitivas para lidar com filas são para inserir itens, remover itens e verificar se a fila está vazia.

Considere uma fila q e um item x, a função

insere(q, x)

insere o item x na fila q;

x = remove(q)

remove o item do início da fila;

vazia(q)

verifica se a fila está vazia.

A operação para remover itens da fila somente pode ser executada se a fila não estiver vazia, por isto a utilizada da função para verificar se a fila está vazia.

Imlementação de filas em linguagem C

Na linguagem C, uma das maneiras de implememtar uma fila é utilizando um vetor para armazenar a fila e mais duas variáveis para armazenar o início e o final da fila .

A fila estará contida no vetor, entre o índice 0 e TAM -1.

A parte do vetor ocupada por elementos na fila será vetor[Início .. Final - 1].

Declaração da fila

Poderíamos declarar uma fila q de inteiros como uma estrutura, com três campos:

#define TAM 100
struct fila {
  int inicio, final;
  int vetor[TAM];
} q;

Inicialmente é definido:

q.final = 0
q.inicio = 0

indicando a fila vazia.

Operação insere

Insere item recebido como argumento no final da fila.

void insere(struct fila *q, int x)
{
   q->vetor[q->final] = x;
   q->final = q->final +1;
}

Note que não posso inserir item na fila, caso a mesma estiver cheia, pois isto caracteriza um overflow. A condição de fila cheia é:

q.final = TAM;

Operação remove

Extrai e retorna item do início da fila.

int remove(struct fila *q)
{
   return q->vetor[q->inicio];
   q->inicio = q->inicio +1;
}

Operação vazia

Verifica se a fila está vazia.

A fila está vazia sempre que:

q.final = q.inicio 

int vazia(struct fila *q)
{
    if (q->final == q->inicio) 
        return -1;
    else
        return 0;
}

A qualquer momento, o número de elementos na fila é dado por:

q.final - q.inicio

Problemas nesta implementação de fila

Note que a fila estará contida no vetor entre o índice 0 e TAM -1. A medidas que os items forem sendo inseridos na fila, os mesmos vão ocupando as posições iniciando pelo índice 0. Do mesmo modo, cada item sendo removido da fila vai ser feito também iniciando pelo índice 0. Uma vez removido um item, esta implementação não permite ocupar a posição que este item estava.

Exercício

1. Implemente uma fila para armazenar uma lista de pessoas para serem atendidas em um balcão de atendimento. Cada vez que uma pessoa chegar para ser atendida a mesma é inserida no final da fila. Cada vez que uma pessoa for chamada para atendimento a mesma é removida do início da fila. O programa deve ficar em loop, aguardando a operação de inserir ou remover pessoas da fila, imprimindo após cada operação o status da fila.

Fila circular

Uma fila circular resolve o problema da implementação anterior, preenchendo os itens entre os índices 0 e TAM - 1 e voltando a inserir itens a partir da posição 0, se os itens do início da fila já tiverem sido removidos e a posição estiver vaga.

A fila estará contida no vetor, entre o índice 0 e TAM -1.

Entretando, na fila circular, a parte do vetor ocupada por elementos na fila será:

vetor[Início .. Final - 1] 

ou

vetor[Início .. TAM - 1] vetor[0 .. Final - 1]

Implementação da fila circular

A declaração da fila circular é idêntica a fila anterior:

#define TAM 100
struct fila {
  int inicio, final;
  int vetor[TAM];
} q;

Para a fila vazia, teremos:

q.final = q.inicio 

Para fila cheia, teremos:

q.final + 1 = q.inicio

ou

q.final + 1 = TAM  e  q.inicio = 0

Operação insere

void insere(struct fila *q, int x)
{
   if (q->final + 1 == q->inicio || q->final + 1 == TAM && q->inicio == 0) {
      printf( "\nSocorro! Fila vai transbordar!\n");
      exit(EXIT_FAILURE); 
   }
   q->vetor[q->final] = x;
   q->final = p->final +1;
   if (q->final == TAM) q->final = 0;
}

Operação remove

int remove(struct fila *q)
{
   return q->vetor[q->inicio];
   q->inicio = p->inicio +1;
   if (q->inicio == TAM) q->inicio = 0;
}

Referências

---

--Evandro.cantu (discussão) 12h16min de 30 de setembro de 2014 (BRT)

---