#include<iostream>

using namespace std;

template<class T>

struct Node

{

    T data;

    Node<T> *next;

};

template <class T>

class LinkStack

{

private:

    Node<T> *top;

public:

    LinkStack(){top=NULL;}

    ~LinkStack();

    void Push(T x);

    void Pop();

    T GetTop();

    int StackEmpty();

    void ClearStack();

    void StackTranverse();

};

template<class T>

LinkStack<T>::~LinkStack()

{

    Node<T> * q;

    while(top)

    {

        q=top;

        top=top->next;

        delete q;

    }

}

/****************链栈的入栈*******************/

template<class T>

void LinkStack<T>::Push(T x)

{

    Node<T> * s;

    s=new Node<T>;

    s->data=x;

    s->next=top;

    top=s;

}

/*************链栈的出栈***********************/

template<class T>

void LinkStack<T>::Pop()

{

    Node<T> *p;

    if(top==NULL) throw "underflow";

    p=top;

    top=top->next;

    cout<<p->data<<"已经被删除"<<endl;

    delete [] p;

}

/*****元素X入栈********/

template<class T>

T LinkStack<T>::GetTop()

{

    return top->data;

}

/**********判断栈是否为空************/

template<class T>

int LinkStack<T>::StackEmpty()

{

    if(top->next==NULL)

        return ;

    return ;

}

/****************清空栈********************/

template<class T>

void LinkStack<T>::ClearStack()

{

    Node<T> * q;

    while(top)

    {

        q=top;

        top=top->next;

        delete q;

    }

}

/********************遍历输出栈中元素************/

template<class T>

void LinkStack<T>::StackTranverse()

{

    Node<T> * temp;temp=top;

    while(temp)

    {

        cout<<temp->data<<" ";

        temp=temp->next;

    }

    cout<<endl;

}