/*
* Resolução
* Pedro Henrique de Lima Ribeiro
* ADS IFPI 2018.1
*/

#include <iostream>

using namespace std;

class No
{
  public:
    char nome;
    No *prox;

    No(char n)
    {
        nome = n;
        prox = NULL;
    }
};

class Queue
{
  public:
    No *inicio;
    No *fim;

    Queue()
    {
        inicio = NULL;
        fim = NULL;
    }

    void push(char n)
    {
        No *novo = new No(n);
        if (inicio == NULL)
        {
            inicio = novo;
            fim = novo;
        }
        else
        {
            fim->prox = novo;
            fim = novo;
        }
    }

    char pop()
    {
        char nome;
        if (inicio != NULL)
        {
            nome = inicio->nome;
            inicio = inicio->prox;
        }
        return nome;
    }
};

class StackWithQueue
{
  public:
    Queue *q;

    StackWithQueue()
    {
        q = new Queue();
    }

    void push(char letra)
    {
        Queue *auxiliar = new Queue();
        // tranfere todos os elementos para outra fila
        while (q->inicio != nullptr)
        {
            auxiliar->push(q->pop());
        }
        // Insere novo elemento
        q->push(letra);
        // Retorna todos os elementos para a lista principal
        while (auxiliar->inicio != nullptr)
        {
            q->push(auxiliar->pop());
        }
    }

    char pop()
    {
        return q->pop();
    }
};

// Main
int main()
{
    StackWithQueue *stack = new StackWithQueue();
    cout << "inserindo elementos na pilha" << endl;
    cout << "Primeiro: A\n";
    stack->push('A');
    cout << "Segundo: B\n";
    stack->push('B');
    cout << "Terceiro: C\n";
    stack->push('C');

    cout << "\nRemovendo elementos da pilha" << endl;
    cout << "Primeiro: " << stack->pop() << endl;
    cout << "segundo : " << stack->pop() << endl;
    cout << "terceiro: " << stack->pop() << endl;

    return 0;
}