 |
| Cinema queue, por: Mean Mr Mustard (CC BY-SA 2.0) |
Querendo aprender sobre as estruturas de dados conhecidas como filas ou FIFO? Então pegue sua ficha, assente-se confortavelmente no sofá e aguarde sua vez. Claro, você também pode clicar no "Continuar lendo", mas aí acaba com o clima da coisa.
Índice - Estruturas de dados
1 - Lista encadeada
2 - Pilha
3 - Fila
4 - Árvore binária
Definição da fila e operações
Se pelo nome você ainda não adivinhou, o outro nome desta estrutura deve dar uma luz: FIFO, First In First Out; o primeiro a entrar é o primeiro a sair. Bem, essa é a política da fila, mas o que há de desafiador nisso? Apesar de parecer mais fácil do que a pilha a nível conceitual, há algumas pegadinhas às quais precisamos prestar atenção. Vamos a ela quando formos implementar uma fila na linguagem C.
A ideia básica aqui é que uma fila seja composta por uma variável que aponte para o começo da fila (quem está "de próximo") e para a posição do próximo a entrar na fila. O meio onde estão os dados em si pode ser um vetor, na implementação estática — ou seja, memória fixa —, ou uma lista encadeada, na implementação dinâmica.
 |
| Na ilustração, temos uma variável front para indicar o próximo elemento a ser retirado. Todas as entradas são feitas ao final da fila. |
Utilizaremos as seguintes operações:
- Inicializar nova fila;
- Verificar se fila está cheia;
- Verificar se fila está vazia;
- Inserir elemento ao final da fila;
- Remover elemento do começo da fila.
Implementação estática
Antes de qualquer coisa, precisamos tomar algumas decisões de projeto. Nossa estrutura de fila será um vetor com duas variáveis auxiliares: uma para indicar a posição do elemento no início e outra para indicar a posição do próximo elemento que entrar. Após inserir um novo elemento na fila, incrementamos o apontador do fim; após remover um elemento da fila, incrementamos o apontador do início.
Parece ótimo, mas aí entra um probleminha. Note que, como na pilha, não estamos excluindo elementos da fila. Eles continuam lá, só não precisamos mais deles, então na prática temos muitos espaços inutilizados. Considere, por exemplo, a fila:
Realizamos uma operação de remover:
Quando chegarmos à situação em que fim = N, realmente podemos dizer que a pilha está cheia? Ora, basta "dar a volta" e utilizar o espaço destinado ao elemento 1, já fora da fila. Esse "dar a volta" é feito através de uma fila circular, que faz uso da aritmética modular para aumentar a eficiência da estrutura. Mas aí temos outro problema: se fim = N não é a condição de fila cheia, então qual é? Uma solução muito prática é adicionar um contador, o que torna também fácil verificar se a fila está vazia.
Ufa, tudo isso para implementar uma mísera fila! Agora sim podemos botar a mão na massa. Já que discutimos tanto, acredito que seja mais útil colocar o código na íntegra e ao final comentar algumas coisinhas.
#include <stdio.h>
#define SIZE 50
#define OBJ_ERRO -1
typedef int tipoElem;
typedef struct {
int ini, fim, cont;
tipoElem v[SIZE];
} Fila;
Fila novaFila() {
Fila f;
f.ini = 0;
f.fim = 0;
f.cont = 0;
return f;
}
int filaVazia(Fila *f) {
return(f->cont == 0);
}
int filaCheia(Fila *f) {
return(f->cont == SIZE);
}
void inserir(Fila *f, tipoElem elem) {
if(!filaCheia(f)) {
f->v[f->fim] = elem;
f->fim = (f->fim + 1) % SIZE;
f->cont++;
} else printf("Overflow\n");
}
tipoElem remover(Fila *f) {
if(!filaVazia(f)) {
tipoElem elem = f->v[f->ini];
f->ini = (f->ini + 1) % SIZE;
f->cont--;
return elem;
} else return OBJ_ERRO;
}
Simples, não? A aritmética modular entra em ação quando inserimos e removemos elementos. Como já dito nesta introdução à teoria dos números, sempre que pensamos em fenômenos periódicos, os ciclos, estamos tratando de aritmética modular. Em um relógio de 12 horas, se agora são 9 horas e passam-se 4 horas, que horas são exibidas?
A resposta é 1, claro. Sempre que passamos das 12 horas, damos uma volta no ciclo e portanto começamos tudo de novo. Como 9 + 4 = 13, que equivale a 12 horas + 1, concluímos que deve ser 1 hora agora. Fizemos uma rotação completa e fomos um pouquinho além até 1 hora. Note as implicações: em um sistema circular, consideramos apenas os restos das divisões. Isso porque o resto da divisão de 13 por 12 é 1, o de 14 é 2, e por aí vai.
 |
