// ------------------------------------------------------------------------------------------------
// ---- Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein) ------------------------------------
// ---- Implementação de Pilhas e Filas em Vetores (Capítulo 10, Seção 10.1) ----------------------
// ------------------------------------------------------------------------------------------------
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <ctime>
using namespace std;

typedef struct pilha {
    int* vet;//pilha de inteiros
    int topo;// pilha topo
    int tam;// pilha tamanho
} pilha;

typedef struct fila {
    int* vet;//fila de inteiros
    int ini;// fila inicio
    int fim;// fila fim
    int tam;// fila tamanho
} fila;


bool Push(pilha& P, int x);
int Pop(pilha& P);
bool pilha_vazia(pilha& P);
bool pilha_cheia(pilha& P);
void pilha_create(pilha& P, int N);
void pilha_delete(pilha& P);


bool Enqueue(fila& F, int x);
int Dequeue(fila& F);
bool fila_vazia(fila& F);
bool fila_cheia(fila& F);
void fila_create(fila& F, int N);
void fila_delete(fila& F);



int main() {
    srand (time(NULL));
    int i;

    pilha P;
    pilha_create(P,10);
    cout <<"Numeros postos na PILHA com PUSH: ";
    while (!pilha_cheia(P)) {
        int x = rand()%100;
        cout << x << " ";
        Push(P, x);
    }
    cout << endl;
    cout <<"Numeros tirados da PILHA com POP: ";
    while (!pilha_vazia(P)) cout << Pop(P) << " ";
    pilha_delete(P);



    cout << endl << endl;
    fila F;
    fila_create(F,10);
    cout <<"Numeros postos na FILA com ENQUEUE:  ";
    while (!fila_cheia(F)) {
        int x = rand()%100;
        cout << x << " ";
        Enqueue(F, x);
    }
    cout << endl;
    cout <<"Numeros tirados da FILA com DEQUEUE: ";
    while (!fila_vazia(F)) cout << Dequeue(F) << " ";
    fila_delete(F);
    cout << endl;
    return 0;
}



// ------------------------------------------------------------------------------------------------
// ---- Algoritmos de PILHA -----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
bool Push(pilha& P, int x) {
    if (pilha_cheia(P)) return false;
    P.vet[++P.topo] = x;
    return true;
}

int Pop(pilha& P) {
    if (pilha_vazia(P)) {
        cout << "Pilha Vazia (estouro negativo)" << endl;
        return -1;
    }
    return P.vet[P.topo--];
}

void pilha_create(pilha& P, int N) {
    P.vet = NULL;
    P.tam = 0;
    P.topo = -1;
    if (N<=0) return;
    P.tam = N;
    P.vet = new int [N];
}

void pilha_delete(pilha& P) {
    if (P.vet==NULL) return;
    delete [] P.vet;
    P.vet = NULL;
    P.tam = 0;
    P.topo = -1;
}

bool pilha_vazia(pilha& P) {
    if (P.topo<0) return true;
    return false;
}

bool pilha_cheia(pilha& P) {
    if (P.topo>=P.tam-1) return true;
    return false;
}


// ------------------------------------------------------------------------------------------------
// ---- Algoritmos de FILA -----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
bool Enqueue(fila& F, int x) {
    if (fila_cheia(F)) return false;
    F.vet[F.fim] = x;
    if (F.fim==F.tam-1) {
        F.fim = 0;
    } else {
        F.fim++;
    }
    return true;
}


int Dequeue(fila& F) {
    if (fila_vazia(F)) {
        cout << "Fila Vazia (estouro negativo)" << endl;
        return -1;
    }
    int x = F.vet[F.ini];
    if (F.ini==F.tam-1) {
        F.ini = 0;
    } else {
        F.ini++;
    }
    return x;
}

void fila_create(fila& F, int N) {
    F.vet = NULL;
    if (N<=0) return;
    F.vet = new int [N];
    F.tam = 0;
    F.ini = 0;
    F.fim = 0;
    F.tam = N;
}

void fila_delete(fila& F) {
    if (F.vet==NULL) return;
    delete [] F.vet;
    F.vet = NULL;
    F.tam = 0;
    F.ini = 0;
    F.fim = 0;
}

bool fila_vazia(fila& F) {
    if (F.ini==F.fim) return true;
    return false;
}

bool fila_cheia(fila& F) {
    if (F.ini==F.fim+1) return true;
    if ((F.ini==0)&&(F.fim==F.tam-1)) return true;
    return false;
}