// IG17 2004-05, II17 2005-06
// Pila.h
// 17-12-2004, 16-12-2005

// Ejemplo del Tema 4: pila generica

// En la pila se insertan y extraen datos siguiendo una estrategia
// LIFO (ultimo en entrar, primero en salir). Para hacer ambas
// operaciones en tiempo O(1), basta un puntero al primer
// elemento. Cada nodo tiene un dato y un puntero al siguiente nodo.

// En esta clase, el constructor sin argumentos por defecto, el
// operador de asignacion por defecto, el constructor de copia por
// defecto y el destructor por defecto NO funcionan correctamente, por
// lo que se han implementado tambien.

// Ejercicios:
//
//  * Supongamos que un usuario tiene una clase X y crea una instancia
//    Pila<X> p, con la que ejecuta todas las funciones de la clase Pila. 
//    Piensa cuales son las funciones (incluyendo constructores y operadores)
//    de la clase X de las que se estaria haciendo uso, y donde.
//
//  * Modifica las funciones Apilar y Desapilar para que se puedan utilizar
//    haciendo, por ejemplo, p.Desapilar().Apilar(55).Apilar(77)
//
//  * Anyade una funcion Comparar(pila2) que devuelva true si las dos pilas
//    contienen los mismos datos en el mismo orden, y false si no.
//
//    Anyade un operador de comparacion (==) que haga lo mismo
//
//  * Anyade una funcion Invertir() que invierta el orden de los datos
//    en la pila.
//
//  * Modifica completamente la implementacion, cambiando la lista de nodos
//    por un vector dinamico cuya talla se duplique cuando se llene, de modo
//    que la interface de la clase siga siendo la misma.


#ifndef _PILA_GENERICA
#define _PILA_GENERICA

template <class T>
class Pila {
  struct Nodo {
    T dato;
    Nodo *sig;
    Nodo(const T &, Nodo* = NULL); // Por eficiencia, evitamos pasar T por valor
  };
  Nodo *datos;
  int talla; // Manteniendo este campo podemos ejecutar Talla() en tiempo O(1)
 public:
  Pila();
  Pila (const Pila &);
  Pila & operator= (const Pila &);
  ~Pila();
  void Vaciar();
  bool EstaVacia() const;
  int Talla() const;
  void Ver() const;
  void Apilar(const T &);
  void Desapilar();  // No hace nada si se llama con una pila vacia

  T & Tope() throw(int);
     // No modifica la pila.
     // Devuelve T por referencia para poder usarla a la izquierda
     // de la asignacion para cambiar el dato en el tope de la pila.
     // Lanza una excepcion si se llama con una pila vacia.
};

#endif