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 | ini | fim | N-1 | |||||||
x = fila[ini++];
fila[fim++] = y;
Isso equivale ao par de instruções "x = fila[ini]; ini += 1;", nesta ordem. É claro que você só deve fazer isso se tiver certeza de que a fila não está vazia. Para inserir(= insert = enqueue) um objeto y na fila basta fazerfila[fim++] = y;
Note como a coisa funciona bem mesmo quando a fila está vazia. É claro que você só deve inserir um elemento na fila se ela não estiver cheia; caso contrário a fila transborda(transbordar = to overflow). Em geral, a tentativa de inserir em uma fila cheia é uma situação excepcional, que indica um mau planejamento lógico do seu programa.
Veja mais: http://www.ime.usp.br/~pf/algoritmos/aulas/fila.html
