Representação de Dados

  Dado - Conjunto de informação agrupadas de uma forma coerente. 
         (Por exemplo, segundo alguma relação existente entre elas).

  Nó   - (Item ou elemento) é cada um dos elementos básicos de uma
      estrutura e pode estar dividido em várias partes chamadas campos.

  Estruturas de dados básicas - Listas.

 Lista linear: é uma sequência de n >= 0 nós, a1, a2, ..., an, todos de
 um mesmo tipo. O número de elementos da lista (n) é o comprimento da lista.
 Observe que existe uma ordenação implícita:
  se n > 0 temos que:

    a1 é o primeiro nó da lista.
    an é o último nó da lista.
    se 1 < k < n 
      ak é precedido por a(k-1) e seguido por a(k+1).

  se n = 0 dizemos que a lista é vazia.
  
 Existem duas formas de se representar uma lista no computador

  - Alocação Sequêncial: Os nós de uma lista ocupam posições contíguas ou 
    igualmente distanciadas. (Vetor).

  - Alocação Ligada: A contiguidade dos nós é lógica.

  
Ex.:
  
    __________________________
   |a1|a2|_____..._________|an|                     Alocação Sequêncial
 
    _____      _____               _____ 
   |a1|__|--->|a2|__|---> ... --->|an|__|--->(Nada)   Alocação Ligada


  Operações básicas sobre listas lineares:

  - Insere(x, p, L): 
   insere x na posição p da lista L, movendo os elementos
   nas posições a partir de p, para a próxima posição. Isto é, se 
   L := a1, a2, ... , an , após a inserção temos
   L := a1, a2, ... , a(p-1), x, ap, ... , an.
   Se na lista L não existe a posição p o resultado é indefinido;

  - Localiza(x, L):  
   retorna a posição da primeira ocorrência do elemento 
   x na lista L. Se x não pertence a L então retorna 0;
   
  - Acessa(p, L): 
   retorna o elemento na posição p da lista L. Caso a L 
   não contenha o elemento p, o resultado é indefinido.

  - Remove(p, L): 
   remove o elemento p da lista. Isto é, se
   L := a1, a2, ... , an , após a remoção temos  
   L := a1, a2, ... , a(p-1), a(p+1), ... , an;

  - Conta(L): 
   retorna o número de elementos de L.

  - Primeiro(L): 
   retorna o primeiro elemento da lista L.

  - Imprime(L): 
   imprime em ordem os elementos de L.

  - Limpa(L): 
   faz com que a lista L seja uma lista vazia (n = 0)

  Outras operações possíveis:

  - Combinar   : duas ou mais listas, segundo algum critério; 
  - Quebrar    : uma lista em duas ou mais listas, também usando algum critério;
  - Classificar: os nós de uma lista, de acordo com os conteúdos de alguns de seus campos.


        Listas Lineares com disciplina de acesso.

    Listas Lineares em que as inserções, as remoções e os acessos em geral
 são feitos no primeiro e/ou no último nó são:
    Pilha ("Stack"), Fila ("Queue") e Fila Dupla ("Deque").

  (1) Pilha: É uma lista linear em que todas as inserções, as remoções e
             os acessos em geral são feitos numa só extremidade chamada topo.

remoções
    |                               
    V
   |_| <- fim (topo) <- inserções            Inserir = Empilhar ("Push Down")
   |_|                                       Remover = Desempilhar ("Pop Up")
   |_|
   |_| <- inicio (base)  


     A pilha é uma estrutura do tipo LIFO (Last In First Out), ou último 
   que foi inserido será o primeiro a ser removido.

   Exemplos da vida real:
   
    (a) Pilha de livros, pratos, etc....;
    (b) Estacionamento de trens.


  (2) Fila é uma lista linear em que todas as inserções são feitas numa 
           extremidade ("REAR") e todas as remoções e qualquer acesso em geral
           são feitos na outra extremidade ("FRONT").


  
              ____________________
