[数据结构]栈之链式栈的类模板实现

栈的抽象基类的实现:(不用抽象基类也是可以的，为了使用虚函数方便）

#ifndef STACK#define STACK//栈的抽象基类template<class T>class Stack{public:Stack(){}~Stack(){}virtual void Push(const T& x)=0;virtual bool Pop(T& x)=0;virtual bool getTop(T& x)const=0;virtual bool IsEmpty()const=0;virtual bool IsFull()const=0;virtual int getSize()const=0;};#endif

链式栈模板类的具体实现：（覆盖了抽象基类中的所有纯虚函数，并增加了一些成员）

/////////////////////////#include"Stack.h"#include <iostream>#include <cstdlib>#include <cassert>using namespace std;template<class T> struct LinkNode //链表节点类 {T data;LinkNode<T>* link;LinkNode(LinkNode<T>* ptr=NULL):link(ptr){}LinkNode(const T& item,LinkNode<T>* ptr=NULL):data(item),link(ptr){} };template<class T>class LinkedStack:public Stack<T>{public:LinkedStack():top(NULL){}LinkedStack(const LinkedStack<T>& rhs);LinkedStack<T>& operator=(const LinkedStack<T>& rhs);~LinkedStack(){makeEmpty();}void Push(const T& x);bool Pop(T& x);bool getTop(T& x)const;bool IsEmpty()const{return top==NULL?true:false;}bool IsFull()const{return false;}//无意义，不可能满int getSize()const;void makeEmpty();friend ostream& operator<< <T>(ostream& out,LinkedStack<T>& rhs);//加<T>private:LinkNode<T>* top;};template<class T>void LinkedStack<T>::makeEmpty(){LinkNode<T>* p=NULL;while(top!=NULL){p=top;top=top->link;delete p;}}template<class T>void LinkedStack<T>::Push(const T& x){top=new LinkNode<T>(x,top);assert(top!=NULL);}template<class T>bool LinkedStack<T>::Pop(T& x){if(IsEmpty()) return false;LinkNode<T>* p=top;top=top->link;x=p->data;delete p;return true;}template<class T>bool LinkedStack<T>::getTop(T& x)const{if(IsEmpty()) return false;x=top->data;return true;}template<class T>int LinkedStack<T>::getSize()const{int k=0;LinkNode<T>* p=top;while(p!=NULL){++k;p=p->link;}return k;}template<class T>ostream& operator<<(ostream& out,LinkedStack<T>& rhs)//不加<T>{out<<"elements nums: "<<rhs.getSize()<<endl;LinkNode<T>* p=rhs.top;out<<"elements is: ";while(p!=NULL){out<<p->data<<" ";p=p->link;}out<<endl;return out;}template<class T>LinkedStack<T>::LinkedStack(const LinkedStack<T>& rhs){LinkNode<T>* src=rhs.top;LinkNode<T>* dest=NULL;LinkNode<T>* newNode=NULL;while(src!=NULL){newNode=new LinkNode<T>(src->data);if(dest==NULL){dest=newNode;top=dest;}else{dest->link=newNode;dest=newNode;}src=src->link;}}template<class T>LinkedStack<T>& LinkedStack<T>::operator=(const LinkedStack<T>& rhs)//copy赋值本质为：析构+copy构造函数{if(top!=NULL)//先析构，释放资源makeEmpty();LinkNode<T>* src=rhs.top;//copy构造LinkNode<T>* dest=NULL;LinkNode<T>* newNode=NULL;while(src!=NULL){newNode=new LinkNode<T>(src->data);if(dest==NULL){dest=newNode;top=dest;}else{dest->link=newNode;dest=newNode;}src=src->link;}return *this;}类的测试代码如下：

int main(int argc, char* argv[]){LinkedStack<int> s;int a=1,b=2,c=3,d=4,e=5;s.Push(a);s.Push(b);s.Push(c);s.Push(d);s.Push(e);cout<<s;s.Pop(e);cout<<s;cout<<std::boolalpha;//控制显式的bool值的显式cout<<"IsEmpty(): "<<s.IsEmpty()<<endl;cout<<"IsFull(): "<<s.IsFull()<<endl;cout<<std::noboolalpha;s.getTop(e);cout<<"getTop(): "<<e<<endl;s.makeEmpty();cout<<s;s.Push(a);s.Push(b);s.Push(c);cout<<s;LinkedStack<int> s1(s),s2;cout<<s1;s2=s1;cout<<s2;system("pause");return 0;}测试结果如下：

elements nums: 5elements is: 5 4 3 2 1elements nums: 4elements is: 4 3 2 1IsEmpty(): falseIsFull(): falsegetTop(): 4elements nums: 0elements is:elements nums: 3elements is: 3 2 1elements nums: 3elements is: 3 2 1elements nums: 3elements is: 3 2 1请按任意键继续. . .注意事项：

1.在模板类的友元函数的实现与声明时：声明的时间要加额外的参数<T>,在实现的时间时不加的。

2. 实现中采用的是无附加头结点的单链表，所以要注意拷贝时，链表要区分是否是空链表或者是第一次建立链表的情况。

3.链式栈的栈顶在链表的头部，新节点的插入和删除都是在栈顶进行的，是对栈顶元素的操作。

4.链表实现的栈是不可能满的，所以总是返回false

5.采用cout<<std::boolaapha与cout<<std::noboolaapha可显式的控制布尔值的显式方式。

，莫愁前路无知己，天下谁人不识君。