当前位置： 首页 >> 数据结构与算法 >> 栈、队列与递归

---

栈、队列与递归

2020-07-04 18:09:33 星期六  阅读：2160

---

####栈 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。不会像数组或者链表暴露太多接口会导致程序不可控； ####栈的实现方式 `顺序栈——用数组实现` 特点：大小固定，初始化栈的时候就需要确定大小。需要使用动态扩容的数组来实现栈空间不够时的场景（开发中不常用） `链式栈——用链表实现` 特点：大小不固定，但是需要额外的空间存储next指针。 ####应用场景——在函数调用中的作用 操作系统给每个线程分配一块独立的内存空间，这块内存被组织成”栈“这种数据结构，用来存储函数调用时的临时变量，每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完时，返回之后，将这个函数对应的栈帧出栈。比如，下面的代码，main函数调用add函数 ``` int main() { int a = 1; int ret = 0; int res = 0; ret = add(3, 5); res = a + ret; printf("%d", res); reuturn 0; } int add(int x, int y) { int sum = 0; sum = x + y; return sum; } ``` 栈在表示求值的应用：编译器通过两个栈来实现的，一个保存操作数的栈，另一个是保存运算符的栈，从左向右遍历表达式，当遇到数字，我们直接压入操作数栈，当遇到运算符，就与运算符栈的栈顶元素进行比较。 ####如何实现浏览器的前进和后退功能？ 这个实际上是使用两个栈来完成的， 比如我们顺序查看了a/b/c三个网页，我们依次把a/b/c压入栈1，当页面从c退后到a时，我们就依次把c/b从栈1中压入到栈2中。此时如果我从a页面访问 了d页面，则就再也返回不到b/c页面了。因此一旦从a访问了d，就会把栈2清空。 需要注意的点： `内存中的堆栈和数据结构的堆栈不是一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。` ####队列 队列与栈的区别如下：相比栈，队列是先进先出。但是跟栈一样，队列也是一种操作受限的线性表数据结构。 对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过”队列“这种数据结构来实现请求队列。 队列的实现方式 `顺序队列——用数组实现` `链式队列——用链表实现` 循环队列的优点，解决了传统队列入队操作需要搬移数据的性能问题。但是循环队列的代码实现要比非循环队列难的多。最关键的是确定好队空和对满的判定条件。 ####阻塞队列与并发队列 阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。这个定义其实也就是”生产者——消费者“模型。 在多线程的情况下，会有多个线程同时操作队列，这时候就会存在线程安全问题，通过锁的机制实现线程安全的队列叫做并发队列。 ####递归 递归是数据结构和算法所有内容中两个最难的难点之一，另外一个是动态规划。 递归的特点 ``` 代码简洁； 表达能力强； 空间复杂度高； 有堆栈溢出的风险； 存在重复计算 过多的函数调用会比较耗时 ``` 满足递归的三个条件 ``` 一个问题可以分解为几个子问题求解； 这个问题与分解后的子问题，除了数据规模不同，求解思路完全一样； 存在递归终止条件 ``` 写递归代码的关键是写出递归公式，找到终止条件。也就是说，找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 递归代码通常非常难理解，我们不需要试图想清楚递归的过程，我们应该把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。 下面是一个简单的递归代码 ``` >>> def f(n): ... if (n == 1) : ... return 1 ... else: ... return f(n - 1 ) + 1 ``` ####递归代码的注意事项 `警惕堆栈溢出`——也就是说，因为递归层层调用时产生的临时变量都会压入内存栈，如果递归深度加深，会导致栈溢出的风险，应对方案是在代码中限制递归调用的最大深度，当递归调用超过一定深度后，比如（1000），直接返回报错。 `警惕重复计算`——递归计算中有很多计算指标其实是已经计算过的，如果我们通过一个数据结构（比如散列表）来保存已经求解过的指标，下次再调用时就不用计算了。 因为递归本来是借助栈来实现的，`任何代码都可以改写成看上去不是递归代码的样子`（也就是使用迭代循环来实现）。但是也并没有解决前面提到的一些问题。