remoções  -> |_|_|____________|_|_| <- inserções                    
              î                  î
            início (FRONT)      fim (REAR)
               


  A fila é uma estrutura do tipo FIFO.

  Ex.:
  
  a-) Estacionamento de trens;
  b-) Sistemas de multiprogramação;
  c-) Fila de Banco.

 (3) Fila Dupla: é  uma lista linear em que todas as inserções, as remoções
    e  acessos  em geral são feitos em ambas  as extremidades.


              ____________________
remoções  -> |_|_|____________|_|_| <- inserções 
inserções ->                        <- remoções 
              î                  î
            extremidade      extremidade
             esquerda          direita

  Ex.:  Analogia  com estacionamento de trens.



  Excessões dos casos anteriores

  (1) No caso da fila, quando quisermos dar prioridade a  um  determinado
  elemento,  podemos inseri-lo  no início  da fila; com isso obtemos  uma  
  Fila Dupla com saída  restrita. 

                ____________________
  remoções  -> |_|_|____________|_|_| <- inserções 
  inserções -> 



  (2) No caso de uma pilha quando ocorre  "overflow" podemos remover  o 
    elemento que está na base; com  isso  temos  uma Fila Dupla com
    entrada  restrita. 

                ____________________
  remoções  -> |_|_|____________|_|_| <- inserções 
                                      <- remoções 


  Representação de Listas Lineares no Computador

  Alocação Sequêncial. Os  elementos  de uma  lista linear  são armazenados  
  consecutivamente,  um  após  o  outro:
    __________________________
   |a1|a2|_____..._________|an|

  Representação da  Pilha  em  C:

...
#define _MAX_ ...
typedef int Indice;
typedef ... TipoDoElemento;

typedef struct _Pilha{
     Indice topo; /* topo = -1, quando a pilha está vazia*/
     TipoDoElemento elementos[_MAX_];
} Pilha;


/* Procedimento para inserir um elemento x na pilha S */

void Empilha( Pilha *S, TipoDoElemento x)
{
  S->topo++;
  if( S->topo == _MAX_ )
     OVERFLOW(); /* a pilha já está cheia*/
  else  
     S->elementos[S->topo] = x;
}

/* Procedimento para remover um elemento na pilha S */

void Desempilha( Pilha *S, TipoDoElemento *x )
{
  if( S->topo == -1 )
     Underflow(); /* a pilha está vazia*/
  else  
    *x = S->elementos[S->topo--];
}

   O Underflow ocorre quando  queremos  remover um elemento inexistente. 
 Em geral, não é uma condição de erro em um programa (pode até ser desejável).
   O Overflow ocorre quando queremos inserir um elemento em uma lista que 
 já está completa.


         Alocação de várias pilhas em um único Vetor

 (a) 2 pilhas

     ________________________
  ..|x|x|..|x|_____|x|_..|x|x|..
   î        î       î         î
  base1    topo1  topo2      base2


 (b) n > 2 pilhas

    Considere para cada i, 1 <= i <= n

    topo_i = topo da pilha  i ( posição do último elemento da pilha i) 
    base_i = base da pilha  i ( posição anterior a do primeiro elemento da pilha i) 


   Situação Genérica

     ________________________________________________
  ..|x|x|..|x|_______|x|_..|x|x|___________|x|_____|x|..
   î        î       î         î           î         î
  base1    topo1  base_i      topo_i     base_n    topo_n

  Inserir  um elemento x em uma pilha i:

    topo_i <- topo_i + 1;
    se  topo_i = base_{i+1}
      então overflow  na pilha i;
      senão V[topo_i] <- x;
  
  Remover um elemento da pilha i,  e colocá-lo em  x:

    se  topo_i = base_i
      então Underflow  na pilha i;
      senão x <- V[topo_i];
            topo_i <- topo_i - 1;


  Como  resolver  o overflow local ???

  Suponhamos  que ocorreu overflow na  pilha i, mas  ainda existe 
 espaço disponível em outras pilhas. Com isso temos várias possibilidades:

   (a) Encontrar  o  menor j tal  que  i < j <= n e topo_j < base_{j+1}

       - se existe tal  j, então mover as pilhas  i+1, i+2, ..., j para a 
   direita.

  (b) Encontrar  o maior j tal que 1 <= j < i e topo_j < base_{j+1}

       - se existe tal  j, então mover as pilhas  1, 2, ..., j para a 
   esquerda.

  (c) Uma outra  forma possíve,  é aproveitar que  já  iremos tratar o 
  overflow em uma pilha, e regularizar o espaço livre em  todas as pilhas.
   Ex.:  Seja free o espaço  livre no vetor V. Podemos fazer com que cada
  pilha fique  com espaço livre igual a |_ free/n _|.

 Como  inicializar os apontadores ???

   Note que coomo todas  as pilhas começam vazias temos que topo_i = base_i.
   Uma  solução possível seria fazer topo_i = base_i = 0, mas  esta solução 
  provoca muitos overflows.
   Uma solução melhor  seria considerar topo_i = base_i = (i-1)*MAX/n, 1 <= i <= n.
  neste caso as pilhas estão igualmente espaçadas.

