[数据结构]栈之顺序栈的类模板实现

栈的数组实现形式，采用动态分配数组，不够时可以调整栈的大小。

Stack.h文件：主要定义栈的抽象基类，提供公共的接口函数。

#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;const int stackIncreament=20;template<class T>class SeqStack:public Stack<T>{public:SeqStack(const int sz=50):top(-1),maxSize(sz),elements(new T[sz]){assert(elements!=NULL);}SeqStack(const SeqStack<T>& rhs);SeqStack<T>& operator=(const SeqStack<T>& rhs);~SeqStack(){delete []elements;}void Push(const T& x);bool Pop(T& x);bool getTop(T& x)const;bool IsEmpty()const{return (top==-1)?true:false;}//要覆盖，基类和继承类的const性质也要一样。函数的形式要形式要完全一样才能同名覆盖。bool IsFull()const{return (top==maxSize-1)?true:false;}int getSize()const{return top+1;}void MakeEmpty(){top=-1;}friend ostream& operator<< <T>(ostream& out,const SeqStack<T> &rhs);//加了一个<Type>才是正确的，不加会报错。类模板引起的一些问题private:void overflowProcess();private:T *elements;int top;int maxSize;};template<class T>void SeqStack<T>::overflowProcess(){T *ptr=new T[maxSize+stackIncreament];if(ptr==NULL){cerr<<"err"<<endl;exit(1);}for(int i=0;i<=top;++i)ptr[i]=elements[i];delete []elements;elements=ptr;maxSize=maxSize+stackIncreament;}template<class T>void SeqStack<T>::Push(const T& x){if(IsFull())overflowProcess();elements[++top]=x;}template<class T>bool SeqStack<T>::Pop(T& x){if(IsEmpty()) return false;x=elements[top–];return true;}template<class T>bool SeqStack<T>::getTop(T& x)const{if(IsEmpty()) return false;x=elements[top];return true;}template<class T>ostream& operator<<(ostream& out,const SeqStack<T> &rhs){out<<"top= "<<rhs.top<<endl;for(int i=0;i<=rhs.top;++i)out<<"elements: "<<rhs.elements[i]<<" ";out<<endl;return out;}template<class T>SeqStack<T>::SeqStack(const SeqStack<T>& rhs){T *ptr=new T[rhs.maxSize];if(ptr==NULL){cerr<<"err"<<endl;exit(1);}for(int i=0;i<=rhs.top;++i)ptr[i]=rhs.elements[i];elements=ptr;maxSize=rhs.maxSize;top=rhs.top;}template<class T>SeqStack<T>& SeqStack<T>::operator=(const SeqStack<T>& rhs){T *ptr=new T[rhs.maxSize];if(ptr==NULL){cerr<<"err"<<endl;exit(1);}for(int i=0;i<=rhs.top;++i)ptr[i]=rhs.elements[i];elements=ptr;maxSize=rhs.maxSize;top=rhs.top;return *this;}

下面是测试函数：

int main(int argc, char* argv[]){SeqStack<int> s(5);int a=1;int b=2;int c=3;int d=4;int e=5;s.Push(a);s.Push(b);s.Push(c);s.Push(d);s.Push(e);cout<<s;cout<<"getSize(): "<<s.getSize()<<endl;cout<<"IsEmpty(): "<<s.IsEmpty()<<endl;cout<<"IsFull(): "<<s.IsFull()<<endl;int t;s.Pop(t);s.Pop(t);cout<<s;s.getTop(t);cout<<"getTop() "<<t<<endl;s.Push(a);s.Push(b);s.Push(c);s.Push(d);s.Push(e);cout<<s;s.MakeEmpty();cout<<s;s.Push(e);s.Push(e);cout<<s;SeqStack<int> s1(s),s2;cout<<s1;s2=s;cout<<s2;system("pause");return 0;}下面是测试结果：

top= 4elements: 1 elements: 2 elements: 3 elements: 4 elements: 5getSize(): 5IsEmpty(): 0IsFull(): 1top= 2elements: 1 elements: 2 elements: 3getTop() 3top= 7elements: 1 elements: 2 elements: 3 elements: 1 elements: 2 elements: 3 elements: 4 elements: 5top= -1top= 1elements: 5 elements: 5top= 1elements: 5 elements: 5top= 1elements: 5 elements: 5请按任意键继续. . .

注意事项：

1.在集成类同名覆盖基类的纯虚函数或者同名函数时，函数形式要完全一样。返回值要一样，const性也要一样，否则视为不同的函数，为函数的重载

2.类模板中的友元函数声明比较特殊，，要多加一点类型。如下：

在里面声明友元函数时ostream&operator<<<Type>(ostream&output,CirQueue<Type>&cq);//多加一个<Type>

否则会报错，在函数的定义时就不要加了。

3.容易敲错单词，键盘要熟练。写程序时，头脑一定要保持清晰，否则不要继续，不然调试很麻烦。

你并不一定会从此拥有更美好的人生，