模板实现一个通用栈
template <class T,int SIZE> class CArrayStackTemp
{
public:
CArrayStackTemp () //缺省构造函数,构造一个空堆栈
{
top= -1;
};
～ CArrayStackTemp (){};//析构函数
void SetEmpty (); //置空堆栈
bool IsEmpty(); //判断堆栈是否为空
bool Push(T element); //入栈
bool Pop(T& element);//出栈
private:
T Buffer[SIZE];
int top;
};
与堆栈的基本操作相对应的成员函数的实现如下:
template <class T, int SIZE> void CArrayStackTemp<T, SIZ
E>:: SetEmpty ()
{
top= -1; //将栈顶指针赋 -1,并不实际清除数组元素
}
template <class T, int SIZE> bool CArrayStackTemp<T, SIZ
E>:: IsEmpty ()
{
return(top == -1);
}
template <class T, int SIZE> bool CArrayStackTemp<T, SIZ
E>:: Push (T element)
{
top++;
if (top>SIZE-1)
{
top--;
return false; //堆栈已满,不能执行入栈操作
}
Buffer[top]=element;
return true;
}
template <class T, int SIZE> void CArrayStackTemp<T, SIZ
E>:: Pop (T& element)
{
if (IsEmpty())
return false;
element =Buffer[top];
top--;
return true;
}
根据实际需要,还可以扩充堆栈功能。例如:加入取栈顶元素、求
堆栈长度等操作,其方法如上。
通用链栈的实现
模板类中允许使用指针和定义自己的结构,这就为实现链式结构
提供了保证。这里采用一个单链表来实现堆栈,栈顶指针指向链表的
第一个结点,入栈和出栈均在链表的头进行。该模板类的定义如下:
template <class T> class CLinkStackTemp
{
public:
//类的缺省构造函数,生成一个空堆栈
CLinkStackTemp ()
{
top=NULL;
};
～ClinkStackTemp(){}; //析构函数
//定义结点结构
struct node
{
T
data; //入栈元素
node* next; //指向下一结点的指针
};
void SetEmpty(); //置空堆栈
bool IsEmpty(); //判断堆栈是否为空
bool Push(T element); //压入堆栈
bool Pop(T& element);//弹出堆栈
private:
node* top;
};
该类的成员函数实现如下:
template <class T> void CLinkStackTemp <T>::SetEmpty()
{
//释放堆栈占用的内存
node* temp;
while (top!=NULL)
{
temp=top;
top=top->next;
delete temp;
}
}
template <class T> bool CLinkStackTemp <T>::IsEmpty()
{
return (top==NULL);
}
template <class T> bool CLinkStackTemp <T>::Push(T element)
{
node* temp=new node();
if (temp ==NULL)
return false ;
temp->data=element;
temp->next=top;
top=temp;
return true;
}
template <class T> bool CLinkStackTemp <T>::Pop(T& element)
{
if ( IsEmpty())
return false;
node* q = top;
element = top->data;
top=top->next;
delete q;
return true;
}