sqstack.h

求图的强连通分支

#ifndef SQSTACK_H
#define SQSTACK_H
#include"exc.h"
template<class ElemType>
class AbsStack{
public:
	AbsStack(){}
	virtual ~AbsStack(){}
	virtual int IsEmpty()const=0;
	virtual int IsFull()const =0;
	virtual void MakeEmpty()=0;
	virtual void Push(const ElemType& X)=0;
	virtual void Pop()=0;
	virtual  ElemType& Top() const=0;
private:
	AbsStack(const AbsStack&){}
};
static const int InitStackSize=10;
template<class ElemType>
class Stack: public AbsStack<ElemType>{
private:
	ElemType* Array;
	int top;
	int MaxSize;
	void DoubleArray(int Max);
public:
	Stack();
	~Stack(){delete [] Array;}
	Stack(int a ){MaxSize=a;top=-1;Array=new ElemType[MaxSize];}
	void MakeEmpty(){top=-1;}
	int IsEmpty()const{return top==-1;}
	int IsFull()const {return top==MaxSize-1;}
     ElemType& Top()const;
	void Push(const ElemType& X);
	void Pop();
	const Stack& operator=(const Stack &R);

};


template<class ElemType>
Stack<ElemType>::Stack():top(-1),MaxSize(InitStackSize){
Array=new ElemType[MaxSize];

}

template<class ElemType>
 ElemType & Stack<ElemType>::Top()const{
Exception(IsEmpty(),"Underflow:Stack is empty");
return Array[top];
}

template<class ElemType>
void Stack<ElemType>::Push(const ElemType& X){
if(top+1==MaxSize)DoubleArray(2*MaxSize);
Array[++top]=X;
}

template<class ElemType>
void Stack<ElemType>::Pop(){
Exception(IsEmpty(),"Stack is underflow!");
top--;
}

template<class ElemType>
const Stack<ElemType>& Stack<ElemType>::operator =(const Stack<ElemType> &R){
if(this==&R)return *this;
delete[] Array;
Array=new ElemType[R.MaxSize];
top=R.top;
for(int j=0;j<=top;j++)Array[j]=R.Array[j];
return this;
}

template<class ElemType>
void Stack<ElemType>::DoubleArray(int Max){
ElemType * oldarr=Array;
Exception(MaxSize>=Max,"New size is too small!");
Array=new ElemType[Max];
for(int k=0;k<=top;k++)Array[k]=oldarr[k];
MaxSize=Max;
delete[] oldarr;
return;
}
#endif