[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;
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;
- Inserir um elemento no início;
- Inserir um elemento no fim;
- Retirar o elemento do início;
- Retirar o elemento do fim;
- Verificar se a fila está vazia;
- 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;
}
Post a Comment