Filas

Filas
Uma fila é uma estrutura de dados que admite inserção de novos elementos e remoção de elementos antigos. Mais especificamente, uma fila (= queue) é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há mais tempo.
Em outras palavras, o primeiro objeto inserido na fila é também o primeiro a ser removido. Essa política é conhecida pela sigla FIFO (= First-In-First-Out).
Veja o verbete Queue na Wikipedia.

Implementação em um vetor

Suponha que nossa fila FIFO mora em um vetor fila[0..N-1]. Suponha que os elementos do vetor são inteiros (isso é só um exemplo; os elementos da fila poderiam ser quaisquer outros objetos). A parte do vetor ocupada pela fila será fila[ini..fim-1]. |0 | |

É conveniente tratar as células como um novo tipo-de-dados e atribuir um nome a esse novo tipo:

typedef struct cel celula;

Uma célula c e um ponteiro p para uma célula podem ser declarados assim:

celula c;

celula *p;

Se c é uma célula então c.conteudo é o conteúdo da célula e c.prox é o endereço da próxima célula. Se p é o endereço de uma célula, então p->conteudo é o conteúdo da célula e p->prox é o endereço da próxima célula. Se p é o endereço da última célula da lista então p->prox vale NULL.
[pic]

Endereço de uma lista encadeada

O endereço de uma lista encadeada é o endereço de sua primeira célula. Se p é o endereço de uma lista, convém, às vezes, dizer simplesmente
"p é uma lista".
Listas são animais eminentemente recursivos. Para tornar isso evidente, basta fazer a seguinte observação: se p é uma lista então vale uma das seguintes alternativas: • p == NULL ou • p->prox é uma