算法之美2 - 线性表

àì夳堔傛蜴生んèń 2022-03-02 10:11 186阅读 0赞

## 线性表 ##

*  线性表：数组、链表、栈、队列
 *  拓展：跳表

--------------------

### 05 | 数组：为什么很多编程语言中数组都从0开始编号？ ###

> 数组如何实现随机访问

1）数组是一种线性数据结构，用连续的存储空间存储相同类型数据

I）线性表：数组、链表、队列、栈 非线性表：树、图

II）连续的内存空间、相同类型的数据，所以数组可以随机访问，但对数组进行删除插入，为了保证数组的连续性，就要做大量的数据搬移工作

1.  数组如何实现下标随机访问。

引入数组再内存种的分配图，得出**寻址公式**

1.  纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O（1）。即便是排好的数组，用二分查找，时间复杂度也是O（logn）。

正确表述：数组支持随机访问，根据下标随机访问的时间复杂度为O（1）

> 低效的插入和删除

1） 插入：从最好O(1) 最坏O(n) 平均O(n)

2） 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把新的元素，插入到第k个位置，此处复杂度为O(1)。

3） 删除：从最好O(1) 最坏O(n) 平均O(n)

4） 多次删除集中在一起，提高删除效率

记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

> 警惕数组的访问越界问题

用C语言循环的越界访问的例子说明访问越界的bug。此例在《C陷阱与缺陷》出现过，**如果用来编译这段程序的编译器按照内存地址递减的方式给变量分配内存，那么内存中的i将会被置为0，则为死循环永远出不去**。

无限循环的问题，我认为内存分配是从后往前分配的。例如，在Excel中从上往下拉4个格子，变量i会先被分配到第4个格子的内存，然后变量arr往上数分配3个格子的内存，但arr的数据是从分配3个格子的第一个格子从上往下存储数据的，当访问第3索引时，这时刚好访问到第4个格子变量i的内存。

1）不同的语言对数组访问越界的处理方式不同，即便是同一种语言，不同的编译器处理的方式也不同。

2）数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。

3）我觉得那个例子，栈是由高到低位增长的，所以，i和数组的数据从高位地址到低位地址依次是：i, a\[2\], a\[1\], a\[0\]。a\[3\]通过寻址公式，计算得到地址正好是i的存储地址，所以a\[3\]=0，就相当于i=0。

> 容器能否完全替代数组

相比于数字，java中的 ArrayList 最大的优势就是**可以将很多数组操作的细节封装起来**，并**支持动态扩容**。一旦超过数组容量，扩容时比较耗内存，因为涉及到内存申请和数据搬移。

数组适合的场景：

1） Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。

2） 若数据大小事先已知，并且涉及的数据操作非常简单，可以使用数组

3） 表示多维数组时，数组往往更加直观。

4） 业务开发容器即可；底层开发，如网络框架，性能优化，选择数组。

> 为什么很多编程语言中数组都从0开始编号？

从**数组存储的内存模型**上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a\[0\] 就是偏移为 0 的位置，也就是首地址，a\[k\] 就表示偏移 k 个 type\_size 的位置，

1） 从偏移角度理解a\[0\] 0为偏移量，如果从1计数，会多出K-1，多了一次减法指令，增加cpu负担。为什么循环要写成for(int i = 0;i<3;i++) 而不是for(int i = 0 ;i<=2;i++)。第一个直接就可以算出3-0 = 3 有三个数据，而后者 2-0+1个数据，多出1个加法运算。

2） 最主要的原因可能是历史原因，C 语言设计者用 0 开始计数数组下标

> 思考

1）前面我基于数组的原理引出 JVM 的标记清除垃圾回收算法的核心理念。我不知道你是否使用 Java 语言，理解 JVM，如果你熟悉，可以在评论区回顾下你理解的标记清除垃圾回收算法。

2）前面我们讲到一维数组的内存寻址公式，那你可以思考一下，类比一下，二维数组的内存寻址公式是怎样的呢？

对于 m \* n 的数组，a \[ i \]\[ j \] (i < m,j < n)的地址为：

address = base\_address + ( i \* n + j) \* type\_size

> 面试题

我在面试的时候，常常会问数组和链表的区别：

“链表适合插入、删除，时间复杂度 O(1)；数组适合查找，**数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)**”。

--------------------

### 06 | 链表（上）：如何实现LRU缓存淘汰算法? ###

> 一、什么是链表？

1.和数组一样，链表也是一种线性表。

2.从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。

3.链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。

> 二、为什么使用链表？即链表的特点

1.插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。

2.和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

> 三、常用链表：单链表、循环链表和双向链表

