Índice > Fila > Fila Circular

Instituto de Ciências Matemáticas de São Carlos 
Departamento de Computação e Estatística 
SCE182 - Algoritmos e Estruturas de Dados 1 
Profs. Resp.: Graça Pimentel e Maria Cristina

Fila Circular

Fila Circular Implementada como Anel

  1. Índices do array: 0 .. m-1
  2. Ponteiros de controle: Começo e Fim
  3. Inicialmente Começo = Fim = 0
  4. Quando Fim = m-1, o próximo elemento será inserido na posição 0 (se essa posição estiver vazia!)
  5. Condição de fila vazia Começo = Fim
  6. Para inserir:
    7.   Procedure Inserir (Var Fim: indice);
  Begin
  If Fim = m-1 Then
    Fim := 0 
  Else
    Fim := Fim + 1;  {ou  Fim := ( Fim + 1 ) mod m}
  End;
  7. Para eliminar um elemento
    8.   Procedure Eliminar (Var Começo: indice);
  Begin
  Começo := (Começo + 1) mod m;
  End;
Problema: Nesta representação, como teremos fila cheia ??? 
  Começo = Fim
Para resolver esse problema, utilizaremos apenas m-1 posições do anel. Deste modo, existe sempre um elemento vazio e, portanto, Fim não coincide com Começo.

O algoritmo para inserção em anel fica: 

  Procedure Inserir (Var Fim: indice; Começo: indice; F: fila);
  Begin
  If (Fim + 1) mod m = Começo Then
    {FILA CHEIA}
  Else
    Begin
      Fim := (Fim + 1) mod m;     {um registro fica vazio}
      F[Fim] := x;
    End;
  End;
O algoritmo para eliminação em anel fica: 
  Procedure Eliminar (Var Comeco: indice; Fim: indice);
  Begin
  If Começo = Fim Then 
    {FILA VAZIA}
  Else 
    Começo := (Começo + 1) mod m;
  End;

Fila