using System;

public class Program

{

    public static void Main()

    {

        // Conceito de pilha: ultimo a entrar, primeiro a sair

        //                    primeiro a entrar, ultimo a sair

        Pilha pilha = new Pilha();

        pilha.empilhar(3);

        // empilhar elementos na pilha

        Console.WriteLine("Empilhado 3");

        pilha.empilhar(7);

        Console.WriteLine("Empilhado 7");

        pilha.empilhar(1);

        Console.WriteLine("Empilhado 1");

        pilha.empilhar(5);

        Console.WriteLine("Empilhado 5");

        pilha.empilhar(6);

        Console.WriteLine("Empilhado 6");

        pilha.empilhar(9);

        Console.WriteLine("Empilhado 9");

        pilha.empilhar(4);

        Console.WriteLine("Empilhado 4");

        // a pilha já está com todos os elementos. Vamos gerar uma pilha clone

        Pilha clone = pilha.getClone();

        // agora vamos desempilhar eles. A ordem que deve ser desempilhada é 4, 9, 6, 5, 1, 7, 3.

        // ------------------- //

        // Desempilhando todos os valores com while:

        int valorDesempilhado = pilha.desempilhar();

        while(valorDesempilhado != -1){

            Console.WriteLine("Valor desempilhado: " + valorDesempilhado);

            valorDesempilhado = pilha.desempilhar();

        }

        valorDesempilhado = clone.desempilhar();

        while(valorDesempilhado != -1){

            Console.WriteLine("Valor desempilhado (pilha clone): " + valorDesempilhado);

            valorDesempilhado = clone.desempilhar();

        }

    }

    public class Celula {   // inicio da classe celula

        public int dado;        // guarda o valor

        public Celula proximo;  // guarda o elemento depois desse na ordem da pilha

        public Celula(int dado, Celula proximo){

            this.dado = dado;

            this.proximo = proximo;         

        }                   // fim da classe celula

    }

    public class Pilha {    // inicio da classe pilha

        Celula proximo;

        public bool vazia(){

            return proximo == null; 

        }

        public void empilhar(int dado){

            this.proximo = new Celula(dado, proximo); // nosso elemento do topo vai receber o dado passado pelo usuário

                                                    // e passa o proximo, para armazenar a proxima celula

        }

        public int desempilhar(){

            if(vazia()){

                return -1;  // se a pilha estiver vazia não tem como retornar o que foi desempilhado, e nem desempilhar nada

            }

            Celula aux = proximo;

            proximo = aux.proximo;  // aqui é a parte que realmente desempilha. O proximo recebe o segundo item da pilha, e o atual para de existir

            return aux.dado;

        }

        public Pilha getClone(){

            Celula aux = proximo;

            Pilha pilhaAux = new Pilha();

            while(aux != null){

                pilhaAux.empilhar(aux.dado);

                aux = aux.proximo;

            }

            // Temos nossa pilha, porém de tras para frente. Agora é só repetir o mesmo processo com a nossa auxiliar para a pilha clone

            Pilha clone = new Pilha();

            aux = pilhaAux.proximo;

            while(aux != null){

                clone.empilhar(aux.dado);

                aux = aux.proximo;

                // inverteu a pilha invertida novamente, para uma pilha clone

            }

            return clone;

        }

    }                       // fim da classe pilha

}