学文网摘要：介绍了栈在数据结构中的应用。
关键词：栈 进栈 出栈 数组
中***分类号：TP311.12 文献标识码：A 文章编号：1002-2422(2008)01-0061-02
栈是数据结构中重要的线性结构，是一种特殊的线性表，只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。栈项的当前位置是动态的，对栈顶当前位置的标记称为栈项指针。当栈中没有数据元素时，称为空栈。栈的插入操作称为进栈或入栈，栈的删除操作称为退栈或出栈。
栈的应用非常广泛，在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好的盘子上。相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。在计算机中进行算术表达式的计算是通过栈来实现的。算术表达式的两种表示方法，即中缀表示法和后缀表示法。日常算术表达式是将操作符(+，-，*，／)放在两个操作数(数字，或代表数字的字母)之问的。假定操作数为单个英文字母，运算符只有+、-、*√(均为双目运算符，相结合)，因为操作符写在操作数的中间，所以把这种写法称为中缀表达法。
例如：(A-(B*C+D)*E)／(F+G)
这是一个中缀表达式，中缀表达式的计算比较复杂，必须遵守以下三条规则：(1)先计算括号内，后计算括号外；(2)在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加减运算的优先级；(3)同一优先级运算，从左向右依次进行。
从这三条规则可以看出，在中缀表达式的计算过程中，既要考虑括号的作用，又要考虑运算符的优先级，还要考虑运算符出现的先后次序。因此，各运算符实际的运算次序往往同在表达式中出现的先后次序是不一致的，是不可预测的。那么，能否把中缀算术表达式转换成另一种形式的算术表达式，使计算简单化呢?波兰科学家卢卡谢维奇(Lukasiewicz)很早就提出了算术表达式的另一种表示，即后缀表示，也称逆波兰式。在后缀表达法中，操作符跟在两个操作数的后面，这样，A+B就成为AB+，AA3成为AB／。采用后缀表示的算术表达式被称为后缀算术表达式或后缀表达式。在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需一遍扫描便可完成，显然比中缀表达式的计算要简单得多。
例如：上面中缀表达式转换为后缀表达式为ABC*D+E*-FG+／
中缀算术表达式转换成对应的后缀算术表达式是：把每个运算符都移到两个操作数的后面，然后删除掉所有的括号即可。中缀表达式转换成后缀表达式的过程是假定中缀表达式中无空格符，但整个算术表达式以空格符结束，并假定所提供的算术表达式非空且语法是正确的。(1)数组IN口存储中缀表达式；(2)数组POLISH[]存储其后缀表达式；(3)数组S口是一个后进先出的栈；(4)函数PRIOR(CHAR)返回符号CHAR的优先级，各符号的优先级如表1所示。
转换规则：
(1)从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：①如果是数字则直接放入后缀表达式数组；②如果是左括号则直接进栈；③如果是右括号，则把从栈项直到对应左括号之间的运算符依次出栈，并清除对应的左括号；④对于运算符，如果该运算符的优先级大于栈顶优先级，则直接进栈，若该运算符的优先级小于等于栈顶优先级，则先把栈顶运算符出栈，写入后缀表达式数组，然后再进栈.(2)扫描完成后，取出栈中所有运算符，写入后缀表达式数组。
中缀表达式(A+B-C*D)*(E-F)／G转换成后缀表达式为AB+CD*-EF-*G／。利用数据结构中的栈，就很方便地把中缀表达式转换成后缀表达式。