说明：这部分通过例题来体会栈的应用。

1.顺序栈的应用

【例3-1】 C语言里算术表达式中的括号只有小括号。编写算法，判断一个表达式中的括号是否正确配对，表达式已经存入字符数组exp[]中，表达式中的字符个数为n。

分析：

本题可以用栈来解决，下面就来说说为什么要用栈来解决。

给你一个表达式，目测怎么判断括号是否匹配呢？可以这样做，从左往右看这个表达式中的括号，看到一个“（”就记住它（这里可以理解为入栈），如果下一个括号是“）”（这里可以理解为出栈），则划掉这两个括号，一对括号处理完毕继续往后看。如果前边所有的括号都被划掉，而下一个括号却是“）”，则括号一定不匹配，因为“）”之前已经没有括号和它匹配了。如果下一个括号是“（”，则暂时不管前一个“（”，先把它放在那里，等后边的“（”处理掉后再来处理它。后边的“（”处理掉才能回来处理先前的“（”，这里体现了栈的先进后出特点。以后看到的括号要么是“（”，要么是“）”，就用前边的方法来处理。如果到最后所有括号都被划掉，则匹配，否则就不匹配。由此可见，一个问题中如果出现诸如这种情况，即在解决问题的过程中出现了一个子问题，但凭现有条件不能解决它，需要记下，等待以后出现可以解决它的条件后再返回来解决。这种问题需要用栈来解决，栈具有记忆的功能，这是栈的FILO特性所延伸出来的一种特性。

通过以上分析可知，此题应该用栈来解决，代码如下：

说明：通过这个简单的例子，考生可以了解什么样的题目要用栈来解决。

【例3-2】 编写一个函数，求后缀式的数值，其中后缀式存于一个字符数组exp中，exp中最后一个字符为“\0”，作为结束符，并且假设后缀式中的数字都只有一位。本题中所出现的除法运算，皆为整除运算，如2/3结果为0、3/2结果为1。

分析：

这里首先要复习一下算术表达式的3种形式：前缀式、中缀式、后缀式。中缀式是我们所熟悉的表达式。例如，（a+b+c×d）/e是一个中缀式，转化为前缀式为/++ab×cde，转化为后缀式为abcd×++e/。(www.daowen.com)

注意：中缀表达式转化成后缀或者前缀，结果并不一定唯一。例如，ab+cd×+e/同样是（a+b+c×d）/e的后缀式。后缀式和前缀式都只有唯一的一种运算次序，而中缀式却不一定。后缀式和前缀式是由中缀式按某一种运算次序而生成的，因此对于一个中缀式可能有多种后缀式或者前缀式。例如，a+b+c可以先算a+b，也可以先算b+c，这样就有两种后缀式与其对应，分别是ab+c+和abc++。

回到本题，后缀式的求值可以用栈来解决，为什么呢？对于一个后缀式，当从左往右扫描到一个数值的时候，具体怎么运算，此时还不知道，需要扫描到后边的运算符才知道，因此必须先存起来，这符合例3-1中黑体字所描述的情形，因此可以用栈来解决。

执行过程：当遇到数值的时候入栈，当遇到运算符的时候，连续两次出栈，将两个出栈元素结合运算符进行运算，将结果当成新遇到的数值入栈。如此往复，直到扫描到终止符“\0”。此时栈底元素值即为表达式的值。

由此可以写出以下代码：

补充：假设有一个字符'5'，如果定义一个整型变量a，执行a='5'；，则此时a里边保存了5的ASCII码，而不是数字5。如何将'5'这个字符代表的真正意义，即5这个整数保存于a中，只需执行a='5'-'0'；即可。同理，如果把一个整型数字（假设为a）转化为对应的字符型数字存储在字符变量（假设为b）中，只需执行b=a+'0'；即可。此时b中保存的是a这个数字的字符，但是这种转化只适用于0～9这10个数字。这个小技巧在程序设计题目中应用得比较多，因此在这里要提一下，有些跨考的同学可能不太熟练。

2.链栈的应用

【例3-3】 用不带头结点的单链表存储链栈，设计初始化栈、判断栈是否为空、进栈和出栈等相应的算法。

分析：

不带头结点的单链表lst为空的条件是lst==NULL，进栈和出栈操作都是在表头进行的。算法如下：