![](https://csdnimg.cn/release/download_crawler_static/86134108/bga.jpg)
10
第三章 栈与队列
3.15
typedef struct{
Elemtype *base[2];
Elemtype *top[2];
}BDStacktype; // 双向栈类型
Status Init_Stack(BDStacktype &tws,int m)// 初始化一个
大小为 m 的双向栈 tws
{
tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype));
tws.base[1]=tws.base[0]+m;
tws.top[0]=tws.base[0];
tws.top[1]=tws.base[1];
return OK;
}//Init_Stack
Status push(BDStacktype &tws,int i,Elemtype x)//x 入
栈,i=0 表示低端栈 ,i=1 表示高端栈
{
if(tws.top[0]>tws.top[1]) return OVERFLOW; //注意
此时的栈满条件
if(i==0) *tws.top[0]++=x;
else if(i==1) *tws.top[1]--=x;
else return ERROR;
return OK;
}//push
Status pop(BDStacktype &tws,int i,Elemtype &x)//x 出
栈,i=0 表示低端栈 ,i=1 表示高端栈
{
if(i==0)
{
if(tws.top[0]==tws.base[0]) return OVERFLOW;
x=*--tws.top[0];
}
else if(i==1)
{
if(tws.top[1]==tws.base[1]) return OVERFLOW;
x=*++tws.top[1];
}
else return ERROR;
return OK;
}//pop
3.16
void Train_arrange(char *train)// 这里用字符串 train 表
示火车 ,'H' 表示硬席 ,'S'表示软席
{
p=train;q=train;
InitStack(s);
while(*p)
{
if(*p=='H') push(s,*p); // 把'H' 存入栈中
else *(q++)=*p; // 把'S'调到前部
p++;
}
while(!StackEmpty(s))
{
pop(s,c);
*(q++)=c; // 把'H' 接在后部
}
}//Train_arrange
3.17
int IsReverse()//判断输入的字符串中 '&' 前和 '&' 后部分
是否为逆串 ,是则返回 1,否则返回 0
{
InitStack(s);
while((e=getchar())!='&')
{
if(e== ’ @’) return 0;// 不允许在’ & ’之前出现’
@’
push(s,e);
}
while( (e=getchar())!='@')
{
if(StackEmpty(s)) return 0;
pop(s,c);
if(e!=c) return 0;
}
if(!StackEmpty(s)) return 0;
return 1;
}//IsReverse
3.18
Status Bracket_Test(char *str)// 判别表达式中小括号是
否匹配
{
count=0;
for(p=str;*p;p++)
{
if(*p=='(') count++;
else if(*p==')') count--;
if (count<0) return ERROR;
}
if(count) return ERROR; //注意括号不匹配的两种情
况
return OK;