#include <iostream>
using namespace std;

template <class T>
class Node
{
public:
    T data;
    Node *next;
    Node () { }
    Node (T d, Node *p): data(d), next(p) { }
};

template <class T>
class LinkStack
{
private:
    Node<T> *top;    
public:
    LinkStack(): top(NULL) { }
    
    ~LinkStack() {makeEmpty(top); }
/*    
    LinkStack(LinkStack<T> &L) 
    {
        cpy(this, L.top);
    }
    
    void cpy(LinkStack<T> *s, Node<T> *x)
    {
        if(x->next) cpy(s, x->next);
        s->Push(x->data);
    } 
*/    
    void Push(const T &x) //
    {
        top = new Node<T>(x, top);
    }
    
    bool Pop(T &x) //
    {
        if(IsEmpty()) return false;
        
        getTop(x);
        Node<T> *d = top;
        top = top->next;
        delete d;
        return true;
    }
    
    bool getTop(T &x) const //
    {
        if(IsEmpty()) return false;
        x = top->data;
        return true;
    }
    
    bool IsEmpty() const { return (top == NULL) ? true : false; } //ok
    
    int getSize() const //ok
    {
        int ret = 0;
        for(Node<T> *p = top; p; p = p->next)
            ret++;
        return ret;
    }
    
    void makeEmpty(Node<T> *p) //
    {
        if (p) makeEmpty(p->next);
        delete p;
    }
    
    void output() //
    {
        Node<T> *temp = NULL;
        
        while(!IsEmpty()) 
        {
            T t;
            if(Pop(t)) cout << t << " ";
            temp = new Node<T> (t, temp);
        }
        cout << endl; 
        top = temp;
    }
};