1 //Node.h  2 template<typename ElemType>  3 struct Node  4 {  5     ElemType data;  6     Node<ElemType> *next;  7     Node();  8     Node(ElemType item,Node<ElemType> * link=NULL);  9 }; 10 template<typename ElemType> 11 Node<ElemType>::Node() 12 { 13     next=NULL; 14 } 15 template<typename ElemType> 16 Node<ElemType>::Node(ElemType item,Node<ElemType> *link) 17 { 18     data=http://www.mamicode.com/item; 19     next=link; 20 } 21 //LinkStack.h 22 template<typename ElemType> 23 class LinkStack 24 { 25 protected: 26     Node<ElemType> *top; 27     int count; 28 public: 29     LinkStack(); 30     virtual ~LinkStack(); 31     int Length() const; 32     bool Empty() const; 33     void Clear(); 34     void Traverse(void (*visit)(const ElemType &)) const; 35     bool Push(const ElemType &e); 36     bool Top(ElemType &e) const; 37     bool Pop(ElemType &e); 38     LinkStack(const LinkStack<ElemType> &copy); 39     LinkStack<ElemType> &operator=(const LinkStack<ElemType> &copy); 40 }; 41 template<typename ElemType> 42 LinkStack<ElemType>::LinkStack() 43 { 44     top=NULL; 45     count=0; 46 } 47 template<typename ElemType> 48 LinkStack<ElemType>::~LinkStack() 49 { 50     Clear(); 51 } 52 template<typename ElemType> 53 int LinkStack<ElemType>::Length() const 54 { 55     return count; 56 } 57 template<typename ElemType> 58 bool LinkStack<ElemType>::Empty() const 59 { 60     return top==NULL; 61 } 62 template<typename ElemType> 63 void LinkStack<ElemType>::Clear() 64 { 65     ElemType tmpElem; 66     while(!Empty()) 67         Pop(tmpElem); 68 } 69 template<typename ElemType> 70 void LinkStack<ElemType>::Traverse(void (*visit)(const ElemType &))const 71 { 72     Node<ElemType> *tmpPtr; 73     LinkStack<ElemType> tmpS; 74     for(tmpPtr=top;tmpPtr!=NULL;tmpPtr=tmpPtr->next) 75         tmpS.Push(tmpPtr->data); 76     for(tmpPtr=tmpS.top;tmpPtr!=NULL;tmpPtr=tmpPtr->next) 77         (*visit)(tmpPtr->data); 78 } 79 template<typename ElemType> 80 bool LinkStack<ElemType>::Push(const ElemType &e) 81 { 82     Node<ElemType> *newTop=new Node<ElemType>(e,top); 83     if(newTop==NULL)//内存耗尽 84         return false; 85     else 86     { 87         top=newTop; 88         count++; 89         return true; 90     } 91  92 } 93 template<typename ElemType> 94 bool LinkStack<ElemType>::Top(ElemType &e)const 95 { 96     if(Empty()) 97         return false; 98     else 99     {100         e=top->data;101         return true;102     }103 104 }105 template<typename ElemType>106 bool LinkStack<ElemType>::Pop(ElemType &e)107 {108     if(Empty())109         return false;110     else111     {112         Node<ElemType> *old_top=top;113         top=old_top->next;114         e=old_top->data;115         count--;116         delete old_top;117         return true;118     }119 120 }121 template<typename ElemType>122 LinkStack<ElemType>::LinkStack(const LinkStack<ElemType> &copy)123 {124     if(Empty())125     {126         top=NULL;127         count=0;128     }129     else130     {131         top=new Node<ElemType>(copy.top->data);132         count=copy.count;133         node<ElemType> *buttomPtr=top;134         for(Node<ElemType> *tmpPtr=copy.top->next;tmPtr!=NULL;tmpPtr=tmpPtr->next)135         {136             buttomPtr->next=new Node<ElemType> (tmpPtr->data);137             buttomPtr=buttomPtr->next;138         }139 140     }141 }142 template<typename ElemType>143 LinkStack<ElemType> &LinkStack<ElemType>::operator=(const LinkStack<ElemType> &copy)144 {145     if(&copy!=this)146     {147         if(copy.Empty())148         {149             top=NULL;150             count=0;151         }152         else153         {154             Clear();155             top=new Node<ElemType>(copy.top->data);156             count=copy.count;157             Node<ElemType> *buttomTop=top;158             for(Node<ElemType> *tmpPtr=copy.top->next;tmpPtr!=NULL;tmpPtr=tmpPtr->next)159             {160                 buttomTop->next=new node<ElemType>(tmpPtr->data);161                 buttomTop=buttomTop->next;162             }163 164         }165     }166 167 }