第1次上机作业：
（1）分别给出顺序栈和链式栈的定义与实现。

//顺序栈
#include <iostream>
using namespace std;

template <class T>
class Stack{
public:
    Stack(int MaxStackSize=10);
    ~Stack() { delete [] stack;}
    bool IsEmpty() const {return top==-1;}
    bool IsFull() const {return top==MaxTop;}
    T Top() const;
    Stack<T>& Push(const T& x);
    Stack<T>& Pop(T& x);
    void Clear(){top=-1;} //清空栈
private:
    int top;//栈顶
    int MaxTop;//最大的栈顶值
    T *stack;//堆栈元素数组
};

template<class T>
Stack<T>::Stack(int MaxStackSize)
{
    MaxTop=MaxStackSize-1;
    stack=new T[MaxStackSize];
    top=-1;
}

template<class T>
Stack<T>& Stack<T>::Push(const T& x)
{
    if(IsFull()) {
        cout<<"no memory;"<<endl;
        return *this;
    }
    top=top+1;
    stack[top]=x;
    return *this;
}

template<class T>
Stack<T>& Stack<T>::Pop(T& x)
{
    if(IsEmpty()) {
        cout<<"no element"<<endl;
        return *this;
    }
    x=stack[top];
    top=top-1;
    return *this;
}

template<class T>
T Stack<T>::Top() const
{
    if(IsEmpty())
    {
        cout<<"no element"<<endl;
        return *this;
    }
    return stack[top];
}

int main()
{
    Stack<int> data;
    int a=0;
    cin>>a;
    while(a!=0)
    {
        data.Push(a);
        cin>>a;
    }

    while(!data.IsEmpty())
    {
        data.Pop(a);
        cout<<a<<" ";
    }
    return 0;
}

//链式栈
#include <iostream>
using namespace std;

template<class T>
class Node;

template <class T>
class LinkedStack
{
    Node<T> * top;
    public:
        LinkedStack();                      //初始化一个空栈
        bool IsEmpty();                     //判断非空
        void Clear();                       //清空元素
        LinkedStack<T> & Push(const T &);   //压入元素
        LinkedStack<T> & Pop(T& x);        //弹出栈顶元素
        LinkedStack<T> & Top(T& x);        //获取栈顶元素
};

template<class T>
class Node
{
    friend class LinkedStack<T>;
    private:
        T         data;     //数据
        Node<T> * link;     //下一个节点
};

//初始化一个空栈
template<class T>
LinkedStack<T>::LinkedStack()
{
    top= nullptr;

}

//判断栈是否是空的
template <class T>
bool LinkedStack<T>::IsEmpty()
{
    if(top!= nullptr) return false;
    else return true;
}

//从栈顶弹出一个数据
template <class T>
LinkedStack<T>& LinkedStack <T> :: Pop(T& x)
{
    if(IsEmpty())
    {
        cout<<"no element"<<endl;
        return *this;
    }
    Node<T> *p=top;
    x = p->data;
    top = top ->link;
    delete p;
    return *this;
}

//从栈顶获取一个数据
template <class T>
LinkedStack<T>& LinkedStack <T> :: Top(T& x)
{
    if(IsEmpty())
    {
        cout<<"no element"<<endl;
        return *this;
    }
    x = top->data;
    return *this;
}

//向栈顶压入一个数据
template <class T>
LinkedStack<T> & LinkedStack < T> :: Push(const T &  x)
{
    Node<T> *p;
    p = (Node<T> *) new Node<T>;
    p->data=x;
    p->link=top;
    top=p;
    return *this;
}

//清空栈
template<class T>
void LinkedStack<T>::Clear()
{
    Node<T> *next;
    while(top){
        next=top->link;
        delete top;
        top=next;
    }
}

int main()
{
    LinkedStack<int> data1;
    int a = 0;
    cin>>a;
    while(a!=0)
    {
        data1.Push(a);
        cin>>a;
    }
    while(!data1.IsEmpty())
    {
        data1.Pop(a);
        cout<<a<<" ";
    }

    return 0;
}

（2）编码实现单链表反转算法。 如果使用到栈，请使用作业（1）中自己定义的，不要用STL的。

#include <iostream>
#include "MyStack.h"
using namespace std;

struct Node {
    Node(int x)
    {
        value = x;
        next = nullptr;
    }
    int value;
    Node* next;
};

/*
TODO:链表倒置的算法
 */
Node* Reverse(Node* x)
{
    LinkedStack<Node *> temp;
    while(x)
    {
        temp.Push(x);
        x=x->next;
    }
    Node * result;
    temp.Pop(result);
    x=result;
    while(!temp.IsEmpty())
    {
        temp.Pop(x->next);
        x=x->next;
    }
    x->next=nullptr;
    return result;
}

void print(Node* node)
{
    while (nullptr != node) {
        cout << node->value << " ";
        node = node->next;
    }
}
int main()
{
    int iNum;
    cin >> iNum;
    Node* a = nullptr;
    Node* pTemp;

    for (int i = 0; i < iNum; i++) {
        int tmp;
        cin >> tmp;
        if (i == 0) {
            a = new Node(tmp);
            pTemp = a;
        } else {
            pTemp->next = new Node(tmp);
            pTemp = pTemp->next;
        }
    }

    cout << "倒置前为：";
    print(a);
    cout << endl;
    Node* r = Reverse(a);
    cout << "倒置后为：";
    print(r);
    cout << endl;
    return 0;
}