注： 模板类的声明与实现都要写在.h文件中，不能写在.cpp文件中。
因为，模板只有在具体实例化时，才去实现。
链式栈模板类：
#include "stdafx.h"
#define NULL 0
template <class Type> class Stack;
//定义--节点
template <class Type>
class StackNode{
friend class Stack<Type>;
public:
StackNode (Type i=0, StackNode<Type>* p=NULL):data(i),next(p)
{
}
private:
Type data;
StackNode<Type> *next;
};
//定义--链式栈
template<class Type>
class Stack{
private:
StackNode<Type> *top;
public:
Stack():top(NULL){}
~Stack();
void Push(const Type & item);
Type Pop();
Type GetTop();
void MakeEmpty();
bool IsEmpty()
{
return top==NULL;
}
};
template<class Type>
Stack<Type>::~Stack()
{
MakeEmpty();
}
template<class Type>
void Stack<Type>::MakeEmpty()
{
StackNode<Type> *p;
while(top!=NULL){
p=top;
top=top->next;
delete p;
}
}
template<class Type>
void Stack<Type>::Push(const Type &item)
{
StackNode<Type> *p = new StackNode<Type>(item,top);
if (!p)
{
cerr<<"Memory Full "<<endl;
exit(0);
}
p->next=top;
top=p;
}
template <class Type>
Type Stack<Type>::Pop()
{
if (IsEmpty())
return 0;
StackNode<Type> *p =top;
top=top->next;
Type t=p->data;
delete p;
return t;
}
template <class Type>
Type Stack<Type>::GetTop()
{
if (IsEmpty())
return 0;
Type t=top->data;
return t;
}
应用：
#include "stdafx.h"
#include "Stack.h"
#include "iostream"
using namespace std;
bool BracketMatch(char *p){
Stack<char> s1;
char q;
while (*p!='\0')
{
switch (*p)
{
case '{': //遇到左括弧，入栈
case '[':
case '(':
s1.Push(*p);
break;
case '}': //遇到右括弧，出栈
case ']':
case ')':
if(!(q=s1.Pop()))
return false;
//检查匹配性
if( *p=='}'&&q!='{' || *p==']'&&q!='[' ||
*p==')'&&q!='(')
return false;
break;
default: //非括弧不理会
break;
};
p++;
}
//扫描结束后，栈必须为空
if(s1.IsEmpty( ))
return true;
else
return false;
}
int main(array<System::String ^> ^args)
{
Stack<int> s;
s.Push(1);
s.Push(2);
while(!s.IsEmpty())
cout<<s.Pop()<<endl;
char c[50];
cout<<"输入带有{}【】（）的算术表达式,回车结束"<<endl;
while(true)
{
cin>>c;
if (BracketMatch(c))
cout<<"Match"<<endl;
else
cout<<"Not Match"<<endl;
}
while(getchar()!='a')
;
return 0;
}