| By Spindled at en.wikipedia [CC-BY-SA-3.0], from Wikimedia Commons |
O que fizemos no código seguiu o mesmo raciocínio. Ao invés de fazermos f->fim = f->fim + 1, calculamos de forma circular com f->fim = (f->fim + 1) % SIZE. Na prática, se SIZE = 12 e fim = 11, colocamos o próximo elemento na posição 11 e agora fim aponta para a posição (11 + 1) % 12 = 12 % 12 = 0. Que coisa, voltamos ao início!
Implementação dinâmica
Aqui é necessário que o leitor tenha conhecimentos de listas encadeadas, então se ainda não conhece aproveite agora para conhecer. Nossa implementação funciona em cima de uma lista encadeada com início e fim. Não complique as coisas pensando em heads e tails, apenas considere que o início é um ponteiro apontando para a próxima célula da fila e fim um ponteiro que aponta para a última:
#include <stdio.h>
#include <stdlib.h>
#define OBJ_ERRO -1
typedef int tipoElem;
typedef struct cel {
tipoElem dado;
struct cel *prox;
}Celula;
typedef struct {
Celula *ini;
Celula *fim;
}Fila;
Nada mais óbvio, certo? Bem, existem outras soluções, muito provavelmente mais eficientes, mas acredito que esta seja mais didática e fácil de entender. A inicialização segue sem problemas:
Fila* novaFila() {
Fila *f = (Fila*)malloc(sizeof(Fila));
f->ini = NULL;
f->fim = NULL;
return f;
}
Por definição, se a primeira célula é nula, então a fila está vazia:
int filaVazia(Fila *f) {
return(f->ini == NULL);
}
O método de remover não é tão diferente do que já estamos acostumados a fazer em estruturas dinâmicas, consistindo em criar um novo ponteiro que armazenará a célula a ser removida e atualizando a primeira célula da fila.
tipoElem remover(Fila *f) {
if(!filaVazia(f)) {
Celula *removida = f->ini;
tipoElem dado = removida->dado;
f->ini = removida->prox;
if(filaVazia(f))
f->fim->prox = NULL;
free(removida);
return dado;
} else return OBJ_ERRO;
}
Atente apenas para a condição: if(filaVazia(f)), seguida da instrução f->fim->prox. Por que fizemos isso? Isso foi devido a algumas decisões de projetos necessárias para o método inserir, descrito a seguir:
void inserir(Fila *f, tipoElem elem) {
Celula *nova = (Celula*)malloc(sizeof(Celula));
nova->dado = elem;
nova->prox = NULL;
if(filaVazia(f))
f->ini = nova;
else
f->fim->prox = nova;
f->fim = nova;
}
Depois de criarmos uma nova célula, verificamos se a fila está vazia. Em caso afirmativo, sabemos que a nova célula corresponde ao primeiro da fila. Vamos supor que essa primeira célula tenha sido 'alpha'. Após as condições, fica evidente que 'alpha' é também o último elemento da fila, estando ele sozinho na estrutura. Mas será que faz sentido para os próximos elementos?
Agora queremos inserir uma célula 'beta' logo a seguir de 'alpha'. Como 'alpha' é o atualmente o último elemento da lista, precisamos que a próxima célula depois de 'alpha' seja justamente 'beta':
f->fim->prox = nova;Ao término, claro, o fim deve ser a célula que acabamos de inserir, 'beta'. Não foi uma análise muito rigorosa do algoritmo, mas espero que tenha conseguido entender por que funciona e como o raciocínio pode ser prosseguido continuamente. Agora você já consegue explicar aquela condição no método remover? Tente aí!
if(filaVazia(f))
f->fim->prox = NULL;
PS: Denominações comuns das funções de inserção e remoção são enqueue e dequeue, respectivamente.
Aplicações e exercícios
O exemplo mais evidente e comumente citado é a fila de impressão. O sujeito está desesperado e começa a imprimir um monte de documentos, mas a impressora vai imprimi-los na ordem que foram requisitados. Você também já deve ter ouvido falar de uma coisinha chamada buffer, certo? É possível notá-lo quando você aperta várias teclas e o PC de repente trava; quando volta ao normal, as informações são digitadas na ordem em que foram digitadas.
Óbvio, há várias ocasiões nas quais pode ser muito útil manter uma fila para cadastrar e consultar dados. Note que poderia ser muito complicado simplesmente usar um vetor, pois precisaríamos ficar sempre lembrando e recalculando onde encontram-se o próximo e último elementos. Para isso, vamos upar alguns levels de skill com filas!
- Talvez já tenha percebido, mas não costumo tomar todos os passos recomendados na linguagem C porque prefiro deixar a lógica simples e geral. Entretanto, o que acontece quando não podemos mais armazenar elementos na fila dinâmica — ou seja, ela está cheia? Altere a função inserir pensando nisso.
- Ainda na questão de alocação de memória, escreva uma função que delete todas as células de uma fila dinâmica, sem se esquecer de liberar a memória alocada.
- Tente realizar outras implementações de fila do seu jeito. Por exemplo, uma fila estática sem um contador ou uma fila estática não-circular.
- Um deque é parecido com uma fila, mas os elementos podem ser removidos e inseridos em ambos os extremos (início e fim). Implemente-o.
Aplicação: Você deve ler um conjunto de caracteres de tamanho arbitrário, sendo terminado por um '\n' (tecla ENTER). A cada caractere inserido, coloque-o na fila; se o caractere em questão for um '*', você deve realizar uma operação de remoção. Na saída, imprima os resultados das remoções na ordem em que foram chamados. Por exemplo:
OL*A MU**NDO *C*RUEL****
A saída deve ser OLA MUNDO. Fonte do exercício: http://www.cs.princeton.edu/courses/archive/spr01/cs126/exercises/adt.html
Fontes
queue - Dictionary of Algorithms and Data Structures
Estruturas de dados em linguagem C - Parte II: Filas
Estruturas de dados: Filas
Queue (abstract data type) - Wikipedia
Postagens
0 comentários:
Postar um comentário