Estruturas de Dados em linguagem C – Parte II: Filas

Assim como a pilha, a fila também é uma estrutura de dados bem simples. Na pilha, os elementos são acessados somente pelo topo: o último elemento a entrar é o primeiro a sair. O funcionamento da fila, ao contrário da pilha, é descrito pela sigla FIFO (first in, first out). Os elementos são sempre inseridos/empilhados no final da fila e exluídos/desempilhados no início da fila. A estrutura fila nada mais é do que uma analogia ao conceito de fila que usamos normalmente. Ou seja, numa fila a ordem de saída é relativa à ordem de chegada (a “fila” do RU não entra neste caso, podemos descrevê-la como uma lista, uma outra estrutura de dados que será abordada futuramente nesta sequência de posts).

Um exemplo de fila na computação é a fila de impressão. Quando temos um computador ligado a uma impressora ao mandarmos imprimir os arquivos, eles vão para uma fila de impressão e assim impressos de acordo com a ordem.

Exemplo do funcionamento de uma fila:

I) Fila inicial contendo 7 posições, e apenas 5 elementos.

II) Push(9) – Empilha elemento 9, que passa a ser o último

III )Pop() – Desempilha o elemento 5, e o elemento 3 passa a ser o primeiro

IV) Push(2) – Empilha elemento 2, que passa a ser o último

Vou seguir a dica do Tarsis Azevedo e mudar o estilo deste post. Irei explicar o funcionamento das filas colocando snippets dos códigos, mas o código também será disponibilizado no Github.

O primeiro exemplo é a fila estática, na qual a quantidade de elementos é fixa.

Bibliotecas e Struct:

#include "stdafx.h"
#include <stdio.h>;
#include <stdlib.h>;
#define N 50

typedef struct fila {
float info[N];
int n;
int ini;
}Fila;

Funções:

Fila *criarFilaVazia(){
Fila *f = (Fila*)malloc(sizeof(Fila));
f->n=0;
f->ini=0;
return f;
}

int estaVazia(Fila *f){
return(f->ini==0 && f->n==0);
}

void push(Fila *f, float v){
if(f->n==N){
printf("\nCapacidade da fila esgotada.\n");
return;
}else{
f->info[f->n]=v;
f->n++;
}
}

float pop(Fila *f){
float v;
if(vazia(f)){
printf("\nFila vazia.\n");
}else{
v = f->info[f->ini];
f->ini++;
}
return v;
}

void liberar(Fila *f){
free(f);
}

void imprimir(Fila *f){
int i;
for(i=f->ini;i<f->n;i++)
printf("\n%.2f",f->info[i]);
printf("\n");
}

O segundo exemplo é a fila estática circular. Assim como na fila estática “normal”, aqui a quantidade de elementos também é fixa. Porém, como nossa fila tem tamanho fixo e só podemos excluir/desempilhar do início chegará uma hora que o último elemento também será o primeiro, e o que fazemos com as posições que ficaram livres sem ter que ficar deslocando todos os elementos sempre? Usaremos o incremento circular. Basta incrementar o valor do índice atual e fornecer o índice incrementado de forma circular. Assim podemos inserir nas posições que ficaram livres no início da nossa fila. Exemplo:

Para conseguir realizar o incremento circular será alterada a nossa Struct para:

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#define N 100

struct fila {
int ini, fim;
float vet[N];
}

E vamos usar as funções abaixo:

Fila* criaFilaVazia(void){
Fila* f = (Fila*) malloc(sizeof(Fila));
f->ini = f->fim = 0;
return f;
}

int incremento(int i){
return (i+1)%N;
}

void push(Fila* f, float v){
if (incremento(f->fim) == f->ini) {
printf("Capacidade da fila estourou.\n");
exit(1);
}

f->vet[f->fim] = v;
f->fim = incremento(f->fim);
}

float pop(Fila* f){
float v;
if (vazia(f)) {
printf("Fila vazia.\n");
exit(1);
}
v = f->vet[f->ini];
f->ini = incr(f->ini);
return v;
}

int vazia (Fila* f){
return (f->ini == f->fim);
}

void libera (Fila* f){
free(f);
}

O nosso terceiro e último exemplo se trata da fila dinâmica na qual os elementos são inseridos dinamicamente usando uma lista, ou seja, não há uma quantidade fixa de elementos.

Bibliotecas e Structs:

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>

typedef struct nolista{
float info;
struct nolista* prox;
}Nolista;

struct Fila{
Nolista* ini;
Nolista* fim;
};

Funções:

Fila* criarFilaVazia(void) {
Fila *f= (Fila*)malloc(sizeof(Fila));
f->ini = f->fim = NULL;
return f;
}

void push(Fila* f, float v) {
Nolista* n = (Nolista*)malloc(sizeof(Nolista));
n->info = v;
n->prox = NULL;
if(f->fim != NULL)
f->fim->prox = n;
else
f->ini = n;
f->fim = n;
}

int estaVazia(Fila* f) {
return (f->ini == NULL);
}

float pop(Fila* f) {
Nolista* t;
float valor;
if(estaVazia(f)){
printf("Fila vazia!");
exit(1);
}
t = f->ini;
valor = t->info;
f->ini = t->prox;
if(f->ini == NULL)
f->fim = NULL;
free(t);
return valor;
}

float verPrimeiroElemento (Fila* f) {
return (f->ini->info);
}

void liberarFila(Fila* f) {
Nolista* q = f->ini;
while(q != NULL){
Nolista* t = q->prox;
free(q);
q = t;
}
free(f);
}

void imprimir(Fila* f){
Nolista* q;
for(q = f->ini; q!= NULL; q = q->prox)
printf("%.2f\n", q->info);
}

Todo os exemplos de código acima foram extraídos de uma solução completa que está disponível no Github.

No próximo post darei continuidade a esta série sobre estrutura de dados escrevendo um pouco sobre listas, que correspondem a uma sequência ordenada de elementos do mesmo tipo podendo ser estáticas, dinâmicas, encadeadas, duplamente encadeadas e circulares.

This entry was posted on segunda-feira, fevereiro 21st, 2011 at 7:37 AM and is filed under C . You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 responses to “Estruturas de Dados em linguagem C – Parte II: Filas”

Ater Fernandes Ferrari

25th fev, 11

Ótimo artigo minha amiga Andressa. Muito bem escrito e desenvolvido!!!

Vale lembrar, também, que pilhas, filas e arvores esão no top da programação para sistemas computacionais, pois geram eficiência e uma organização coerente, possibilitando um melhor desempenho dos programas.

Parabéns pelo artigo.
at
Ater Fernandes Ferrari

25th fev, 11

“estão” e não esão hehe. sorry.
at
Spidey

29th set, 11

Dá pra misturar os dois modos, fazer uma fila circular sem usar ponteiros, só controlando o índice de início e o tamanho da fila.
Programação é massa por isso, o mesmo problema pode ser resolvido de várias formas, e SEMPRE alguém vai pensar e fazer de forma diferente. Mesmo que essa outra forma não seja melhor que a sua, para um próximo problema pode ser, daí o ponto interessante da interação entre os programadores.
at
Andressa Agnhesi

29th set, 11

Concordo Cláudio! Visões diferentes sempre tem, por isso é importante a troca de informações e conhecimentos. Acaba forçando o jeito de pensar e melhorando bastanteˆˆ
at

Andressa Agnhesi

Pesquisar

Posts Recentes

Comentários

Twitter