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, ocupam os índices entre Início e 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;

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 = p->final +1;
}

Operação remove

Extrai e retorna item do início da fila.

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

Operação vazia

Verifica se a fila está vazia.

Inicialmente é definido:

q.final = 0
q.inicio = 0

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

Referências

---

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

---