Filas

                Uma fila é uma lista linear de informações, que leva a associar ao funcionamento de um vetor devido a tal semelhança, entretanto o que diferencia uma fila de um vetor, é a forma com que se consegue o dado, para acessar itens nesta lista, obedece à regra de ordem na qual o primeiro a entrar, será o primeiro a sair, conhecido como FIFO (First In, First Out), no mundo real existem diversos exemplos, como fila no banco ou no ponto de ônibus, reiterando que a diferença com vetor está em NÂO permitir o acesso randômico a nenhum item especifico.

Ao enumerar as regras a serem seguidas, temos apenas duas, podem-se eliminar itens em uma extremidade (inicio) e podem-se inserir itens na outra extremidade (fim), para tanto duas operações serão utilizadas, insert() e remove(). Imagine a seguinte sequencia de comandos:

legenda
	inicio
	fim

insert(A);

A

insert(B);

A

B

insert(C);

A

B

C

x = remove();

B

C

insert(D);

B

C

D

insert(E);

B

C

D

E

y = remove();

C

D

E

Em termos de código, a implementação do tipo de dado fila em C será representada através de um vetor para armazenar os elementos da fila e duas variáveis para apontar as posições de inicio e fim dos dados dentro do vetor.

#define SIZE_QUEUE              0x10 typedef struct tagSQUEUE {         char cBuf[SIZE_QUEUE];         int         iIni;         int         iEnd; } SQUEUE;

O próximo trecho de código não faz nenhuma verificação de segurança por questão de simplificar a apresentação das rotinas, evidentemente que usar um vetor para armazenar uma fila introduz a possibilidade para estouro (overflow) ao inserir itens alem do tamanho limite ou retirar um item invalido (underflow) de uma fila vazia.

void insert(SQUEUE *sPtr, int wVal) {     sPtr->cBuf[sPtr->iEnd++] = wVal; } int remove(SQUEUE *sPtr) {     return sPtr->cBuf[sPtr->iIni++]; }

                O exemplo completo segue abaixo, aonde mimetiza a explicação dada:

#include <stdio.h> // DEFINICOES PARA FILAS #define SIZE_QUEUE              10 typedef struct tagSQUEUE {        char   cBuf[SIZE_QUEUE];        int          iIni;        int          iEnd; } SQUEUE; // ROTINAS PARA FILAS void insertQ(SQUEUE *sPtr, int wVal) {        if (sPtr->iEnd >= SIZE_QUEUE) {              fprintf(stderr, "OVERFLOW\n");              return;        }        sPtr->cBuf[sPtr->iEnd++] = wVal; } int removeQ(SQUEUE *sPtr) {        if (sPtr->iEnd == sPtr->iIni) {              fprintf(stderr, "UNDERFLOW\n");              return -1;        }        else              return sPtr->cBuf[sPtr->iIni++]; }            void displayQ(SQUEUE *sPtr) {        int i;        for (i = 0; i < SIZE_QUEUE; i++) {              if (i >= sPtr->iIni && i <= sPtr->iEnd)                     printf("\t%c", sPtr->cBuf[i]);              else                     printf("\t ");        }        printf("\n"); } void main(void) {        SQUEUE sQueue = { '\0', 0, 0 };        insertQ(&sQueue, 'A');            displayQ(&sQueue);        insertQ(&sQueue, 'B');            displayQ(&sQueue);        insertQ(&sQueue, 'C');            displayQ(&sQueue);        removeQ(&sQueue);                 displayQ(&sQueue);        insertQ(&sQueue, 'D');            displayQ(&sQueue);        insertQ(&sQueue, 'E');            displayQ(&sQueue);        removeQ(&sQueue);                 displayQ(&sQueue); }

                Irá resultar em:

C:\Projects\Queue\Debug>queue         A         A       B         A       B       C                 B       C                 B       C       D                 B       C       D       E                         C       D       E

                Caso deseje testar os limites da fila, condicionais foram incluídas para evitar um erro grave e imprimem na tela o aviso, alterando a rotina main() como indicado a seguir.

insertQ(&sQueue, 'A');       insertQ(&sQueue, 'B');       removeQ(&sQueue);       removeQ(&sQueue);       removeQ(&sQueue);       insertQ(&sQueue, 'C');       insertQ(&sQueue, 'D');       insertQ(&sQueue, 'E');       insertQ(&sQueue, 'F');       insertQ(&sQueue, 'G');       insertQ(&sQueue, 'H');       insertQ(&sQueue, 'I');       insertQ(&sQueue, 'J');       insertQ(&sQueue, 'K');

                As mensagens de erro indicam seus respectivos casos.

C:\Projects\Queue\Debug>queue UNDERFLOW OVERFLOW