/********************************************************

   ROT-DEQUE
   =========

   Rotinas basicas de manipulacao de DEQUES usando vetores:
   - Estruturas de dados com alocacao estatica
   - Insere no inicio da fila
   - Insere no final da fila
   - Remove do inicio da fila
   - Remove do final da fila
   
   - Fila circular

   Aplicacao tipica:
   - Filas onde temos a total liberdade de insercao e
     remocao dos elementos (Double Ended Queue)
     
   Por: Fernando Osorio
   Data da ultima atualizacao: Out. 2013

*********************************************************/

#include <stdio.h>
#include <stdlib.h>

#define MAX_DEQUE 100

#define FALSO      0
#define VERDADEIRO 1

#define OK         1
#define ERRO       0

typedef int Tipo_Dado;

typedef struct
        {
           Tipo_Dado Dado    [MAX_DEQUE];
           int       Inicio,Fim;\
           int       Qtde;
        }  Tipo_Deque;

/***

 => Rotinas de Manipulacao de Deques
    Insere: inicio/fim - Remove: inicio/fim
    Alocacao sequencial

***

void inicializa_deque    (Tipo_Deque *D);
int  insere_inicio_deque (Tipo_Deque *D; Tipo_Dado  Dado);
int  insere_final_deque  (Tipo_Deque *D; Tipo_Dado  Dado);
int  retira_inicio_deque (Tipo_Deque *D; Tipo_Dado *Dado);
int  retira_final_deque  (Tipo_Deque *D; Tipo_Dado *Dado);
void lista_deque         (Tipo_Deque *D);
int  acha_deque          (Tipo_Deque *D; Tipo_Dado Dado; int *Indice);
int  cheio_deque         (Tipo_Deque *D);
int  vazio_deque         (Tipo_Deque *D);
int  quantidade_deque    (Tipo_Deque *D);
int  apaga_deque         (Tipo_Deque *D);

***/

void inicializa_deque (D)
Tipo_Deque *D;
{
  D->Inicio=0;
  D->Fim=0;
  D->Qtde=0;
}

int insere_inicio_deque (D,Dado)
Tipo_Deque *D;
Tipo_Dado Dado;
{
  int ant,prox;

  if (D->Qtde == MAX_DEQUE)    /* Deque cheio ? */
     return(ERRO);
  else
  {
     if (D->Qtde==0)           /* 1o. elemento */
     {
        prox=D->Fim+1;
        if (prox == MAX_DEQUE)
           prox=0;
        D->Fim=prox;
     }
     
     ant=D->Inicio-1;
     if (ant < 0)
        ant=MAX_DEQUE-1;
        
     D->Dado[D->Inicio]=Dado;
     D->Inicio=ant;

     (D->Qtde)++;
     
     return(OK);
  }
}

int insere_final_deque (D,Dado)
Tipo_Deque *D;
Tipo_Dado Dado;
{
  int ant,prox;

  if (D->Qtde == MAX_DEQUE)    /* Deque cheio ? */
     return(ERRO);
  else
  {
     if (D->Qtde==0)           /* 1o. elemento */
     {
        ant=D->Inicio-1;
        if (ant < 0)
           ant=MAX_DEQUE-1;
        D->Inicio=ant;
     }

     prox=D->Fim+1;
     if (prox == MAX_DEQUE)
        prox=0;

     D->Dado[D->Fim]=Dado;
     D->Fim=prox;

     (D->Qtde)++;
     
     return(OK);
  }
}

int retira_inicio_deque (D,Dado)
Tipo_Deque *D;
Tipo_Dado *Dado;
{
  if (D->Qtde == 0)    /* Deque vazio? */
     return(ERRO);
  else
  {
     (D->Inicio)++;
     if (D->Inicio == MAX_DEQUE)
        D->Inicio=0;
        
     *Dado= D->Dado[D->Inicio];
     
     (D->Qtde)--;
     if (D->Qtde == 0)
        D->Fim=D->Inicio;
        
     return(OK);
  }
}

int retira_final_deque (D,Dado)
Tipo_Deque *D;
Tipo_Dado *Dado;
{
  if (D->Qtde == 0)     /* Deque vazio? */
     return(ERRO);
  else
  {
     (D->Fim)--;
     if (D->Fim < 0)
        D->Fim=MAX_DEQUE-1;
        
     *Dado= D->Dado[D->Fim];
     
     (D->Qtde)--;
     if (D->Qtde == 0)
        D->Inicio=D->Fim;
        
     return(OK);
  }
}

