#include <iostream>
#include <string>
#include <assert.h>

template <typename T> 
  class stack
  { protected:
  
      struct entry
      { T value;
        entry * next;
        entry(T, entry *); };
  
      entry * end;
  
    public:
  
      stack();
      bool empty();
      void add(T);
      T take(); };

template <typename T> 
  stack <T> :: entry :: entry(T v, entry * prev)
  { value = v;
    next = prev; }

template <typename T> 
  stack <T> :: stack()
  { end = NULL; }

template <typename T> 
  bool stack <T> :: empty()
  { return end == NULL; }

template <typename T>
  void stack <T> :: add(T v)
  { end = new entry(v, end); }

template <typename T>
  T stack <T> :: take()
  { assert(end != NULL);
    T v = end->value;
    entry * old_end = end;
    end = end->next;
    delete old_end;
    return v; }

void main()
{ stack <string> ss;
  stack <int> si;

  ss.add("one");
  si.add(1);
  ss.add("three");
  si.add(3);
  ss.add("five");
  ss.add("seven");
  ss.add("nine");
  si.add(5);
  si.add(7);
  ss.add("eleven");
  ss.add("thirteen");
  si.add(9);
  si.add(11);
  si.add(13);

  while (! ss.empty())
    cout << ss.take() << " ";
  cout << "\n";

  while (! si.empty())
    cout << si.take() << " ";
  cout << "\n"; }