数据结构

　　由于栈的操作具有后进先出的固有特性，致使栈成为程序设计中的有用工具。反之，从本节所举例子中可以发现，凡应用问题求解的过程具有"后进先出"的天然特性的话，则求解的算法中也必然需要利用"栈"。
　　本节将从简到繁举以下五个利用栈求解的例子。

　3.2.1 数制转换

　　十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：
　　　N = (N div d)×d + N mod d
　　(其中：div 为整除运算，mod 为求余运算)

　例如：(1348)10 = (2504)8 ，其运算过程如动画演示所示：
　　假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。

　　问题很明确，就是要输出计算过程中所得到的各个八进制数位。然而从动画演示的计算过程可见，这八进制的各个数位产生的顺序是从低位到高位的，而打印输出的顺序，一般来说应从高位到低位，这恰好和计算过程相反。

　　因此，需要先保存在计算过程中得到的八进制数的各位，然后逆序输出，因为它是按"后进先出"的规律进行的，所以用栈最合适。
　

怎样将一个十进制的数值转换成一个八进制的数值呢？

　好的，我想这样一个简单问题你一定回答出来了。不过，你一定在想，这样一个简单算法难道还要用栈吗？那么，下面就让我们来看看用栈的理由。

算法 3.1
　　void conversion ()
　{
　// 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数
　　InitStack(S); 　　// 构造空栈
　　cin >> N;　　　　// 输入一个十进制数
　　while(N)
　　{
　　　Push(S,N % 8);　// "余数"入栈
　　　N = N/8;　　　　// 非零"商"继续运算
　　} // while
　　while (!StackEmpty)
　　{ 　　　　　　　 // 和"求余"所得相逆的顺序输出八进制的各位数
　　　Pop(S,e);
　　　cout << e;
　　} // while
　} // conversion

　　当然这是利用栈的一个极其简单的例子。在这个例子中，栈的操作序列是直线式的，即先一味地入栈，然后一味地出栈。

　　你可能会说，用数组直接实现不也很简单吗？你可以试一下利用数组重新写这个算法，那么你一定能体会到在这个算法中用栈的好处了。

怎么样？你觉得好处在哪儿呢？

　你是否也觉得，栈的引入简化了程序设计的问题，突出了解决问题的根本所在。而用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。在以后几个例子中你将会看到，实际利用栈的问题中，入栈和出栈操作大都不是直线式的，而是交错进行的。