栈的应用

栈具有先进后出的特点，这个特点在解决某些问题时是很有效的。本节我们来看几个栈的常见应用以及栈结构适合解决的问题类型。

---

1 数值转换

我们日常生活中用的是十进制，而计算机中绝大多数时候是二进制，八进制或十六进制，这就涉及到数值转换的问题。十进制向其他进制转换一般是通过连除实现的，例如，如果我们想找出十进制的 42 对应的二进制表示，就需要对 42 连除 2，直到商为 0 。下图展示了完整过程：

用公式概括就变为了：
N = ( N   d i v   d ) × d + N   m o d   d N = (N\ \mathrm{div} \ d ) \times d + N\ \mathrm{mod}\ d N=(N div d)×d+N mod d
其中， d i v \mathrm{div} div 为整除运算， m o d \mathrm{mod} mod 为求余运算。

假设现在要编写一个程序来将任意的十进制数转换为八进制数。由于上述方法最先计算出的余数位于最低位，最后计算出的位于最高位，符合后入先出的思想，所以可以用栈来保存余数。

void conversion(int n){
    int r;          // 用来保存余数

    LinkedStack S;
    InitStack(S);

    while (n!=0){
        r = n % 8;	// 求余数
        n = n / 8;	// 将n更新为商，以便后续运算
        Push(S, r); // 将余数入栈
    }

    Print(S);       // 将栈内元素输出
}

2