#include<iostream>
#include<assert.h>
using namespace std;


struct linkNode
{
    int data;
    linkNode *link;
    linkNode(linkNode *pre=NULL):link(pre){}
    linkNode(int d,linkNode *pre=NULL):link(pre),data(d){}

};

class linkedStack
{
public:
    linkedStack():top(NULL){}
    ~linkedStack(){makeEmpty();};
    void Push(const int &x);
    bool Pop(int &x);
    int getTop(int &x)const;
    bool isEmpty()const {return (top==NULL)?true:false;}
    int getSize()const;
    void makeEmpty();
    void output();
private:
    linkNode *top;
};

void linkedStack::makeEmpty()
{
    linkNode *p;
    while(top!=NULL)
    {
        p=top;
        top=top->link;
        delete p;
    }
}

void linkedStack::Push(const int &x)
{
    top=new linkNode(x,top);
    assert(top!=NULL);
}

bool linkedStack::Pop(int &x)
{
    if(isEmpty()==true) return false;
    linkNode *p=top;
    top=top->link;
    x=p->data;
    delete p;
    return true;
}

int linkedStack::getTop(int &x)const
{
    if(isEmpty()==true) return false;
    x=top->data;
    return x;
}

int linkedStack::getSize()const
{
    linkNode *p=top;
    int i=0;
    while(p!=NULL)
    {
        p=p->link;
        i++;
    }
    return i;
}

void linkedStack::output()
{
    linkNode *p=top;
    while(p!=NULL)
    {
        cout<<p->data<<endl;
        p=p->link;
    }
}


int menu()
{
    int choice;

    cout<<"*************鏈式棧的基本操作************"<<endl<<endl;
    cout<<"插入結點，請按1"<<endl;
    cout<<"刪除結點，請按2"<<endl;
    cout<<"返回棧頂元素的值，請按3"<<endl;
    cout<<"求棧的元素個數，請按4"<<endl;
    cout<<"清空棧的元素，請按5"<<endl;
    cout<<"打印棧的元素，請按6"<<endl;
    cout<<"退出，請按7"<<endl<<endl;
    cout<<"*****************************************"<<endl<<endl;

    cout<<"請選擇:";
    cin>>choice;
    return choice;
}

int main()
{
    linkedStack obj;
    bool exit=false;
    while(true)
    {
        int choice=menu();
        switch(choice)
        {
        case 1:
            int s;
            cout<<"請輸入要推入元素的數據域:";
            cin>>s;
            obj.Push(s);break;
        case 2:
            int x;
            cout<<"請任意輸入一個數:";
            cin>>x;
            cout<<obj.Pop(x)<<endl;break;
        case 3:
            int y;
            cout<<"請任意輸入一個數,用做返回棧頂元素的容器:";
            cin>>y;
            cout<<obj.getTop(y)<<endl;break;
        case 4:
            cout<<obj.getSize()<<endl;break;
        case 5:
            obj.makeEmpty();break;
        case 6:
            obj.output();break;
        case 7:
            exit=true;break;
        }
        if(exit==true)
            break;
    }
    return 0;
}