[Curso de AeED - Aula 16] - Filas - Variações

1- Fila dupla


A estrutura de dados que chamamos de fila dupla consiste numa fila na qual é possível inserir novos elementos em ambas as extremidades, no início e no fim. Conseqüentemente, permite-se também retirar elementos de ambos os extremos. É como se, dentro de uma mesma estrutura de fila, tivéssemos duas filas, com os elementos dispostos em ordem inversa uma da outra.

A interface do tipo abstrato que representa uma fila dupla acrescenta novas funções para inserir e retirar elementos. Podemos enumerar as seguintes 

criar uma estrutura de fila dupla;


  1. Inserir um elemento no início;
  2. Inserir um elemento no fim;
  3. Retirar o elemento do início;
  4. Retirar o elemento do fim;
  5. Verificar se a fila está vazia;
  6. Liberar a fila.



O arquivo fila2.h, que representa a interface do tipo, pode conter o seguinte código:

typedef struct fila2 Fila2;

Fila2* cria (void);
void insere_ini (Fila2* f, float v);

void insere_fim (Fila2* f, float v);
float retira_ini (Fila2* f);
float retira_fim (Fila2* f);

int vazia (Fila2* f);
void libera (Fila2* f);

A implementação dessa estrutura usando um vetor para armazenar os elementos não traz grandes dificuldades, pois o vetor permite acesso randômico aos elementos, e fica como exercício.

Exercício: Implementar a estrutura de fila dupla com vetor.

Obs: Note que o decremento circular não pode ser feito de maneira compacta como fizemos para incrementar. Devemos decrementar o índice de uma unidade e testar se ficou negativo, atribuindo-lhe o valor N-1 em caso afirmativo.


2- Implementação de fila dupla com lista

A implementação de uma fila dupla com lista encadeada merece uma discussão mais detalhada. A dificuldade que encontramos reside na implementação da função para retirar um elemento do final da lista. Todas as outras funções já foram discutidas e poderiam ser facilmente implementadas usando uma lista simplesmente encadeada. No entanto, na lista simplesmente encadeada, a função para retirar do fim não pode ser implementada de forma eficiente, pois, dado o ponteiro para o último elemento da lista, não temos como acessar o anterior, que passaria a ser o então último elemento.

Para solucionar esse problema, temos que lançar mão da estrutura de lista duplamente encadeada (veja a seção 9.5). Nessa lista, cada nó guarda, além da referência para o próximo elemento, uma referência para o elemento anterior: dado o ponteiro de um nó, podemos acessar ambos os elementos adjacentes. Este arranjo resolve o problema de acessarmos o elemento anterior ao último. Devemos salientar que o uso de uma lista duplamente encadeada para implementar a fila é bastante simples, pois só manipulamos os elementos das extremidades da lista.
O arranjo de memória para implementarmos a fila dupla com lista é ilustrado na figura abaixo:



O nó da lista duplamente encadeada para armazenar valores reais pode ser dado por:

struct no2 {
float info;

struct no2* ant;
struct no2* prox;

};
typedef struct no2 No2;

A estrutura da fila dupla agrupa os ponteiros para o início e o fim da lista:
struct fila2 {

No2* ini;
No2* fim;

};

Interessa-nos discutir as funções para inserir e retirar elementos. As demais são praticamente idênticas às de fila simples. Podemos inserir um novo elemento em qualquer extremidade da fila. Portanto, precisamos de duas funções auxiliares de lista: para inserir no início e para inserir no fim. Ambas as funções são simples e já foram exaustivamente discutidas para o caso da lista simples. No caso da lista duplamente encadeada, a diferença consiste em termos que atualizar também o encadeamento para o elemento anterior. Uma possível implementação dessas funções é mostrada a seguir. Essas funções retornam, respectivamente, o novo nó inicial e final.

/* função auxiliar: insere no início */

No2* ins2_ini (No2* ini, float v) {

No2* p = (No2*) malloc(sizeof(No2));
p->info = v;
p->prox = ini;

p->ant = NULL;
if (ini != NULL)       /* verifica se lista não estava vazia */

ini->ant = p;
return p;

}

/* função auxiliar: insere no fim */
No2* ins2_fim (No2* fim, float v) {

No2* p = (No2*) malloc(sizeof(No2));

p->info = v;
p->prox = NULL;

p->ant = fim;
if (fim != NULL)       /* verifica se lista não estava vazia */

fim->prox = p;
return p;

}


Uma possível implementação das funções para remover o elemento do início ou do fim

é    mostrada a seguir. Essas funções também retornam, respectivamente, o novo nó inicial e final.

/* função auxiliar: retira do início */
No2* ret2_ini (No2* ini) {

No2* p = ini->prox;
if (p != NULL)       /* verifica se lista não ficou vazia */

p->ant = NULL;
free(ini);

return p;
}

/* função auxiliar: retira do fim */
No2* ret2_fim (No2* fim) {

No2* p = fim->ant;
if (p != NULL)       /* verifica se lista não ficou vazia */

p->prox = NULL;
free(fim);

return p;
}

As funções que manipulam a fila fazem uso dessas funções de lista, atualizando os ponteiros ini e fim quando necessário.

void insere_ini (Fila2* f, float v) {
f->ini = ins2_ini(f->ini,v);

if (f->fim==NULL)     /* fila antes vazia? */
f->fim = f->ini;

}

void insere_fim (Fila2* f, float v) {
f->fim = ins2_fim(f->fim,v);

if (f->ini==NULL)     /* fila antes vazia? */
f->ini = f->fim;

}

float retira_ini (Fila2* f) {

float v;
if (vazia(f)) {

printf("Fila vazia.\n");
exit(1);                     /* aborta programa */

}
v = f->ini->info;

f->ini = ret2_ini(f->ini);
if (f->ini == NULL)       /* fila ficou vazia? */

f->fim = NULL;
return v;

}

float retira_fim (Fila2* f) {
float v;

if (vazia(f)) {
printf("Fila vazia.\n");

exit(1);                     /* aborta programa */
}

v = f->fim->info;
f->fim = ret2_fim(f->fim);

if (f->fim == NULL) /* fila ficou vazia? */ f->ini = NULL;

return v;
}


[Curso de AeED - Aula 16] - Filas - Variações [Curso de AeED - Aula 16] - Filas - Variações Reviewed by Vinicius dos Santos on 09:19:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!