算法设计:

将编号为0和1的两个栈存放于一个数组空间V[m]中,栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空,当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化,判断栈空、进栈和出栈等算法的函数。双栈数据结构的定义如上图:

(1)初始化:

int Init()
{
	S.top[0]=-1;
	S.top[1]=m;
	return 1;//初始化成功
}

(2)入栈:

int push(stack S ,int i,int e)
{//i为栈号,i=0表示左栈,i=1为右栈,e是入栈元素。入栈成功返回1,失败返回0
	if(i<0||i>1)
	{
		cout<<"栈号输入错误"<<endl;
		exit(0);
	}
	if(S.top[1]-S.top[0]==1)
	{
		cout<<"栈满"<<endl;
		return(0);
	}
	switch(i)
	{
	case 0: S.V[++S.top[0]]=x;
	return(1);
	break;
	case 1: S.V[--S.top[1]]=x;
	return(1);
	}
}

(3)出栈:

ElemType pop(stack S,int i)
{//i代表栈号,i=0时为左栈,i=1时为右栈。退栈成功时返回退栈元素,否则返回-1
	if(i<0 || i>1)
	{
	cout<<"栈号输入错误"<<endl;
	exit(0);
	}
	switch(i)
	{
		case 0: if(S.top[0]==-1) 
				{
					cout<<"栈空"<<endl;
					return (-1);
				}
				else return(S.V[S.top[0]--]);
		case 1: if(S.top[1]==m 
				{
					cout<<“栈空”<<endl;
					return(-1);
				}
 				else return(S.V[S.top[1]++]);
	}
}

(4)判空:

int Empty()
{
	return (S.top[0]==-1 && S.top[1]==m);
}