2- Fila como tipo abstrato de dados

 Operações necessárias:

  - InicializaFila(q) : Faz q uma fila vazia. Retorna fila.
  - InsereFila(q,i)   : Insere o elemento i no fim da fila q. Retorna fila.
  - RemoveFila(q)     : Remove o primeiro elemento da fila q. Retorna fila.
  - BuscaInicio(q)    : Retorna o elemento que está no inicio da fila q.
  - FilaVazia(q)      : Retorna verdadeiro se a fila q está vazia, ou falso caso contrário

 Para toda fila q e todo elemento i devem valer:

 - FilaVazia( InicializaFila(q) ) = verdadeiro
 - FilaVazia( InsereFila(q, i) ) = verdadeiro
 - RemoveFila( InicializaFila(q) ) = erro ou underflow
 - RemoveFila( InsereFila(q, i)  ) = se FilaVazia(q) 
     então InicializaFila(q)
     senão InsereFila(q, RemoveFila(q))
 - BuscaInicio( InicializaFila(q) ) = erro
 - BuscaInicio( InsereFila(q,i) ) = se FilaVazia(q)
     então i
     senão BuscaInicio(q)


 Representação da Fila em um Vetor

 -1 0_1____________________(MAX - 1)
   |_|_|__________________|_|          FILA (inicialização)


   início = fim = -1

   início := indica a posição anterior ao último elemento removido da fila
   fim    := indica a posição do último elemento inserido na fila


 -1 0_1_____i_______________f_____(MAX - 1)
   |_|_|_____|X|X|X|...|X|X|X|____|_|          FILA (situação genérica)
 
  início = i
  fim    = f

 Overflow ocorre quando na inserção fim = MAX -1
 Underflow ocorre quando na remoção início = fim

 Em C:


#define _MAX_ ...
typedef ... TipoDoElemento
typedef int Indice
typedef struct {
                 Indice inicio, fim;
                 TipoDoElemento elementos[_MAX_];
               } TipoFila;

TipoFila fila; /* Variável global, acessível em qualquer das funções */
 
                 

/* Procedimento para inserir um elemento x na fila */

void Insere( TipoDoElemento x)
{
  fila.fim++;
  if( fila.fim == _MAX_ )
     Overflow(); /* O fim chegou a ultima posiçao do vetor*/
  else  
     S->elementos[S->topo] = x;
}

/* Procedimento para remover um elemento da fila */

void Remove( TipoDoElemento *x )
{
  if( fila.fim==fila.inicio )
     Underflow(); /* a fila está vazia*/
  else  
    *x = fila[++fila.inicio];
}