1.单链表

1）每个节点只包含一个指针，即后继指针。

2）单链表有两个特殊的节点，即头结点和尾结点。为什么特殊？头结点用来记录链表的基地址，尾节点的后继指针指向空地址null。

3）性能特点：插入和删除节点的时间复杂度为O(1），查找的时间复杂度为O(n)。

2.循环链表

1）除了尾结点的后继指针指向首结点的地址外均与单链表一致。

2）适用于具有环型结构特点的数据，比如约瑟夫问题。

3.双向链表

1）结点除了存储数据外，还有两个指针分别指向前一个结点地址（前驱指针prev）和下一个结点地址（后继指针next）。

2）首结点的前驱指针prev和尾结点的后继指针均指向空地址。

3）性能特点：

和单链表相比，存储相同的数据，需要消耗更多的存储空间。

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。以删除操作为例，删除操作分为2种情况：给定数据值删除对应结点和给定结点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。

对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

4.双向循环链表：首结点的前驱指针指向尾结点，尾结点的后继指针指向首结点。

> 四、选择数组还是链表？

1.插入、删除和随机访问的时间复杂度

数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。

链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。

2.数组缺点

1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。

2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。

3.链表缺点

1）内存空间消耗更大，因为需要额外的空间存储指针信息。

2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。

4.如何选择？

数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。

如果代码对内存的使用非常苛刻，那数组就更适合。

> 五、设计思想

时空替换思想：“用空间换时间” 与 “用时间换空间”

当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高，时间复杂度小相对较低的算法和数据结构，缓存就是空间换时间的例子。如果内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间的思路。

> 六、有关缓存

1）什么是缓存？

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。

2）为什么使用缓存？即缓存的特点

缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要用到缓存淘汰策略。

3）什么是缓存淘汰策略？

指的是当缓存被用满时清理数据的优先顺序。

4）有哪些缓存淘汰策略？

常见的3种包括先进先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。

LFU最少使用策略是根据节点访问的次数来判断的：如果一个数据在**最近一段时间内使用次数**很少，那么在将来一段时间内被使用的可能性也很小，每次删除的都是访问次数最少的那个；

LRU最近最少使用策略是根据时间的纬度来的：如果一个数据在**最近一段时间没有被访问到**，那么在将来它被访问的可能性也很小，每次删除的都是最后那个没有被访问的。

> 七、如何基于链表实现 LRU 缓存淘汰算法？

我的思路是这样的：我们维护一个**有序单链表**，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1.  如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2.  如果此数据没有在缓存链表中，又可以分为两种情况：

*  如果此时缓存未满，则将此结点直接插入到链表的头部；
 *  如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

这样我们就用链表实现了一个 LRU 缓存，是不是很简单？

现在我们来看下 m 缓存访问的时间复杂度是多少。因为不管缓存有没有满，我们都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度为 O(n)。

实际上，我们可以继续优化这个实现思路，比如引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。

> 六、除了基于链表的实现思路，实际上还可以用数组来实现 LRU 缓存淘汰策略。如何利用数组实现 LRU 缓存淘汰策略呢？

1、如何用数组实现LRU缓存淘汰策略：维护一个**有序的数组a**，越靠近数组尾部的元素是越早访问的。

1）当前访问数据在缓存中，遍历数组将当前数据对应元素item前的元素后移一位，并将item放入0位置。

2）当前访问数据不在缓存，又分为两种情况

*  缓存未满，则将当前数组所有元素后移一位，再将当前数据对应元素放入a\[0\]。
 *  缓存满了，先删除数组最后一个元素删除，然后把数组所有元素后移一位，最后将当前数据对应元素放入a\[0\]。

方式一：首位置保存最新访问数据，末尾位置优先清理

当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。

方式二：首位置优先清理，末尾位置保存最新访问数据

当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）

> 六、思考

如何判断一个字符串是否是回文字符串的问题，我想你应该听过，我们今天的思题目就是基于这个问题的改造版本。如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？你有什么好的解决思路呢？相应的时间空间复杂度又是多少呢？

思路一：

1）快慢指针定位中间节点

2）从中间节点对后半部分逆序

3）前后半部分比较，判断是否为回文

4）后半部分逆序复原

时间复杂度O(n), 空间复杂度O(1)

思路二：

由于回文串最重要的就是对称，那么最重要的问题就是找到那个中心，用快指针每步两格走，当他到达链表末端的时候，慢指针刚好到达中心，慢指针在过来的这趟路上还做了一件事，他把走过的节点反向了，在中心点再开辟一个新的指针用于往回走，而慢指针继续向前，当慢指针扫完整个链表，就可以判断这是回文串，否则就提前退出，总的来说时间复杂度按慢指针遍历一遍来算是O(n),空间复杂度因为只开辟了3个额外的辅助，所以是o(1)

1）快慢两个指针定位链表中点，同时逆序前半部分链表

2）已逆序的前半部分与后半部分进行比较

3）再次逆序前半部分链表

--------------------

### 07 | 链表（下）：如何轻松写出正确的链表代码？ ###

*  理解指针或引用的含义

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

*  警惕指针丢失和内存泄漏

在插入和删除结点时，要注意先持有后面的结点再操作，否者一旦后面结点的前继指针被断开，就无法再访问，导致内存泄漏。

*  利用\*\*\*哨兵\*\*\*简化难度

链表的插入、删除操作，需要对插入第一个结点和删除最后一个节点做特殊处理。利用哨兵对象可以不用边界判断，链表的哨兵对象是只存指针不存数据的头结点。

*  重点留意边界条件处理

操作链表时要考虑链表为空、一个结点、两个结点、头结点、尾结点的情况。学习数据结构和算法主要是掌握一系列思想，能在其它的编码中也养成考虑边界的习惯。

*  举例画图，辅助思考

对于比较复杂的操作，可以用纸笔画一画，释放脑容量来做逻辑处理（时间换空间思想），也便于完成后的检查。

*  多写多练，没有捷径

孰能生巧，不管是什么算法，只有经过反复的练习，才能信手拈来。

*  思考

今天我们讲到用哨兵来简化编码实现，你是否还能够想到其他场景，利用哨兵可以大大地简化编码难度？

--------------------

### 08 | 栈：如何实现浏览器的前进和后退功能？ ###

> 一、什么是栈？

叠盘子

1.  后进者先出，先进者后出，这就是典型的“栈”结构。
2.  从栈的操作特性来看，是一种“操作受限”的线性表，只允许在端插入和删除数据。

> 二、为什么需要栈？

1.  栈是一种操作受限的数据结构，其操作特性用数组和链表均可实现。顺序栈和链式栈
2.  但，任何数据结构都是对特定应用场景的抽象，数组和链表虽然使用起来更加灵活，但却暴露了几乎所有的操作，难免会引发错误操作的风险。
3.  所以，当某个数据集合只涉及在某端插入和删除数据，且满足后进者先出，先进者后出的操作特性时，我们应该首选栈这种数据结构。

> 三、如何实现栈？

1.栈的API

class Stack():
        def __init__(st,size):
            st.stack=[]
            st.size=size
            st.top=-1
    
        def empty(st):
            if st.top==-1:
                return True
            else:
                return False
    
        def full(st):
            if st.top==st.size:
                return True
            else:
                return False
    
        def push(st,data):
            if st.full():
                print "Stack is full"
            else:
                st.stack.append(data)
                st.top=st.top+1
    
        def pop(st):
            if st.empty():
                print "Stack is empty"
            else:
                st.top=st.top-1

2.数组实现（自动扩容）

时间复杂度分析：根据均摊复杂度的定义，可以得数组实现（自动扩容）符合大多数情况是O(1)级别复杂度，个别情况是O(n)级别复杂度，比如自动扩容时，会进行完整数据的拷贝。

空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量存储空间，所以O(1)级别。我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

3.链表实现

时间复杂度分析：压栈和弹栈的时间复杂度均为O(1)级别，因为只需更改单个节点的索引即可。

> 四、栈的应用

1.栈在函数调用中的应用

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将其中的临时变量作为栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

2.栈在表达式求值中的应用（比如：34+13\*9+44-12/3）

利用**两个栈**，其中一个用来保存操作数，另一个用来保存运算符。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈，若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。

3.栈在括号匹配中的应用（比如：\{\}\{ ()\}）

用栈保存为匹配的左括号，从左到右一次扫描字符串，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果能匹配上，则继续扫描剩下的字符串。如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明未匹配的左括号为非法格式。

4.如何实现浏览器的前进后退功能？

我们使用两个栈X和Y，我们把首次浏览的页面依次压如栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据一次放入Y栈。当点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，说明没有页面可以继续后退浏览了。当Y栈没有数据，那就说明没有页面可以点击前进浏览了。

> 五、思考

1.我们在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？

答：因为**函数调用的执行顺序符合后进者先出，先进者后出的特点**。比如函数中的局部变量的生命周期的长短是先定义的生命周期长，后定义的生命周期短；还有函数中调用函数也是这样，先开始执行的函数只有等到内部调用的其他函数执行完毕，该函数才能执行结束。  
正是由于函数调用的这些特点，根据数据结构是特定应用场景的抽象的原则，我们优先考虑栈结构。

2.我们都知道，JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那 JVM 里面的“栈”跟我们这里说的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？

答：JVM里面的栈和我们这里说的是一回事，被称为方法栈。和前面函数调用的作用是一致的，用来存储方法中的局部变量。

3.内存中的堆栈和数据结构堆栈

内存中的堆栈和数据结构堆栈不是一个概念，可以说**内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构**。

内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。

代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。

静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。

栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。

堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。

--------------------

### 09 | 队列：队列在线程池等有限资源池中的应用 ###

排队买票

> 一、什么是队列？

1.  先进者先出，这就是典型的“队列”结构。
2.  支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。
3.  所以，和栈一样，队列也是一种操作受限的线性表。
4.  实现：由数组和链表来实现
5.  队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

> 二、如何实现队列？

1.队列API

class Queue():
        def __init__(qu, size):
            qu.queue = []
            qu.size = size
            qu.front = -1
            qu.rear = -1
    
        def empty(qu):
            if qu.front == qu.rear:
                return True
            else:
                return False
    
        def full(qu):
            if (qu.rear + 1) % qu.size == qu.front:
                return True
            else:
                return False
    
        def enQueue(qu, data):
            if qu.full():
                print "Queue is full"
            else:
                qu.queue.append(data)
                qu.rear += 1
    
        def outQueue(qu):
            if qu.empty():
                print("Queue is empty")
            else:
                qu.front -= 1

2.数组实现（顺序队列）：

顺序队列存在一个问题， tail 指针移动到数组最大下标时，即使数组中还有空闲空间，也无法继续往队列中添加数据了。

解决方法是在入队列时，如果没有空闲空间，就触发一次**数据搬运**，将 head 到 tail 之间的数据，整体搬运到数组的 0 到 tail - head 位置。

3.链表实现（链式队列）：

链式队列与顺序队列的区别是没有容量限制，在请求排队的场景下，如果排队的请求数量过多，请求处理的响应时间会过长。

4.循环队列（基于数组）：

循环队列是为了解决顺序队列在 tail == n 时，需要数据搬运操作的问题。

队列为空时可以根据 head == tail 来判断。循环队列满时，tail 指针位置不存储数据，所以队满判断公式为：

(tail + 1) % n = head

你有没有发现，当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。

class MyCircularQueue(object):
    
        def __init__(self, k):
            """ Initialize your data structure here. Set the size of the queue to be k. :type k: int """
            self.queue = [None] * k
            self.k = k
            self.front = 0
            self.rear = 0
    
        def enQueue(self, value):
            """ 如果队列未满，则在队尾插入元素，时间复杂度O(1) Insert an element into the circular queue. Return true if the operation is successful. :type value: int :rtype: bool """
            if not self.isFull():
                self.queue[self.rear] = value
                self.rear = (self.rear + 1) % self.k
                return True
            else:
                return False
                
    
        def deQueue(self):
            """ 如果队列不为空，则删除队头的元素，时间复杂度O(1) Delete an element from the circular queue. Return true if the operation is successful. :rtype: bool """
            if not self.isEmpty():
                data = self.queue[self.front]
                self.queue[self.front] = None
                self.front = (self.front + 1) % self.k
                return True
            else:
                return False
    
        def Front(self):
            """ Get the front item from the queue. :rtype: int """
            if not self.isEmpty():
                data = self.queue[self.front]
                return data
    
        def Rear(self):
            """ Get the last item from the queue. :rtype: int """
            if not self.isEmpty():
                data = self.queue[(self.rear - 1 + self.k) % self.k]
                return data
            
        def QueueLength(self):
            # 返回当前队列的长度
    
            return (self.rear - self.front + self.k) % self.k
        
        def isEmpty(self):
            """ Checks whether the circular queue is empty or not. :rtype: bool """
            if self.rear == self.front:
                return True
            else:
                return False
    
        def isFull(self):
            """ Checks whether the circular queue is full or not. :rtype: bool """
            if (self.rear + 1) % self.k == self.front:
                return True
            else:
                return False

> 三、队列有哪些常见的应用？

1.阻塞队列

1）在队列的基础上增加阻塞操作，就成了阻塞队列。

2）阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。

3）从上面的定义可以看出这就是一个“生产者-消费者模型”。这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，比如配置几个消费者，来应对一个生产者。

2.并发队列

1）在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。

2）并发队列简单的实现就是在enqueue()、dequeue()方法上**加锁**，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。

3）实际上，基于数组的循环队列利用CAS**原子操作**，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

4）在考虑线程安全时，需要用到并发队列，并发队列同一时刻只允许一个插入操作，但是允许多个读操作。

1.  场景

在资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

> 四、思考

1.除了线程池这种池结构会用到队列排队请求，还有哪些类似线程池结构或者场景中会用到队列的排队请求呢？

2.今天讲到并发队列，关于如何实现无锁的并发队列，网上有很多讨论。对这个问题，你怎么看？

--------------------

### 17 | 跳表：为什么Redis一定要用跳表来实现有序集合？ ###

> 什么是跳表

为一个值有序的链表建立**多级索引**，比如每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。如下图所示，其中down表示**down指针**，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。

![14753c824a5ee4a976ea799727adc78e.jpg][]

> 跳表的时间复杂度

1.计算跳表的高度

如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那第1级索引的节点个数大约是n/2，第2级索引的节点个数大约是n/4，依次类推，第k级索引的节点个数就是n/(2k)。假设索引有h级别，最高级的索引有2个节点，则有n/(2h)=2，得出h=log2n-1，包含原始链表这一层，整个跳表的高度就是log2n。

2.计算跳表的时间复杂度

假设我们在跳表中查询某个数据的时候，如果每一层都遍历m个节点，那在跳表中查询一个数据的时间复杂度就是O(m\*logn)。那这个m是多少呢？如下图所示，假设我们要查找的数据是x，在第k级索引中，我们遍历到y节点之后，发现x大于y，小于后面的节点z，所以我们通过y的down指针，从第k级下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个节点（包含y和z），所以，我们在k-1级索引中最多只需要遍历3个节点，以此类推，每一级索引都最多只需要遍历3个节点。所以m=3。因此在跳表中查询某个数据的时间复杂度就是**O(logn)**。

![d03bef9a64a0368e6a0d23ace8bd450c.jpg][]

> 跳表是不是很浪费内存

1.计算索引的节点总数

如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2，等比数列求和n-1，所以跳表的空间复杂度为**O(n)**。

2.如何降低索引占用的内存空间

如果链表有n个节点，每3或5个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以3为例）：n/3，n/9，n/27，…，27，9，3，1，等比数列求和n/2，所以跳表的空间复杂度为O(n)，和每2个节点抽取一次相比，时间复杂度要低不少呢。

> 高效的动态插入和删除

跳表本质上就是链表，插入和删除操时间复杂度就为O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时，但在跳表中这个查找操作的时间复杂度是O(logn)，所以，跳表的插入和删除操作的是时间复杂度也是**O(logn)**。

> 跳表索引动态更新

跳表是通过**随机函数**来维护前面提到的“平衡性”。

当往跳表中插入数据的时候，可以选择同时将这个数据插入到部分索引层中，那么如何选择这个索引层呢？可以通过随机函数来决定将这个节点插入到哪几级索引中，比如随机函数生成了值K，那就可以把这个节点添加到第1级到第K级索引中。

> 为什么Redis一定要用跳表来实现有序集合？

Redis 中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。不过散列表我们后面才会讲到，所以我们现在暂且忽略这部分。如果你去查看 Redis 的开发手册，就会发现，Redis 中的有序集合支持的核心操作主要有下面这几个：

*  插入一个数据；
 *  删除一个数据；
 *  查找一个数据；
 *  按照区间查找数据（比如查找值在 \[100, 356\] 之间的数据）；
 *  迭代输出有序序列。

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。

对于按照**区间查找**数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。

当然，Redis 之所以用跳表来实现有序集合，还有其他原因，比如，**跳表更容易代码实现**。虽然跳表的实现也不简单，但比起红黑树来说还是好懂、好写多了，而简单就意味着可读性好，不容易出错。

还有，**跳表更加灵活**，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

不过，跳表也不能完全替代红黑树。因为红黑树比跳表的出现要早一些，很多编程语言中的 Map 类型都是通过红黑树来实现的。我们做业务开发的时候，直接拿来用就可以了，不用费劲自己去实现一个红黑树，但是跳表并没有一个现成的实现，所以在开发中，如果你想使用跳表，必须要自己实现。

> 思考

在今天的内容中，对于跳表的时间复杂度分析，我分析了每两个结点提取一个结点作为索引的时间复杂度。如果每三个或者五个结点提取一个结点作为上级索引，对应的在跳表中查询数据的时间复杂度是多少呢？

[14753c824a5ee4a976ea799727adc78e.jpg]: /images/20220302/df5ec47571424f3e8adbfbc57e50ee62.png
[d03bef9a64a0368e6a0d23ace8bd450c.jpg]: /images/20220302/07716d77783344e3b0bae327417a8b03.png