一楼祭天
（大佬轻喷）
------------------------------------------------
什么？一楼也有楼中楼？果断自占

导语：
你有没有在编程中遇到什么问题？或者一直想不出某种方法解决？
那么你可以看看这篇贴子
本贴是介绍基于scratch2.0来构造一些神奇的东西的。
注：本帖中可能会出现大量scratch基本操作，看不懂的请绕道或参阅其它便民设施。
切记古人言：量力撸帖，小撸怡情，大撸伤身，强撸断根。
所有内容链接: 网盘后缀：
10Ix48p51cdg9U5d8LCZj8w 提取码: kqv1
（大佬轻喷）

at人楼

一、栈
栈是限定仅在表头进行插入和删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头称为栈底（bottom）。不含元素的空表称为空栈。
就像这样：
（出栈叫做pop，入栈叫做push）
我们举个在计算机中最常见的例子
各位应该都在word文档里面写过东西吧，那应该都会用到一个东西叫做撤销，那个就是用栈做的。
这个，你在撤销的时候只能从最上面的开始撤销，如果要撤销中间的必须让它上面的所有元素出栈。
使用scratch来创建一个栈很简单，只需要新建一个链表即可
然后：
注：这里的返回只是一个伪指令罢了，栈顶的访问可以不用函数（scratch现在还没有带返回值的自定义函数）

栈结构链接：卡搭后缀：3119649-781258.htm
（看不懂后缀的直接搜栈结构也行）
说了这么多，那栈到底有什么用呢？
再举个栗子：括号匹配检验
假设一个表达式中只允许含有两种字符：‘(’和‘)’，现在需要检测括号是否匹配。()(()())和(()(()))均为
正确的
匹配方式，而()()(()和())(())都为错误的匹配方式
应该都能看懂的吧。
看不懂的直接在楼中楼提问好了

前排
支持

队列：
队列只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一样的，最早进入队列的元素先离开。在队列中，允许插入的一端叫队尾（rear），允许删除的一端叫队头（front）
就像这样：
其实用scratch实现队列很方便，根本不用考虑什么假溢出的问题。
前面过程我就不再赘述了。
队列结构链接：卡搭后缀：3129644-781258.htm

除了栈（stack）和队列（queue）之外，还有一种限定性数据结构叫双端队列（deque）
双端队列它可以在表头和表尾进行添加和删除操作，这两段称为端点1和端点2。
如图所示：
尽管双端队列表面上看起来比栈和队列灵活，然而现实生活中它没有栈和队列有用，所以不详细讨论
扩展练习：优先队列（priority_queue）
实现一个
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。
就比如你将1,8,2,3,9入队，出队时就是9,8,3,2,1
思路：
我们人脑模拟应该是这样的：
将1入队列：1
将8入队列：8,1
将2入队列：8,2,1
将3入队列：8,3,2,1
将9入队列：9,8,3,2,1
完成。
但是如果用计算机呢？
就是每次入队列时进行插入运算，把这个值插入合适的地方。
那么插入怎么做呢？
从首位开始一直到末位，用要入队的元素与每个链表里面的元素进行比较，直到找到第一个比它小的元素就停止，然后插入它之前。
由于用了插入，所以每次入队列之前队列都是有序的，所以第一个比它小的元素后面肯定都比它小。
（不贴源码，有兴趣的可以试着做一下）

递归算法：
相信各位都对递归有一些了解吧，就是自己调用自己的函数嘛。
没错，其中自己调用自己的叫做直接递归，而a调用b，b调用a的这种叫间接递归。
举个栗子（引例）：
求斐波那契数列 1,1,2,3,5,8...... 的第100位 F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)
如果我们用循环（递推）来实现，是这样的：
但是！！！用递归呢？
你甚至不用链表！
并且代码量少很多。
太高级了有木有。

前排支持

那可能一堆人说我看不懂第二个写的啥玩意。
没关系，我来分析一下。
number1和number2两个参数大家都知道，是用来进行求第100个值的。
可是这个“个数”是干嘛的呢？
它是用来判断有没有进行100次递归的（由于前两个值已经给出，所以在当绿旗被点击下面是传了参数2）
此处放张图：
别告诉我有了图你还看不懂啥意思。
（看懂的有没有感觉这玩意像栈一样）

那么现在，会了一些基础的递归后，我们来操练一下吧。
例：有100个数已经按从小到大的顺序排列，现在输入x，判断它是否在这个数列中，存在说Yes，并说出在第几个位置，不存在说No。
（100个数生成）
（冒泡排序）
（使用时请隐藏链表，这样速度会快）
该问题属于数据查找，数据查找一般方法是：顺序查找和二分查找。当数据有序时，用二分查找速度快很多。
如果这道题用顺序查找做，最差情况要找100次
但如果用二分查找做，最差情况需要找7次
log2100≈6.643856≈7
26<100<27
程序如下
hhh是不是感觉难度又上升一个档次了。
其实并不难。
这个函数的意思是：在左~右的区间内查找元素
这里的向下取整是因为scratch它支持小数。
最大的一个如果否则是来判断是否可以继续寻找，如果不能寻找肯定是左=右的情况，也就是找不到。
第二大的如果否则用来判断是否要输出（说），这个应该不难
最里面的一个如果否则是来判断在前半段找还是后半段找。
用scratch写递归程序注意事项：
在函数里面有循环，循环里面有调用本身的情况下最好不要用递归，因为scratch用的是全局变量，不过你依然可以用SteveScratch来创造运行时变量

大佬...小白表示 看不懂

前排围观

扩展练习：
刚才我们说到，二分查找在数据有序时，它的速度快很多。
我们不禁想起之前的那个优先队列（priority_queue），它插入时用的是顺序查找啊！
让我们把它改成二分查找！
各位脑子里：
加油吧