Fila de Prioridade

CÓDIGO-FONTE: https://github.com/r-bauer/prioQueue/archive/master.zip

Como explicado na postagem anterior(Fila Circular), um problema singular ocorre quando se cria um tipo de dado abstrato como a fila usando vetores, aonde inserir e remover elementos continuamente desloca os dados por  toda a memória, como solução utiliza-se um buffer circular, em um segundo caso quando criamos uma fila com lista encadeada, a mesma sofre de uma deficiência ligeiramente diferente em seu formato, continuar criando e apagando nós da lista, acabara por fragmentar a memória com as sucessivas operações de alocar e liberar.

No caso da fila com lista encadeada temos duas soluções para o problema:

1.       Usar funções próprias para alocar e devolver a memória, esta função iria alocar uma sequencia de nós que seriam usados e devolvidos.

2.       Criar uma lista encadeada de nós livres, conforme os itens foram inseridos, os nós são movidos da lista livre para a fileira, ao remover, os nós retornam para a lista livre.

Será utilizada a abordagem numero 2, as rotinas de lista encadeada a serem utilizadas, foram introduzidas anteriormente na postagem lista encadeada genérica parte 1 e parte 2. Para os arquivos de aplicação qapp.c e qapp.h, teremos a adaptação da lista ligada para uma fila, semelhante à forma com que se trabalhou com os arquivos llapp.c e llapp.h.

Uma lista ordenada será usada para representar a fila de prioridade, utilizando uma lista ordenada ascendente, implica numa alteração do processo de inserção, aonde abandonamos o FIFO (First In, First Out) para colocar o elemento na posição indicada para sua prioridade, a rotina insere fica responsável em manter a ordem enquanto a rotina remove mantém sua simplicidade ao remover o primeiro da fila, em termos de desempenho o processo de inserção requer uma media de aproximadamente n/2 nós para inserção e apenas um nó para eliminação.

