|
先入后出(FILO First In Last Out)的有序列表
2.栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表.允许插入和删除的一端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底(Bottom).
3.根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除.
栈的应用场景
1.子程序的调用:在调往子程序前,会先将下个指令的地址存到栈中,直到子程序执行完后再将地址取出,以回到原来的程序.
2.处理递归调用:和子程序的调用类似,只是除了储存下一个指令的地址外,也将参数区域变量等数据存入堆栈中.
3.表达式转换(中缀表达式转后缀表达式)与求值(实际解决).
4.二叉树的遍历.
5.图形的深度优先(depth-first)搜索算法.
栈结构实现案例用栈完成表达式的计算(中缀表达式)
准备两个栈,数字栈和符号栈.
1.通过一个index值(索引),来遍历表达式.
2.如果发现是一个数字就直接入数字栈.
3.如果是一个符号,分情况考虑如果当前符号栈为空,就直接入站.如果符号栈有操作符,就进行比较.
-
如果当前操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop两个数,再从符号栈中pop出一个字符,进行运算,将得到结果入数栈,然后当前操作符入符号栈.
-
如果当前的操作符的优先级大于栈中的操作符,就直接入栈.
4.当表达式扫描完毕,就顺序地从数栈和符号栈中pop出相应的数和符号,并运行.
5.最后在数字栈只有一个数字,就是表达式的结果.
（编辑：莆田站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
