3.15.c

数据结构习题及答案

◆3.15③ 假设以顺序存储结构实现一个双向栈，即在一维数组的存
储空间中存在着两个栈，它们的栈底分别设在数组的的两个端点。
试编写实现这个双向栈tws的三个操作:初始化inistack(tws)、入栈
 push(tws,i,x)和出栈pop(tws,i,x)的算法, 其中i为0或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)
{ 
 if(!(tws.elem=(SElemType*)malloc((size-1)*sizeof(SElemType)))) return ERROR;
 tws.top[0]=0;
 tws.top[1]=size-2;
 tws.size=size-1;
 return OK;

}

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

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