数据结构与算法之美2_栈&队列&递归

数据结构与算法之美2_栈&队列&递归



本系列文章,算是《极客时间》的《数据结构与算法之美》专栏的读书笔记。

只是一些个人心得与练习,想要得到更详细更好更系统的学习,请去 极客时间APP订阅专栏。

跟着专栏学了好久,也该有点成果不是;

正好趁着最后的几篇练习章节,把之前学到的,做个笔记总结一下。


笔记列表




定义

栈是一种操作受限的线性表数据结构,只允许在一端插入和删除数据。

特性

先进后出,后进先出

分类

  • 顺序栈

  • 链式栈

应用

  • 函数调用
  • 表达式求值
  • 括号匹配


队列

定义

队列是一种操作受限的线性表数据结构,允许在两端插入和删除数据。

特性

先进先出,后进后出

分类

  • 顺序队列
  • 链式队列

应用

  • 循环队列
    • 判断循环队列为空:head == tail
    • 判断循环队列为满:(tail+1)%n == head
  • 阻塞队列
    • 在队列为空的时候,获取数据操作被阻塞,直到队列中有数据才能获取数据,再返回。
    • 在队列为满的时候,插入数据操作被阻塞,直到队列中有空间才能插入数据,再返回。
  • 并发队列
    • 线程安全的队列。
    • 最简单的方法就是在插入数据、获取数据处加锁。


递归

定义

递归是程序调用自身的编程技巧。

递归需要满足的三个条件

  1. 一个问题的解可以分解为几个子问题的解
  2. 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
  3. 存在递归终止条件

如何解

关键在于找到如何将大问题分解为小问题的规律,并基于此写出递推公式,找到终止条件。

注意

  • 警惕堆栈溢出
    • 通过限制最大深度来做限制
  • 警惕重复计算
    • 每次计算前查看是否计算过,将计算过得值存储。
  • 在函数调用数量达时,时间效率会很高
  • 因为防止重复计算,空间复杂度也不是O(1)



练习

必知必会

  • 用数组实现一个顺序栈
  • 用链表实现一个链式栈
  • 编程模拟实现浏览器的前进、后退功能

LeetCode


队列

必知必会

  • 用数组实现一个顺序队列
  • 用链表实现一个链式队列
  • 实现一个循环队列

LeetCode


递归

必知必会

  • 编程实现斐波那契数列求值 f(n) = f(n-1) + f(n-2)
  • 编程实现求阶乘 n!
  • 编程实现一组数据结合的全排列

LeetCode