首页 > 代码库 > 栈的应用
栈的应用
堆栈和队列是最基本的两个ADT，简单但是重要。先讲堆栈在计算机中的应用。
堆栈：
1.用于符号匹配。
在编译器的语法检查中，一个过程就是检查各种括号是否匹配，比如 ([]) ，这就是匹配的，而 {[}] 就不匹配了。可以用堆栈来实现括号匹配。
具体算法如下：
建立一个空的堆栈。
while( 文件没有结束 ) {
读取一个字符。
if 遇到一个左括号，把它入栈。
else if 遇到右括号 then 检查堆栈，{
if 堆栈为空 then 报告错误，终止程序（括号不匹配）。
else if 堆栈非空 then {
if 栈顶不是对应的左括号 then 报错，终止程序。
弹出栈顶。
}
}
if 栈非空 then 报错。
2.用于计算代数式。( 也可以用二叉树来解决 )
如果我们要计算 6 + 4 * 8 ，要考虑到优先级的问题，这时候就可以用到堆栈了。
先要把代数式构造成 6 4 8 * + （构造方法也是用堆栈，在下一条会讲到）。逐个读取数据，当读到数字时， 把数字入栈，
读到运算符时，弹出栈中的两个元素（因为这里的是二元运算符，所以弹出两个，如果是sin等一元运算符就弹出一个），根据读取
的运算符执行运算，把结果压入栈中，然后继续读取数据，读取结束后栈顶元素就是结果。
比如读取6，4，8，由于是数字，所以依次入栈，
读到 "*" 时，弹出 4 和 8，相乘得到 32，把32入栈。读到 "+" 时，
弹出 6 和 32 ，执行运算得到 38，压入栈中，接着读取结束，栈顶的 38 就是结果。
3.构造表达式。( 也可以用二叉树来解决 )
比如一个正常的代数式（叫他infix）, a + b * c + ( d * e + f ) * g , 转化成表达式 a b c * + d e * f + g * +, 这个表达式我们叫他 postfix。
把postfix按照 2 中的算法计算就能得到正确的计算顺序。
先规定优先级，加减的优先级最低，左括号优先级最高
创建一个字符串output储存 postfix。
创建一个空栈 operators。
while ( )
逐个读取 infix 中的元素，储存在 temp 中。
if temp 是数字（operand）then 把 temp 压入 output 字符串。
if temp 是除了右括号 ")" 之外的运算符（operator）
if operators 栈空 then temp 入栈。
if operators 栈非空，
while ( 栈顶元素优先级大于或等于 temp 并且 栈顶元素不等于左括号 )
弹出栈顶元素到 output 。
if temp 是右括号 ")"
while ( 栈顶元素不等于左括号 )
弹出栈顶元素到 ouput.
弹出左括号, 但是不输出到 output
比如 a * ( b * c + d )，左边是堆栈中的情况，右边是输出
1. 输出 a，把 "*" 入栈
operators output
top * a
2. "(" 入栈，输出 b
operators output
top (
* a b
3. "*"入栈，输出 c
operators output
top * a b c
(
*
4. 读到 + 号，因为栈顶的 * 优先级大于 + 号，所以弹出栈顶到 output，也就是弹出 "*" ，并输出 "*"
operators output
top + a b c * d
(
*
5.读到 ")" 右括号，弹出左括号 "(" 上的所有运算符，并弹出左括号 "(" ，注意此时左括号没有输出
operators output
top * a b c * d +
6.最后所有元素依次出栈
operators output
top a b c * d + *4.用于函数调用
因为CPU一次只能执行一个命令，而寄存器也是公用的，
当前函数 current() 在运行时，数据储存在寄存器中，如果要调用另外一个函数 target()，而target() 也要求使用寄存器，为了防止数据丢失并且在执行完 target()
能够返回到 current() 继续执行, 这时候就要把当前函数的重要数据储存起来，压入内存中的栈中( 包括变量的值和函数地址 )。这样target()函数就可以无所顾忌的使用寄存器了。
target() 函数执行结束就取栈顶的返回地址继续执行 current()。如果target()中又调用另外一个函数，相应的操作也是一样的。
这种机制和括号匹配有点相似，函数调用就像遇到了一个左括号，函数返回就像遇到一个右括号。
这种机制就是递归的原理。递归返回地址就是自己。（这句话可能有问题，我就是这么理解的）。
栈的空间有限，如果递归没有结束条件，就会不断的压栈，然后栈溢出，程序出错。
队列：
当多个任务分配给打印机时，为了防止冲突，创建一个队列，把任务入队，按先入先出的原则处理任务。
当多个用户要访问远程服务端的文件时，也用到队列，满足先来先服务的原则。
……
有一个数学的分支，叫队列理论（queuing theory ）。用来计算 预测用户在队中的等待时间，队的长度等等问题。
答案取决于用户到达队列的频率，用户的任务的处理时间。如果比较简单的情况，可以单单用分析解决。一个简单的例子就是，
一部电话，一个接线员。当一个电话打进来，如果接线员很忙，就电话放到等待线路后。接线员从队头开始应答。
如果有k个接线员，问题就变的复杂了。通常难以分析解决的问题就用模拟来解决。 可以用一个队列来模拟这个问题。如果k的值很大，
我们也可能需要其他数据结构来模拟问题。通过模拟，可以找到最小的 k 值，使队列满足一个合理的等待时间。
http://www.cnblogs.com/pengyingh/articles/2388882.html
其实还有中断，缓冲处理，迷宫等等。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。