习题－5.c

数据结构经典算法

//本程序只给出了算法思想
//读者可以自己完善本程序
//双向栈的栈结构类型与以前定义略有不同
#define StackSize 100 // 假定分配了100个元素的向量空间
#define char Datatype
typedef struct{
		Datatype Data[StackSize]
		int top0;	//需设两个指针
		int top1;
}DblStack
void InitStack( DblStack *S )
{	//初始化双向栈
		S->top0 = -1;
S->top1 = StackSize; 	/*这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错*/
}	
int EmptyStack( DblStack *S, int  i )
{	//判栈空(栈号 i)
		return  (i == 0 && S->top0 == -1|| i == 1 && S->top1== StackSize)  ;
}
int FullStack( DblStack *S)
{	//判栈满,满时肯定两头相遇
		return (S->top0 == S-top1-1);
}
void Push(DblStack *S, int i, Datatype x)
{	//进栈(栈号i)
		if (FullStack( S ))
		 	Error("Stack overflow");//上溢、退出运行
		if ( i == 0) S->Data[ ++ S->top0]= x;  //栈0入栈
		if ( i == 1) S->Data[ -- S->top1]= x;  // 栈1入栈
}
Datatype Pop(DblStack *S,  int i)
{	//出栈(栈号i)
		if (EmptyStack ( S,i) )
		 	Error("Stack underflow");//下溢退出
		if( i==0 )   
		return ( S->Data[ S->top0--] );//返回栈顶元素，指针值减1
		if( i==1 )
		return ( S->Data[ S->top1++] ); //因为这个栈是以另一端为底的，所以指针值加1。
}
//其余算法略