typedef struct tagSNODEDATA {       char *pText;                 // ponteiro para um texto       unsigned int uiPriority;     // o nivel de prioridade }SNODEDATA;

A vantagem de uma lista sobre vetor para programar a fila de prioridade reside no fato de que não é necessário nenhum deslocamento de dados, um item pode ser inserido numa lista sem deslocar os demais, enquanto que a mesma operação num vetor fica impossível se não houver espaços vazios.

A estratégia para o programa se inicia com a criação de duas estruturas de lista encadeada slQueue e slFreeList no arquivo qdriver.c.

SLIST *slQueue, *slFreeList;     // configura a estrutura de lista ligada para filas     slQueue = CreateLList(  CreateData1,                             DeleteData1,                             DuplicatedNode,                             NodeDataCmp1 );     slFreeList = CreateLList(   CreateData2,                                 DeleteData2,                                 DuplicatedNode,                                 NodeDataCmp2 );

Antes de detalhar as rotinas especificas de cada lista, é importante ressaltar que toda a memória usada será criada pela lista livre e compartilhada pelas duas listas, o que resulta na criação de todos os nós pela lista livre no seguinte trecho.

for (iCount = 0; iCount < QMAX; ++iCount)     {         AddNodeAtHead(slFreeList, cRecord);     }

A consequência desta lógica acaba com as rotinas CreateData1 e DeleteData1 jamais sendo executadas no código, com suas declarações sendo vazias no arquivo qapp.c.

void *CreateData1(void *data) {     return (NULL); } BOOL  DeleteData1(void *data) {     return TRUE; }

O mesmo acontece para tratamento de elementos duplicados , apesar de incluir a rotina DuplicateNode, a mesma não é chamada por nenhuma das duas listas, mantendo sua declaração apenas com fim de compatibilidade, ambas as listas compartilham a mesma rotina.

int   DuplicatedNode(SLINK slkNewNode, SLINK slkListNode) {     return 2; }

A única operação especifica para a lista slQueue será a comparação dos nós através do valor de prioridade para posicionar na fila.

int   NodeDataCmp1(void *first, void *second) {     return (((pND)first)->uiPriority - ((pND)second)->uiPriority); }

Como a lista slFreeList fica responsável por gerar e apagar o nós, CreateData2 e DeleteData2 serão as únicas rotinas com a tarefa de alocar e liberar.

void *CreateData2(void *data) {     SNODEDATA *pNewData;     // aloca sua estrutura de dados     pNewData = (SNODEDATA *) malloc(sizeof(SNODEDATA));     // move os valores para a estrutura de dados     pNewData->uiPriority = 0;     pNewData->pText = (char *) malloc(TEXT_SIZE + 1);     *pNewData->pText = '\0';     return (pNewData);     // retorna o endereco da estrutura } BOOL  DeleteData2(void *data) {     // SNODEDATA consiste em: um ponteiro e um inteiro.     // Sendo nescessario liberar a string manualmente     free( ((pND) data)->pText);     // e somente agora libera SNODEDATA     free(  data );     return TRUE; }

Com a adaptação das rotinas especificas de lista encadeada para uso com a fila de prioridade, monta-se o controlador de fila, com as rotinas para inserir e remover elementos da fila.

Função	InsertQueue
Propósito	Armazenar um dado baseado em sua prioridade
Parâmetros	SLIST *slQueue - lista ligada usada para fila de prioridade SLIST *slFree - lista com as vagas livres a serem inseridas void *pNewEntry - a nova entrada a ser guardada na fila
Retorno	TRUE - dado armazenado FALSE - não foi possível armazenar o dado
Descrição	Enfileira os dados passados no inicio da lista livre, e depois adiciona o nó na lista baseada na prioridade.

BOOL InsertQueue(SLIST *slQueue, SLIST *slFree, void *pNewEntry) {     SLINK slkCurr, slkNewNode;     // existe algum noh livre na lista     if (slFree->uiCount == 0)         return (FALSE);     // usa como novo noh, o inicio da lista livre     slkNewNode = slFree->slkHead;     DataCopy(slkNewNode->pdata, pNewEntry);     // adiciona os dados numa lista vazia     if (slQueue->uiCount == 0)     {         // encontrou uma vaga, corrige a lista livre         // atualiza a o inicio da lista para o seguinte         slFree->slkHead = slFree->slkHead->next;         // ponteiros do noh = NULO por ser o primeira insercaoh         slkNewNode->prior = NULL;         slkNewNode->next = NULL;         // indica que o novo noh faz parte da lista de prioridade         slQueue->slkTail = slkNewNode;         slQueue->slkHead = slkNewNode;         slQueue->uiCount = 1;// inicia o contador da lista         --slFree->uiCount;   // retira uma vaga da lista livre         return (TRUE);     }     // jah existem dados na lista     else     {         //´percorre a lista para encontrar a posicaoh de insercaoh         for (slkCurr = slQueue->slkHead; ; slkCurr = slkCurr->next)         {             if ((slkCurr == NULL) || // se for fim da fila            // ou dentro dele            (slQueue->fNodeDataCmp(pNewEntry, slkCurr->pdata) < 0))             {                 // encontrou uma vaga, corrige a lista livre                 // atualiza a o inicio da lista para o seguinte                 slFree->slkHead = slFree->slkHead->next;                 // eh o fim da lista ?                 if (slkCurr == NULL) {                     // novo noh aponta para o fim da fila                     slkNewNode->prior = slQueue->slkTail;                       // naoh tem para quem apontar                     slkNewNode->next = NULL;                     // o seguinte do fim aponta para o novo noh                     slQueue->slkTail->next = slkNewNode;                        // indica o novo fim da lista                     slQueue->slkTail = slkNewNode;                 }                 else {                     // estah adicionando no inicio da lista ?                     if (slkCurr->prior == NULL)                         // atualiza o inicio da lista                         slQueue->slkHead = slkNewNode;                          // atualiza os ponteiro do novo noh                     slkNewNode->prior = slkCurr->prior;                           // colocando ele entre o atual e anterior                     slkNewNode->next = slkCurr;                                 // naoh estah adicionando no inicio                     if (slkCurr->prior != NULL)                         // anterior p/ referenciar o novo noh                         slkCurr->prior->next = slkNewNode;                       // ajusta o atual p/ referenciar o novo noh                     slkCurr->prior = slkNewNode;                 }                 // atualiza a contagem das lista                 // adiciona um noh na lista de prioridade                 ++slQueue->uiCount;                 // subtrai um noh da lista de livres                 --slFree->uiCount;                 return (TRUE);             }         }     } }

Função	RemoveQueue
Propósito	Retira o dado de uma fila
Parâmetros	SLIST *slQueue - lista ligada usada para fila de prioridade SLIST *slFree - lista com as vagas livres a serem inseridas  void *pOurData - o dado retirado da fila
Retorno	TRUE - recuperou a informação da fila FALSE - Fila vazia ou erro ao copiar dado para buffer
Descrição	Para remover, usa um ponteiro para o nó no inicio da fila. Move esse nó inicial retirado da fila e o insere na lista de nó livres. Obs.: Se não os dados não forem usados antes que se execute uma nova operação p/ enfileirar (insertQueue), os dados serão perdidos, portanto copie se for necessário.

BOOL RemoveQueue(SLIST *slQueue, SLIST *slFree, void *pOurData) {     SLINK slkRemove;     // existe algum dado p/ desinfilerar ?     if (slQueue->uiCount == 0)         return (FALSE);     // faz a copia dos dados desenfilerados     DataCopy(pOurData, slQueue->slkHead->pdata);     // salva a posicaoh do dado a ser retirado da fila     slkRemove = slQueue->slkHead;     // remove o noh da fila de prioridade     // atualizando o inicio p/ o seguinte da lista     slQueue->slkHead = slQueue->slkHead->next;          // se diferente de nulo, tem elemento armazenados na fila     if (slQueue->slkHead != NULL)         // eliminando a referencia de um previo         slQueue->slkHead->prior = NULL;              // se o inicio for nulo, fila foi esvaziada, atualiza o fim     else         // naoh existe dados armazenados         slQueue->slkTail = NULL;                    --slQueue->uiCount; // ajusta a contagem de itens na fila         // e adiciona no inicio da lista de livres     slkRemove->prior = NULL;          // aponta o anterior p/ NULO     // e o seguinte para o inicio da lista de livres     slkRemove->next = slFree->slkHead;     // e atualiza o inicio da lista de nohs livres     slFree->slkHead = slkRemove;          ++slFree->uiCount;  // avisa que tem + 1 noh livre     return (TRUE); }

Para testarmos o resultado, a função QDriver servirá de exemplo de tratamento para fila de prioridade, irá abrir para leitura um arquivo de dados consistindo em linhas de texto no formato X9MESSAGE, aonde:

X	I – para inserir na fila R – remover L – listar a fila
9	Prioridade do item da fila
MESSAGE	Texto a ser inserido

Obs.: A ações D e P não tem prioridade ou texto.

O arquivo texto com dados deverá ter o seguinte padrão:

I8Lacuna Coil I4Anthrax R L R I1Various I9White Zombie I2John Williams I4Killswitch Engage L I4Ayreon

O código simplificado de teste para abrir o arquivo e executar as ações que encontrar em cada linha segue abaixo.

fin = fopen(argv[1], "rt"); pTemp = CreateData2(NULL); while (fgets(cRecord, sizeof(cRecord) - 1, fin) != NULL) {       if (*cRecord == 'I')       {             ((pND) pTemp)->uiPriority = *(cRecord + 1) - '0';             ((pND) pTemp)->pText = cRecord + 2;             InsertQueue(slQueue, slFreeList, pTemp);       }       else if (*cRecord == 'R')       {             RemoveQueue(slQueue, slFreeList, pTemp);       }       else if (*cRecord == 'L')       {             SLINK slkCurr;             printf("\n- Fila -\n");             for ( slkCurr = slQueue->slkHead;                   slkCurr != NULL;                   slkCurr = slkCurr->next)             {                   printf("%d %s\n",                         ((pND) slkCurr->pdata)->uiPriority,                         ((pND) slkCurr->pdata)->pText);             }             printf("\n");       } } fclose(fin);

Os arquivos deste projeto se encontram no github: https://github.com/r-bauer/prioQueue, o arquivo prio.txt deve ser criado para ser usado no teste como indicado acima, ao rodar o programa terá como resultado: 

C:\Algorit\Projects\pqueue\Debug>pqueue PRIO.TXT         Enfilerou (1 Bryan Adams)         Enfilerou (4 KC and the Sunshine Band)         Desenfilerou (1 Bryan Adams) ----------- Fila ateh o momento ----------- 4 KC and the Sunshine Band         Enfilerou (2 Meat Loaf)         Enfilerou (1 R.E.M)         Enfilerou (9 Sugar Ray)         Desenfilerou (1 R.E.M)         Desenfilerou (2 Meat Loaf) ----------- Fila ateh o momento ----------- 4 KC and the Sunshine Band 9 Sugar Ray         Enfilerou (7 The Mission)         Enfilerou (4 Temple of the Dog)         Enfilerou (3 Pantera)         Enfilerou (1 Ministry)         Enfilerou (1 Kelly Clarkson)         Desenfilerou (1 Ministry)         Desenfilerou (1 Kelly Clarkson) ----------- Fila ateh o momento ----------- 3 Pantera 4 KC and the Sunshine Band 4 Temple of the Dog 7 The Mission 9 Sugar Ray

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