邓俊辉数据结构第三章栈和队列笔记

栈接口与实现

在这里插入图片描述
如果颠倒过来，会导致O(n)的复杂度复杂度正比与后继成正比

进制转换

在这里插入图片描述

括号匹配

在这里插入图片描述
问题：视频中括号不匹配的那个例子，如{（]），邓老师说用栈实现的话可以发现不匹配从而告知失配，这里是否给了一个前提“栈实现的时候告知了程序哪种左右括号是相配对的”，不然栈如何发现这两个左右括号不是配对的呢？

那么在给了多个计数器的情况下，若是也告知程序这个前提，遇到相配对的右括号时相应的计数器再减1，那么不就能实现了吗？（by W_X ）
答：这个例子是 [ ( ] )，方括号计数器、圆括号计数器都是 0 到 1 到 0，会判定成匹配的（by yuantailing 老师）
在这里插入图片描述

栈混洗

在这里插入图片描述

中缀表达式求值

在这里插入图片描述
如果这么写，不能保证两个 pop 的执行顺序。执行顺序因编译器和编译优化而异。（by yuantailing 老师）

逆波兰表达式

在这里插入图片描述

问题：中缀表达式完成了计算……那么为什么还要转化一个RPN（by 蔡一不二）
答：同样长度（指同样多操作数）的 RPN 比中缀表达式算得快。

课件上的转换例子，每个操作数都是一个具体的数，把中缀表达式转成 RPN 的过程已经足以把中缀表达式计算出来了。正如你所理解的，这种情况下转成 RPN 再计算得不偿失。

但是，操作数可能是一个未知数。例如中缀表达式 (a + b) * c 分别代入 n 组具体数字计算表达式值，例如代入 (a=1,b=2,c=3) 、 (a=4,b=5,c=6) 、 (a=10,b=11,c=12) 求值。不转就要算 n 次中缀表达式，转就只要转 1 次 + 算 n 次 RPN 。（by yuantailing 老师）

队列接口与实现

在这里插入图片描述
问题：基于List来实现Queue的时候是否需要像基于Vector来实现Stack那样注意方向性呢？
个人认为是不需要注意的。这是由于List和Vector的区别造成的，前者的动态性能优于后者。答得不知道对不对，欢迎指正。（by dongding134 ）
答：对的。“前者的动态性能优于后者”具体是指Vector只有一端增、删是O(1)的，另一端O(n)；List两端增、删都是O(1)。（by yuantailing 老师）
问题：栈是否可以用列表派生队列是否可以用向量派生（by 你得算1626呐）
答：栈可以由列表派生，因为入栈、出栈操作可以对应于列表头部插入、删除。