基于链式存储结构的栈

基于链式存储结构的栈和单链表几乎没差，不同的地方在链栈也是只能在一端进行存取操作，而单链表则可以在任何位置进行。单链表的建立分为前插法和后插法，前插法是将每次新插入的结点作为头，后插法是将每一次新进入的结点放在最后面。链栈的建立用前插法是很方便的。

链栈的结点类和单链表的一样：

//链栈作用在不知道栈元素多少的情况下，便于合理利用空间，不会造成浪费//没有最大MAXSIZE属性值，也没有栈溢出判断,没有头结点#pragma once#include"LinkNode.h"#include<iostream>using namespace std;template<class T>class Stack{LinkNode<T> *top;//首指针public:Stack();Stack(Stack<T> &S);~Stack();void makeEmpty();//销毁链栈LinkNode<T> * GetTop();//返回链栈的 首指针topvoid push(T elem);//进栈T pop();//出栈,这里是链栈 返回的是指向当前栈顶元素的指针(最好返回元素值)int Length();//求栈当前的大小bool isEmpty();//判链栈空void output();//一次性全部输出链栈元素,仍从栈顶出void operator= (Stack<T> &S);//复制函数};template<class T>Stack<T>::Stack(){top = NULL;//初始化 首指针为空，即为空栈}template<class T>Stack<T>::Stack(Stack<T> &S)//切记勿忘 <T>{LinkNode<T> *srcptr = S.GetTop();LinkNode<T> *destptr = top = NULL;LinkNode<T> *newNode;T elem;//临时存储变量elem = srcptr->data;newNode = new LinkNode<T>(elem);top = newNode;//此四步骤 是为了解决没有头结点 需先为当前连战的top值赋值 此后保存首指针destptr = top;srcptr = srcptr->link;//关键的一句,要不然从此和top断开 //从第二个开始循环复制while(srcptr !=NULL){elem = srcptr->data;//获取当前指针所指向的元素值newNode = new LinkNode<T>(elem);//以此元素值为参数 new出新的destptr->link = newNode;//然后放在当前链栈的后面srcptr = srcptr->link;//两个链栈指针后移一位destptr = destptr->link;}}template<class T>Stack<T>::~Stack(){makeEmpty();}template<class T>void Stack<T>::makeEmpty(){LinkNode<T> *del;while(top != NULL){del = top;//删除循环的赋值，，，del的被赋值必须是循环的top = del->link;delete del;}}template<class T>LinkNode<T> * Stack<T>::GetTop(){return top;}template<class T>void Stack<T>::push(T elem){LinkNode<T> *newNode;newNode = new LinkNode<T>(elem);//if(newNode == NULL)//return false;newNode->link = top;top = newNode;//return true;}template<class T>T Stack<T>::pop(){T elem;LinkNode<T> *del = top;top = del->link;elem = del->data;delete del;return elem;//出栈 相当于删除栈顶元素了}template<class T>int Stack<T>::Length(){LinkNode<T> *current = top;int count = 0;while(current != NULL){current = current->link;count++;}return count;}template<class T>bool Stack<T>::isEmpty(){return ((top == NULL) ? true : false);}template<class T>void Stack<T>::output(){LinkNode<T> *current = top;int count = 0;while(current != NULL){cout<<"#"<<count+1<<":"<<current->data<<endl;current = current->link;count++;}}template<class T>void Stack<T>::operator= (Stack<T> &S){//makeEmpty();//先销毁栈LinkNode<T> *srcptr = S.GetTop();LinkNode<T> *destptr = top;//其实销毁后空栈top即为NULL 无须赋值LinkNode<T> *newNode;T elem;//临时存储变量elem = srcptr->data;newNode = new LinkNode<T>(elem);top = newNode;//此四步骤 是为了解决没有头结点 需先为当前连战的top值赋值 此后保存首指针destptr = top;srcptr = srcptr->link;//从第二个开始循环复制while(srcptr !=NULL){cout<<"hello1"<<endl;elem = srcptr->data;//获取当前指针所指向的元素值newNode = new LinkNode<T>(elem);//以此元素值为参数 new出新的destptr->link = newNode;//然后放在当前链栈的后面srcptr = srcptr->link;//两个链栈指针后移一位destptr = destptr->link;}}