栈的链接存储结构--链栈 图解和代码实现

栈的链接存储结构--链栈

链栈的图片：

LinkStack.h

//LinkStack.h#ifndef LINKSTACK_H#define LINKSTACK_Htemplate <class T>struct Node{    T data;    Node<T> *next;  //此处<T>也可以省略};template <class T>class LinkStack{public:    LinkStack( );              //构造函数，置空链栈    ~LinkStack( );             //析构函数，释放链栈中各结点的存储空间    void Push(T x);           //将元素x入栈    T Pop( );                  //将栈顶元素出栈    T GetTop( );               //取栈顶元素（并不删除）    bool Empty( );             //判断链栈是否为空栈private:    Node<T> *top;             //栈顶指针即链栈的头指针};#endif

LinkStack.cpp

//LinkStack.cpp#include "LinkStack.h"/* * 前置条件：栈不存在 * 输    入：无 * 功    能：栈的初始化 * 输    出：无 * 后置条件：构造一个空栈 */template <class T>LinkStack<T>::LinkStack( ){top=NULL; }/* * 前置条件：栈已存在 * 输    入：无 * 功    能：销毁栈 * 输    出：无 * 后置条件：释放栈所占用的存储空间 */template <class T>LinkStack<T>::~LinkStack( ){while (top){Node<T> *p;p=top->next;        delete top;        top=p;}}/* * 前置条件：栈已存在 * 输    入：节点s * 功    能：在栈顶插入该节点 * 输    出：无 * 后置条件：如果插入成功，栈顶增加了一个元素 */template<class T> void LinkStack<T>::Push(T x){    Node<T> *s;s=new Node<T>;        s->data = x;     //申请一个数据域为x的结点s    s->next = top; top=s;           //将结点s插在栈顶}/* * 前置条件：栈已存在 * 输    入：无 * 功    能：删除栈顶元素 * 输    出：如果删除成功，返回被删元素值，否则，抛出异常 * 后置条件：如果删除成功，栈顶减少了一个元素 */    template <class T> T LinkStack<T>::Pop( ){       Node<T> *p;int x;     if (top==NULL) throw "下溢";    x=top->data;            //暂存栈顶元素    p=top; top=top->next;         //将栈顶结点摘链    delete p;    return x;}/* * 前置条件：栈已存在 * 输    入：无 * 功    能：读取当前的栈顶元素 * 输    出：若栈不空，返回当前的栈顶元素值 * 后置条件：栈不变 */template <class T> T LinkStack<T>::GetTop( ){    if (top!=NULL) return top->data;}/* * 前置条件：栈已存在 * 输    入：无 * 功    能：判断栈是否为空 * 输    出：如果栈为空，返回1，否则，返回0 * 后置条件：栈不变 */template <class T> bool LinkStack<T>::Empty( ){    if(top==NULL) return 1;else return 0;}