Scratch利用“堆栈”实现元素交换

堆栈可以实现两个元素的交换。由于在编程中，经常要将两个元素互换，因此研究各种互换方法就变得非常重要。

 

过去有种提法，认为程序=算法+数据结构。今天我们就谈谈数据结构中的“堆栈”。

 

栈的概念：堆栈(stack)，有的书上也叫栈，是计算机内存中开辟的一块空间。它有一个很特殊的地方：只能在栈顶操作。所以它是先进后出(LIFO)的。

 

 

栈的操作：主要有入栈(Push)和出栈(Pop)两种操作。其中入栈是在栈顶加入一个元素，出栈是将栈顶的元素取出。

 

栈的作用：栈最大的作用是保护现场，以便于系统处理更高优先级的响应。

 

举例来说，假设小明正在家里写作业。突然门铃响了，打开门一看原来是快递到了。正在接收快递的时候，烧水的水壶汽笛响了，水这时候烧开了。

 

对应的操作可能是这样的：正在处理写作业；快递到了，响应中断，将作业写到哪里入栈，转去处理收快递；水烧开了，再次响应中断，将快递接收情况入栈，转去处理水烧开了；烧开水处理结束后，将快递接收情况出栈，继续处理收快递；收快递处理结束后，将写作业出栈，继续处理作业，直至作业完成。

 

流程图如下所示：

 

 

利用堆栈实现交换：堆栈还有一个用处是交换两个元素。如下图所示：

 

开始的时候，苹果在左侧盘子里，香蕉在右侧盘子里。

 

将苹果先入栈，再将香蕉入栈，变为上图。

 

再将香蕉出栈，放在左侧盘子里。

 

最后将苹果出栈，放在右侧盘子里，就实现了苹果和香蕉位置的互换。

 

程序实现：Scratch中没有“堆栈”这种数据结构，可以用列表来模拟。

 

入栈相当于将对象插入列表的第一项。

 

注意到入栈操作必须带有具体对象，所以要先判断。如果堆栈已满，则不能执行入栈操作。如果入栈成功，则将当前对象清空。

 

出栈相当于删除列表的第一项。

 

注意到出栈操作必须没有具体对象，所以要先判断。如果堆栈已空，则不能执行出栈操作。如果出栈成功，将栈顶元素设置为当前对象。

以上是堆栈功能部分的实现。配合其他部分，利用堆栈实现两个元素互换的过程如下：

 

 

后记：为什么现在不提“程序=算法+数据结构”这种说法了呢？

 

引用知乎上的一个回复：“程序这个概念已经膨胀到了需要用操作系统管理，用编译器来抽象化成高级语言，而且这些本身还是程序。数据根据特征，存储方式，读写频率等等有着极其复杂的相适应的算法需求”。

 

简单的说，算法和数据是不可分割的，有着深刻的联系。

始发于微信公众号：
全不知老师