大话数据结构-栈与队列

《大话数据结构-栈与队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、文章知识点来至于大话数据结构里边章节知识，这篇主要介绍栈与队列在计算机中存储形式，以及在某些算法领域中对栈和队列的相关应用。章节最后介绍了著名的逆波兰表达式，以及通过算法来实现该表达式的运算过程。在实现代码的同时添加了流程图。相关代码源码请查看文章最后。栈与队列1栈结构定义                                2栈的顺序存储 3两栈共享空间        思路：他们是在数组的两端，向中间靠拢top1和top2是两个栈的栈顶指针，只要两个指针不碰头就可以        图解 4栈的链式存

2、储        5栈的顺序存储和链式存储区别        如果栈使用过程中元素变化不可预测，有时候小，有时候非常大，那么推荐用栈的链式存储。如果一直栈的的元素变化在可控范围内，推荐使用栈的顺序存储。6后缀表达式        表达式：931–3*+102/+        规则：从左到右遍历表达式中的每个数字和符号，遇到是数字就进栈，遇到事符号就就将栈顶两个数字取出进行计算，运算结果进栈，一直到最终获得结果。5中缀表达式转后缀表达式        中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“

3、9313–3*+102/+”        规则：从左到右遍历表达式的每个数字和符号，若是数字就输出，就成为后缀表达式的一部分；若是符号，则判断与其栈顶符号的优先级，是右括号或者优先级低于栈顶元素则栈顶元素以此出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式。6队列        定义：只允许在一段进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出的线性表，简称FIFO。允许插入的一段陈为队尾，允许删除的一段称为对头        循环队列                  定义：我们把队列

4、头尾相接的顺序存储结构称为循环队列7队列的链式存储        队列的链式存储结构其实就是线性表的单链表，只不过它只能头出尾进，我们把它简称为队列。8接下来开始对以上知识点实践运用，我们已计算器为例来说明算法对于堆栈的使用。目的是计算表达式9+(3-1)*3+10/2的运行结果首先我们熟悉下后缀表达式9313–3*+102/+，他是通过中缀表达式9+(3-1)*3+10/2的来的。关于中缀表达式转后缀表达式：　　　中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9313–3*+102/+”    

5、    规则：从左到右遍历表达式的每个数字和符号，若是数字就输出，就成为后缀表达式的一部分；若是符号，则判断与其栈顶符号的优先级，是右括号或者优先级低于栈顶元素则栈顶元素以此出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式。关于后缀表达式计算：　　 表达式：931–3*+102/+        规则：从左到右遍历表达式中的每个数字和符号，遇到是数字就进栈，遇到事符号就就将栈顶两个数字取出进行计算，运算结果进栈，一直到最终获得结果。9中缀表达式转后缀表达式流程图：后缀表达式计算结果流程图：10 中缀表达式

6、转后缀表达式实现代码：publicstaticstringGetSufficExpression(stringexpression){varexpressionArray=expression.Split('');varoperateStack=newStackLinkList();varsufficExpression=string.Empty;for(vari=0;i

7、llOrEmpty(input)){continue;}if(IsNumber(input)){sufficExpression+=string.Format("{0}",input);continue;}elseif(input==")"){while(true){varpopValue=operateStack.Pop();if(popValue=="("){break;}sufficExpression+=string.Format("{0}",popValue);}}elseif(IsOperation

8、Char(input)){while(true){if(operateStack.IsEmpty()){operateStack.Push(input);break;}varpopValue=operateStack.Pop();if(!IsOperationChar(popValue)){operateStack.Push(popValue);operateStack.Push(in