客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
栈是一种先进后出机制，它只允许访问访问一个数据项，即 栈顶（最后插入的数据项）。它有主要的三种操作：push,向栈内压入值；pop,弹出栈顶的值，即返回栈顶的值，并把它从栈内删除；peek,只返回但不删除栈顶。 概念很容易理解，无非就像给弹匣压子弹等等这种类比，但是像我这样的新手在刚接触到栈的时候总是很迷茫，认为它很难，其实这只是错觉，主要是因为没有搞清楚栈主要用在那些场景。 栈普遍应用于编译器、文本检测、科学计算等等，在编译器中，它用来检测一个函数体等是否为封闭的（括号是否成对等等），在文本检测中，想想你的vs，如果最后没有大括号它就会检测出来，和编译器中一样，在科学计算中，就像商店能买到的那些高级计算器，输入一个算式可以直接计算出来结果，而不像普通计算器中，只能输入数字，然后在按键一步一步计算，以上这些应用场景，归根结底都是对文本的检测，现在知道栈的用途了吧，后面将结合队列一起练练手。 队列queue 顾名思义，就是一堆东西成队排列了，它是先进先出机制(FIFO)与栈相反，栈是后进后出(LIFO)。它的主要操作有：Enqueue,向队尾添加值；Dequeue,返回并移除对头的值；peek,返回但不移除对头的值。 队列很容易理解，它主要应用在网络通信、系统等。windows的所有事件都是放在队列里面的。 最典型的，就是系统的任务分配了，每个进程或线程都分配在某些队列里，方便cpu时间片的分配调度，任务的运行不可能是你最后打开的程序先运行吧，当然它有优先级，这个排除在外。 栈的应用 现在搞清楚了栈和队列的应用场景，那就趁热打铁，练练手。 现在，按部就班的实现一个科学表达式的计算。 首先了解一下计算机是怎么计算类似于 1*(2+3)+4/2 这样的计算。对于大脑来说，这个算式简单到不能再简单了，但是电脑却不是如此，得让它明白那个先算，那个后算，以及哪些是操作符（运算符）哪些不是（例如括号）。 像我们经常使用的这种算式称为 中缀式 ，就是运算符都在两个操作符中间了，这种中缀式对于我们人脑来说，并不是顺序执行的，它可以从中间先开始，比如1+2*3 ，这正是电脑很难理解中缀式的原因，因为他总是顺序执行的。那么，我们就得把中缀式换成 后缀式(postfix) 或称作 逆波兰记法(reverse Polish notation)。 中缀式就是把运算符放到两个操作数后边，让算式保持顺序计算（对于我们人脑也是如此）。具体怎么放，大家看看下面的例子就明白了。
结合上边的示例，会发现后缀式并没有描述优先级的括号，这是因为括号并不是运算符。大家在自己动手做两个，就掌握这种方法了。 程序中如何实现这种转换呢？那就要依靠强大的栈了。 中追到后缀的转换 |
请发表评论