#include <iostream>

using namespace std;

template <typename DataType>
struct Node 
{
    DataType data;
    Node<DataType> * next;
};

template <typename DataType>
class LinkStack
{
public:
    LinkStack(); // 构造函数 初始化 链栈
    ~LinkStack(); // 析构函数 销毁链栈
    void Push(DataType x); // 入栈操作,将元素x入栈
    DataType Pop(); // 出栈操作,将栈顶元素出栈
    DataType GetTop(); // 取出栈顶元素,不删除
    void Empty(); // 判空
private:
    Node<DataType> * top; // 栈顶指针 
};

// 初始化
template <typename DataType>
LinkStack<DataType>:: LinkStack()
{
    top = new Node<DataType>; // 生成栈顶指针结点
    top->next = nullptr;
}

// 析构函数 链栈的销毁
template <typename DataType>
LinkStack<DataType> :: ~LinkStack( )
{
    Node<DataType> *q;
    while (top != NULL)        //释放链栈的每一个结点的存储空间
    {
        q = top;                 //暂存被释放结点
        top = top->next;         // top指向被释放结点的下一个结点
        delete q;    
    }
}

// 入栈操作,将元素x入栈
template <typename DataType>
void LinkStack<DataType>:: Push(DataType x)
{
    Node<DataType> * s = nullptr;
    s = new Node<DataType>;
    s->data = x;
    s->next = top;
    top = s;
}

// 出栈操作,将栈顶元素出栈
template <typename DataType>
DataType LinkStack<DataType>:: Pop()
{
    Node<DataType> * p = nullptr;
    DataType x;
    if (top == nullptr) throw "下溢";
    x = top->data;
    p = top;
    top = top->next;
    delete p;
    return x;
}

// 取出栈顶元素,不删除
template <typename DataType>
DataType LinkStack<DataType>:: GetTop()
{
    if (top == nullptr) throw "栈顶为空";
    else return top->data;
}

// 判空
template <typename DataType>
void LinkStack<DataType>:: Empty()
{
    if (top == nullptr) cout << "栈为空" << endl;
    else cout << "栈不为空" << endl;
}

int main()
{
    LinkStack<int> S{ }; // 定义栈
    cout << "1 和 2 入栈";
    S.Push(1);
    S.Push(2);

    cout << "当前栈顶元素位: " << S.GetTop() << endl;

    int x;
    try 
    {
        x = S.Pop(); // 出栈
        cout << "出栈操作,出来的元素是: " << x << endl; 
    }
    catch (char *str)
    {
        cout << str << endl;
    }

    int y;
    try 
    {
        cout << "请输入待入栈元素: ";
        cin >> y;
        cout << "待入栈元素为: " << y << endl;
        S.Push(y); // 进栈
    }
    catch (char *str)
    {
        cout << str << endl;
    }

    S.Empty();

    return 0;
}