3.2　栈的应用举例

视频二维码（扫码观看）

由于栈具有的“后进先出”的固有特性，因此，栈成为程序设计中常用的工具和数据结构。以下是几个栈应用的例子。

一、数制转换

十进制整数N向其他进制数d（二、八、十六）的转换是计算机实现计算的基本问题。

转换法则对应于一个简单算法原理：

N＝（N div d）×d＋N mod d

其中，div为整除运算，mod为求余运算，例如（1348）₁₀＝（2504）₈，其运算过程如下：

采用静态顺序栈方式实现

二、括号匹配的检验

匹配思想：从左至右扫描一个字符串（或表达式），则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈顶删除该左括号。

算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到的右括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。

算法描述：