栈和队列的应用非常之广,只要问题满足后进先出和先进先出原则,均可使用栈和队列作为其数据结构。

栈的应用

1、 数制转换
将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题,很容易通过”除B取余法”来解决。
【例】将十进制数13转化为二进制数。
解答:按除2取余法,得到的余数依次是1、0、1、1,则十进制数转化为二进制数为1101。
分析:由于最先得到的余数是转化结果的最低位,最后得到的余数是转化结果的最高位,因此很容易用栈来解决。

转换算法如下:

typedef int DataType;//应将顺序栈的DataType定义改为整型
void MultiBaseOutput (int N,int B)
{//假设N是非负的十进制整数,输出等值的B进制数
int i;
SeqStack S;
InitStack(&S);
while(N){  //从右向左产生B进制的各位数字,并将其进栈
push(&S,N%B); //将bi进栈0<=i<=j
N=N/B;
}
while(!StackEmpty(&S)){  //栈非空时退栈输出
i=Pop(&S);
printf(“%d”,i);
}
}

除数制的转换外,栈还可用于解决括号匹配检查、行编辑处理和表达式求解等问题。

Tagged on:

发表评论