算法设计:
将编号为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);
}