Aplicações de pilhas:

Verificar o balanceamento de expressões matemáticas com (), [] e {}.

Transformação de notação infixa para pósfixa.
((5+3)*2)  =  53+2*

Cálculo de expressões pósfixas.

Eliminação de recursão (ou melhor colocar a recursão explícita)
 
 1. Fatorial:    definição matemática:

                        0! = 1
                        n! = n*(n-1)!


                algoritmo recursivo:
          
                    int fat(int n){
               
                        if (n == 0) return 1;
                        else return n*fat(n-1);
                    }
		    
		com pilha
 
                    int fat(int n){
			pilha p;
			int res=1, i;
			limpa(&p);
                        while (n>0){
			   empilha(n,&p);
			   n--;
			}   
			while (!vazia(&p)){
			  desempilha(&i,&p);
			  res = res * i;
			}
			printf("%d\n", res);
                    }


 2. Fibonacci: definição matemática:

                   F(0) = 0 
                   F(1) = 1
                   F(n) = F(n-1)+F(n-2)


                algoritmo recursivo:

                    int Fib(int n){
                     
                       if (n==0) return 0;
                       else if (n==1) return 1;
                              else return Fib(n-1)+Fib(n-2);
                   }

		 Com pilha: exercício
  

Fila (Queue): É 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 (First In First Out).

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

 Fila como tipo abstrato de dados

 Operações necessárias:

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




 Representação da Fila em um Vetor


  Temos várias alternativas:

  1. O início da fila é sempre na posição 0.
     Inserções são simples. Para remover um elemento, 
     todos os elementos devem ser deslocados.

  2. O fim da fila é sempre na posição 0.
     Remoções são simples. Para inserir um elemento,
     todos os elementos devem ser deslocados.

  3. O início e o fim da fila são móveis. 
     

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


   inicio = 0
   fim = -1

   início := indica a posição do ú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|____|_|          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


 Desvantagem: podemos ter overflow com a fila vazia!
              Considere uma fila num vetor com 3 posições.
              Inserimos elementos 1, 2 e 3. Depois das inserções, 
              fim = 2 e início = 0. Removemos três elementos.
              fim = 2 e início = 3. A fila está vazia, mas fim = MAX-1
              e não é possível inserir mais elementos.  
              
                            
 Em C:


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


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

void InsereFila(TipoDoElemento x, TipoFila *F) {
  F->fim++;
  if( F->fim == _MAX_ )
     Overflow( F ); /* O fim chegou a ultima posiçao do vetor*/
		    /* pode ser que de para resolver...      */
  F->elementos[F->fim] = x;
}


/* Procedimento para remover um elemento da fila */
void Remove(TipoDoElemento *x, TipoFila *F) {
  if( F->fim == F->inicio ){
     Underflow();
    } /* a fila esta vazia*/
  else {
      F->inicio++;
      *x = F->elementos[F->inicio];
    }
}





 - Fila Circular

                  0           (MAX -1)
                  _____________
Fila Circular -> |x|...|_|x|x|x|       Situação genérica
                  î     î   
                 fim  inicio  

Em C:

#define MAX ...

typedef ... TipoDoElemento;

typedef struct{
    int inicio;     /* antes da primeira posição cheia   */
    int  fim;       /* última posição cheia              */ 
    int nelementos; /* quantidade de elementos           */
    TipoDoElemento elementos[MAX];
   } FilaCircular;



void RemoveFilaCircular(FilaCircular *F) {
  if(F->nelementos == 0 )
    Underflow();
  else { 
    F->inicio = (F->inicio + 1) % MAX;
    *x = F->elementos[F->inicio];	
    F->nelementos--;
  }
}


Qual a utilidade de 'nelementos'?
  
  Existem dois casos onde 'inicio = (fim + 1) % MAX':
   - Quando a fila esta vazia;
   - Quando a fila esta completamente cheia.

  Resolvemos isso utilizando 'nelementos'.
  Ou: - guardar em uma variavel a condição vazia.
      - deixar sempre uma posicao livre, i.e., a fila só pode ter 
         MAX-1 elementos.