Pilhas

Pilhas

Filas são estruturas de dados representando uma coleção de itens de tal forma que novos itens são inseridos em um ponto da fila ( END - “fim da fila” ) e antigos itens são eliminados em um outro ponto da mesma ( START - “começo da fila” ).

Estrutura da Fila (“queue”)

As filas são denominadas FIFO (First-In First-Out).

Analogia com estacionamento de trens, proposta por E.W.Dikjstra, para ilustrar o funcionamento de uma fila.

Operações básicas que uma fila suporta:

• Enqueue: Insere um elemento no final da fila

• Dequeue: Remove um elemento do começo da fila

Operações que manipulam Filas

InicFila(q) : Faz a fila ficar vazia

Filavazia(q) : Retorna 1 se a fila q estiver vazia

Filacheia(q) : Retorna 1 se a fila q estiver cheia

Enqueue(q, x): Insere o elemento x no final da fila q

Dequeue(q) : Remove o primeiro elemento da fila,retornando o elemento como resultado da função

Operação Estado da Fila Resultado

------------------ F:[] --------------------

Enqueue(F,a) F:[a] --------------------

Enqueue(F,b) F:[a, b] --------------------

Enqueue(F,c) F:[a, b, c] --------------------

Enqueue(F,d) F:[a, b, c, d] --------------------

Dequeue(F) F:[b, c, d] a

Dequeue(F) F:[c, d] b

Enqueue(F,e) F:[c, d, e] --------------------

Enqueue(F,f) F:[c, d, e, f] --------------------

Enqueue(F,Dequeue(F)) F:[d, e, f] c

F:[d, e, f, c] --------------------

Dequeue(F) F:[e, f, c] d

Considerações sobre a implementação de Filas

Inicialmente, poderíamos criar a fila definindo o seu valor inicial como 0 e valor final –1. A fila estaria vazia sempre que q.fim < q.inic. O número de elementos dessa fila seria sempre igual ao valor de q.fim – q.inic + 1.

Com essas considerações, notamos que a fila, ao ser inicializada como vazia, tem zero elementos (-1+0+1) = 0.

Podemos observar que, à medida que se inserem elementos na fila q, q.fim é incrementado em uma posição. Na remoção é a vez de q.inic ser incrementado em uma posição. Analisando esse processo notamos que o valor de q.inic caminha em direção ao valor de q.fim, até o momento em que q.fim se torna menor que q.inic. Nesse caso, é sinalizado que a fila está vazia (q.fim < q.inic). Isso pode gerar alguns inconvenientes:

q.fim=4

q.fim=2 q.inic=q.fim=2

q.inic=0 q.inic=2

q.inic=0

q.fim=-1

(a) (b) (c) (d)

No momento d, se houver a necessidade de inserirmos mais valores no vetor que representa a fila, percebemos que não será possível, pois o elemento 50 já ocupa a última posição do vetor, contudo, existem duas posições livres (0 e 1).

Para ser resolvido esse problema utilizamos a solução de Fila Circular.

Fila Circular

A idéia é armazenar os elementos na fila como se esta fosse um círculo.

Para compreendermos essa solução, é necessário imaginar que o primeiro elemento do vetor vem logo depois do último. Isto significa que, se o último elemento estiver ocupado, um novo valor poderá ser inserido depois dele, nesse caso, o primeiro elemento do vetor desde que esteja obviamente vazio. Podemos notar que, um elemento novo não será incluído em fila circular somente se não houver, de fato, espaço na fila.

Dessa forma, a fila passa a estar vazia quando q.inic = q.fim.

Fila.H

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define MAXFILA 100

struct queue {

int item[MAXFILA];

int inic, fim;

};

void inicFila(struct queue *pq); /*Inicializa a estrutura da fila*/

void insFila(struct queue *pq, int x); /*Insere o elemento x na fila*/

int remFila(struct queue *pq); /*Remove um elemento da fila*/

int filaVazia(struct queue *pq); /*Verifica se a fila est vazia*/

int filaCheia(struct queue *pq); /*Verifica se a fila est cheia*/

int guardainicio(struct queue *pq); /*Consulta o inicio da fila*/

void retornainicio(struct queue *pq,int x); /*Atribui o indice do primeiro elemento*/

/*Operações*/

void inicFila(struct queue *pq) /*Inicializa a estrutura da fila*/

{

pq->inic = MAXFILA-1;

pq->fim