void lista_deque (D)
Tipo_Deque *D;
{
   int cont;

   printf("\n");
   if (D->Qtde != 0)
   {
      cont=D->Inicio;
      for ( ; ; )
      {
         cont++;
         if (cont == MAX_DEQUE)
            cont=0;
         if (cont == D->Fim)
            break;
         printf("Deque[%d]=%d\n",cont,D->Dado[cont]);
      }
   }
   printf("\n");
}

int acha_deque (D,Dado,Indice)
Tipo_Deque *D;
Tipo_Dado Dado;
int *Indice;
{
  /* Que tal praticar um pouco a programacao em "C"... */
  /* Faca voce mesmo! */
  printf("\n>> Nao implementada <<\n");
}

int cheio_deque (D)
Tipo_Deque *D;
{
  if (D->Qtde == MAX_DEQUE)
     return(OK);
  else
     return(!OK);
}

int vazio_deque (D)
Tipo_Deque *D;
{
  if (D->Qtde == 0)
     return(OK);
  else
     return(!OK);
}

int quantidade_deque (D)
Tipo_Deque *D;
{
   return(D->Qtde);
}

void apaga_deque (D)
Tipo_Deque *D;
{
  D->Inicio=0;
  D->Fim=0;
  D->Qtde=0;
}

/* Programa Principal */

main()
{
  Tipo_Deque Deque;
  int Valor;
  int Indice;
  int opcao;

  inicializa_deque(&Deque);

  for ( ; ; )
  {
    printf("\n>>> ROTINAS DE MANIPULACAO DE DEQUES <<<\n\n");
    printf("1 - Insere dado no inicio\n");
    printf("2 - Insere dado no final\n");
    printf("3 - Remove dado do inicio\n");
    printf("4 - Remove dado do final\n");
    printf("5 - Lista o conteudo\n");
    printf("6 - Procura por um dado\n");
    printf("7 - Verifica se esta cheio\n");
    printf("8 - Verifica se esta vazio\n");
    printf("9 - Exibe quantidade de elementos\n");
    printf("10- Apaga todos os dados\n");
    printf("0 - FIM\n\n");
    printf("Opcao: ");
    scanf("%d",&opcao);

    switch(opcao)
    {
       case 0: break;
       case 1: printf("Valor: ");
               scanf ("%d",&Valor);
               insere_inicio_deque(&Deque,Valor);
               system("pause");
               break;
       case 2: printf("Valor: ");
               scanf ("%d",&Valor);
               insere_final_deque(&Deque,Valor);
               system("pause");
               break;
       case 3: if (retira_inicio_deque(&Deque,&Valor))
                  printf("Retirado - Valor: %d\n",Valor);
               else
                  printf("Nao foi possivel retirar dado do deque...\n");
               system("pause");
               break;
       case 4: if (retira_final_deque(&Deque,&Valor))
                  printf("Retirado - Valor: %d\n",Valor);
               else
                  printf("Nao foi possivel retirar dado do deque...\n");
               system("pause");
               break;
       case 5: printf("Lista dos dados no deque:\n");
               lista_deque(&Deque);
               system("pause");
               break;
       case 6: acha_deque(&Deque,Valor,&Indice);
               system("pause");
               break;
       case 7: if (cheio_deque(&Deque))
                  printf("=> Deque cheio!\n");
               else
                  printf("=> Deque com espaco livre\n");
               system("pause");
               break;
       case 8: if (vazio_deque(&Deque))
                  printf("=> Deque vazio!\n");
               else
                  printf("=> Deque com dados inseridos\n");
               system("pause");
               break;
       case 9: printf("=> Quantidade de dados: %d\n",quantidade_deque(Deque));
               system("pause");
               break;
       case 10: printf("=> Dados do deque apagados...\n");
                apaga_deque(&Deque);
                system("pause");
                break;
       default: printf(">> Opcao invalida!\n");
                system("pause");
    }
    
    if (opcao == 0) break;

  }

  printf("\nFIM.\n");
  system("pause");
}