假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈Push(tw

Question

假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈 tws 的三个操作：初始化inistack(tws)、入栈Push(tws,I,x) 和出栈 pop(tws,i)的算法，其中 i 为 0或 1，用以分别指示设在数组两端的两个栈。

Answer 1

实现下列3个函数：
Status InitStack(TwoWayStack &tws, int size);
Status Push(TwoWayStack &tws, int i, SElemType x);
Status Pop(TwoWayStack &tws, int i, SElemType &x);
双向栈类型定义如下：
typedef struct {
SElemType *elem;
int top[2];
int size; // 分配给elem的总容量
}TwoWayStack; // 双端栈


Status InitStack(TwoWayStack &tws, int size)
{ tws.elem=(SElemType*)malloc(sizeof(SElemType)*size);
tws.size=size;
tws.top[0]=0; //hao
tws.top[1]=size-1;
return OK;
}
Status Push(TwoWayStack &tws, int i, SElemType x)
{int w=tws.top[0];
if(w==tws.top[1]) return ERROR;
else if(i==0)
{
tws.elem[tws.top[0]]=x;
tws.top[0]=tws.top[0]+1;
}
else if(i==1)
{
tws.elem[tws.top[1]]=x;
tws.top[1]=tws.top[1]-1;
}
return OK;

}
Status Pop(TwoWayStack &tws, int i, SElemType &x)
{ if(tws.top[1]==tws.size-1&&i==1) return ERROR;
else if(tws.top[0]==0&&i==0) return ERROR;
else if(i==0)
{
tws.top[0]-=1;
x=tws.elem[tws.top[0]];
}
else if(i==1)
{
tws.top[1]+=1;
x=tws.elem[tws.top[1]];
}
return x;
}