quinta-feira, 20 de junho de 2013

Fila Circular

Em sua forma mais simples a fila é uma estrutura de dados fácil de programar, entretanto, percebe-se rapidamente que a aparente simplicidade esconde algumas complicações.

 Como a questão da representação na memória, pode-se representar a fila como um vetor ou uma lista encadeada, no primeiro caso um problema singular ocorre, se você continua adicionando elementos no fim da fila e eliminando os do inicio, os dados da fila percorrera toda a memória.

Quando se usa vetores para implementar filas, podemos contornar este problema transformando em um vetor circular, de forma que ao acessar o ultimo elemento do vetor, continua-se a partir do primeiro, obtendo assim a fila circular, resultando na situação abaixo:

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

insert(F);
F

C
D
E


O código modifica o exemplo anterior para incluir o suporte ao buffer circular, a necessidade de indicar o status de fila cheia, as variáveis que apontam para o inicio e fim, podem apontar para a mesma posição do vetor em duas situações, quando a fila está vazia ou cheia:


Status = livre
inicio









fim





Status = cheia



inicio

F
G
H
D
E



fim



O tipo de dados abstrato fila inclui agora o status da fila

#define SIZE_QUEUE      8

#define FREE            0
#define FULL            1

typedef struct tagSQUEUE
{
      char  cBuf[SIZE_QUEUE];
      int   iIni;
      int   iEnd;
      char  cSts;
} SQUEUE;

Para a rotina que insere elementos na fila:
1.       Apenas irá armazenar se não estiver cheia.
2.       Após inserir o dado, verifica se o índice de fim passou o limite do vetor, sendo o caso reinicia o contador.
3.       Ultima verificação é para ver se o índice de fim alcançou o inicio o que caracteriza como fila cheia.

void insertQ(SQUEUE *sPtr, int iVal)
{
      if (sPtr->cSts == FULL)
            return;

      sPtr->cBuf[sPtr->iEnd++] = iVal;

      if (sPtr->iEnd >= SIZE_QUEUE)
            sPtr->iEnd = 0;

      if (sPtr->iEnd == sPtr->iIni)
            sPtr->cSts = FULL;
 }


Para remover elementos da fila:
1.       Verificamos se a fila está vazia ao analisar os indicadores de posição do inicio e fim em conjunto do status.
2.       Como feito anteriormente na rotina insere com o valor da posição final, certificamos que o valor da posição inicial não ultrapassou o limite do vetor, reiniciando a posição caso tenha alcançado o fim.
3.       Sempre que um elemento é retirado significa que existe espaço livre na fila, atualiza o valor de status.

int removeQ(SQUEUE *sPtr)
{
      int iTmp;

      if (sPtr->iEnd == sPtr->iIni && sPtr->cSts == FREE)
            return -1;

      iTmp = sPtr->cBuf[sPtr->iIni++];

      if (sPtr->iIni >= SIZE_QUEUE)
            sPtr->iIni = 0;

      sPtr->cSts = FREE;

      return iTmp;  
}           


                O código abaixo repete o do ultimo exemplo, incluída uma pequena alteração nas rotinas abaixo para aperfeiçoar valendo-se do fato que o tamanho da fila permite operações de mascara de bit.

Decimal
Binário
iIni
iIni & 7
iIni
iIni & 7
6
6
0110
110
7
7
0111
111
8
0
1000
000


                Ao rodar o programa, o resultado será:

C:\Projects\CircQueue\Debug>CIRCQUEUE
        A
        A       B
                B

QUEUE EMPTY

                        C
                        C       D
                        C       D       E
                        C       D       E       F
                        C       D       E       F       G
                        C       D       E       F       G       H
        I               C       D       E       F       G       H
        I       J       C       D       E       F       G       H
QUEUE FULL
        I       J       C       D       E       F       G       H

quarta-feira, 5 de junho de 2013

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