Fila circular

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (519 palavras )
  • Download(s) : 0
  • Publicado : 8 de outubro de 2012
Ler documento completo
Amostra do texto
Assunto: Lista Circular

“Dobrar” o vetor de forma que as suas extremidades se encontrem









Vamos modificar a implementação das operações e da estrutura utilizada para representaruma fila utilizando uma organização circular (conforme os conceitos discutidos até então);

Observe a seguinte situação (considerando uma fila normal, de tamanho N implementada sobre um vetor):
–São inseridos N elementos na fila;
– Em seguida são retirados n-2 elementos;
– Tenta-se incluir mais um elemento;

O que acontece?
– A fila acusará fila cheia! Mas há espaço no vetor!
– Isso é umproblema da regra que define a fila? Não!
– O problema decorre da forma utilizada para representar a fila: o VETOR;

Antes de mais nada, uma fila circular é uma fila e portanto suas operaçõesacontecem da seguinte forma:
– Inclusões: no final da fila;
– Retiradas: no início da fila;
– A diferença está na forma de tratar a organização física da fila. A interface é a mesma da fila tradicional.Definição Conceitual

Precisamos controlar o tamanho da Fila de outra forma !!





Funcionamento

• As condições “fila cheia” e “fila vazia” também devem ser alteradas:
• Uma fila estácheia se o campo que foi adicionado para controlar o tamanho for igual ao tamanho do vetor;
• Uma fila está vazia se o tamanho for igual a zero;

Observa-se que na fila com incremento circular aparte ocupada do vetor pode chegar a última posição.

Implementação:

• Para reaproveitar as primeiras posições livres do vetor podemos incrementar o vetor de forma “circular”.
• Se o últimoelemento da fila ocupa a última posição do vetor, inserimos os novos elementos a partir do início do vetor.



Se modificarmos a organização física da fila e a implementação de suas operações oproblema pode ser resolvido.
Vamos imaginar um “vetor dobrado” de forma que o fim do vetor se encontre com o início.

Arquivo “FilaCircular.h”

#define MAX 5

typedef struct {
int inicio;...
tracking img