数据结构与算法之美专栏笔记
数据结构与算法之美课后笔记
01 为什么学习数据结构和算法
一、数据结构和算法是什么
1、数据结构是指一组数据的存储结构
2、算法就是操作数据的方法
3、数据结构和算法是相辅相成的，数据结构是为算法服务的，而算法要作用在特定的数据结构之上
二、学习的重点在什么地方
数据结构和算法解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。在学习数据结构和算法的过程中，要学习它的「来历」、
「自身的特点」、「适合解决的问题」 以吸「实际的应用场景」。
-
数据结构和算法学习的精髓-复杂度分析
-
在本专栏中，重点学习20个最常用的最基础的数据结构和算法，需要我们逐一攻克。
10个数据结构: 数组，链表，栈，队列，散列表，二叉树，堆，跳表，图，Trie树
10个算法： 递归，排序，二分查找，搜索，哈希算法，贪心算法，分治算法，回溯算法，动态规划，字符串匹配算法
三、怎么样衡量数据结构和算法
- 需要引入一个衡量的标准(metri-)–时间复杂度和空间复杂度。
- 学习数据结构和算法的基石，就是要学会复杂度分析。知道怎么去分析复杂度,才能作出正确的判
断，在特定的场景下选用合适的正确的算法。而不是盲目的死记烂背，机械操作。
四、为什么学习数据结构和算法? 有3点比较重要
- 直接好处是能够有写出性能更优的代码。
- 算法,是一种解决问题的思路和方法，有机会应用到生活和事业的其他方面。
- 长期来看，大脑思考能力是个人最重要的核心竞争力，而算法是为数不多的能够有效训练大脑思考能力的途径之一。
02 复杂度分析(上)
一、什么是复杂度分析?
- 数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
- 因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
- 分别用时间复杂度和空间复杂度两个概念来描述性能问题，二 者统称为复杂度。
- 复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
二、为什么要进行复杂度分析?
- 和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
- 掌握复杂度分析，将能编写出性能更优的代码,有利于降低系统开发和维护成本。
三、如何进行复杂度分析?
1.大0表示法
- 来源
算法的执行时间与每行代码的执行次数成正比，用T(n) = 0(n))表示,其中T(n)表示算法执行总时间，f
(n)表示每行代码执行总次数，而n往往表示数据的规模。 - 特点
以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势,所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。
2.复杂度分析法则
- 单段代码看高频:比如循环。
- 多段代码取最大:比如一-段代码中有单循环和多重循环,那么取多重循环的复杂度。
- 嵌套代码求乘积:比如递归、多重循环等
- 多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。
四、常用的复杂度级别?
-
多项式阶:随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。
包括,0(1) (常数阶)、O(logn) (对数阶)、O(n) (线性阶)、O(nlogn) (线性对数阶)、O(n^2) (平方
阶)、0(n^3) (立方阶) -
非多项式阶:随着数据规模的增长，算法的执行时间和空间占用暴增,这类算法性能极差。
包括,O(2^n) (指数阶)、O(n!) (阶乘阶)。
如何掌握好复杂度分析方法?
复杂度分析关键在于多练，所谓孰能生巧。
02 复杂度分析(下)
一、 复杂度分析的4个概念
-
最坏情况时间复杂度:代码在最理想情况下执行的时间复杂度。
-
最好情况时间复杂度:代码在最坏情况下执行的时间复杂度。
-
平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示。
-
均摊时间复杂度:
在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
二、为什么要引入这4个概念?
- 同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度,所以引入这4个概念。
- 代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。
三、如何分析平均、均摊时间复杂度?
1.平均时间复杂度
代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。
2.均摊时间复杂度
两个条件满足时使用:
- 代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度;
- 低级别和高级别复杂度出现具有时序规律。均摊结果-般都等于低级别复杂度。
03 数组：为什么很多编程语言中数组都从0开始编号？
一、为什么很多编程语言的数组都是从0开始编号的?
- 从数组存储的内存模型上来看，“下标” 确切的说法就是一种”偏移”，相比从1开始编号,从0开始编号会少-次减法运算, 数组作为非常基础的数组结构，通过下标随机访问元素又是非常基础的操作，效率的优化就要尽可能的做到极致。
- 主要的原因是历史原因，C语言的设计者是从0开始计数数组下标的,之后的Java、JS等语言都进行了效仿，或者说是为了减少从C转向Java、JS等的学习成本。
二、什么是数组?
- 数组是一个线性数据结构,用一组连续的内存空间存储一组具有相同类型的数据。
- 其实数组、链表、栈、队列都是线性表结构;树、图则是非线性表结构。
三、数组和链表的面试纠错
- 数组中的元素存在一个连续的内存空间中, 而链表中的元素可以不存在于连续的内存空间。
- 数组支持随机访问，根据下标随机访问的时间复杂度是0(1);链表适合插入、删除操作，时间复杂
度为O(1)。
四、容器是否完全替代数组?
容器的优势:对于Java语言,容器封装了数组插入、删除等操作的细节,并且支持动态扩容。对于Java，一些更适合用数组的场景:
- Java的ArrayList无法存储基本类型， 需要进行装箱操作，而装箱与拆箱操作都会有一定的性能消
耗，如果特别注意性能，或者希望使用基本类型，就可以选用数组。 - 若数组大小事先已知，并且对数组只有非常简单的操作,不需要使用到ArrayList提供的大部分方
法，则可以直接使用数组。 - 多维数组时，使用数组会更加直观。
五、JVM标记清除算法
GC最基础的收集算法就是标记-清除算法，如同他们的名字一样, 此算法分为“标记”、“清除” 两个
阶段,先标记出需要回收的对象,再统- -回收标记的对象。不足有二，一是效率不高， 二是产生碎片内
存空间。
大多数主流虚拟机采用可达性分析算法来判断对象是否存活，在标记阶段，会遍历所有 GC ROOTS，将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后，清理工作才会开始。
不足：
- 效率问题。标记和清理效率都不高，但是当知道只有少量垃圾产生时会很高效。
- 空间问题。会产生不连续的内存空间碎片。
- 另外，对于数组访问越界造成无限循环，我理解是编译器的问题，对于不同的编译器，在内存分配时，会按照内存地址递增或递减的方式进行分配。老师的程序，如果是内存地址递减的方式，就会造成无限循环。
六、数组的内存寻址公式
一维数组:
$$
a[i]_address=base_address+i*typesize
$$
二维数组假设是，对于 $mn$ 的数组，$a[i]][j]$ (i < m,j < n)的地址为:
$$
a[i][j]_address=base_address + (in+j)typesize
$$
三维数组假设是，对于 $mn*q$ 的数组
$$
a[i][j][k]_address=base_address + (inq + jq + k)typesize
$$
04 链表(上): 如何实现LRU缓存淘汰算法?
一、什么是链表？
- 和数组一样，链表也是一种线性表。
- 从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。
- 链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针Next。
二、为什么使用链表？即链表的特点
-
插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。
-
和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。
三、常用链表：单链表、循环链表和双向链表
- 单链表
1）每个节点只包含一个指针，即后继指针。
2）单链表有两个特殊的节点，即首节点和尾节点。为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址null。
3）性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。 - 循环链表
1）除了尾节点的后继指针指向首节点的地址外均与单链表一致。
2）适用于存储有循环特点的数据，比如约瑟夫问题。 - 双向链表
1）节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。
2）首节点的前驱指针prev和尾节点的后继指针均指向空地址。
3）性能特点：
和单链表相比，存储相同的数据，需要消耗更多的存储空间。
插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。
对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。 - 双向循环链表：首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点。
四、选择数组还是链表？
- 插入、删除和随机访问的时间复杂度
数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。
链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。 - 数组缺点
1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。
2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。 - 链表缺点
1）内存空间消耗更大，因为需要额外的空间存储指针信息。
2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。 - 如何选择？
数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。
如果代码对内存的使用非常苛刻，那数组就更适合。
五、应用
如何分别用链表和数组实现LRU缓冲淘汰策略？
-
什么是缓存？
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。 -
为什么使用缓存？即缓存的特点
缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要用到缓存淘汰策略。 -
什么是缓存淘汰策略？
指的是当缓存被用满时清理数据的优先顺序。 -
有哪些缓存淘汰策略？
常见的3种包括先进先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frequently Used）、最近最少使用策略LRU（Least Recently Used）。 -
链表实现LRU缓存淘汰策略
当访问的数据没有存储在缓存的链表中时，直接将数据插入链表表头，时间复杂度为O(1)；当访问的数据存在于存储的链表中时，将该数据对应的节点，插入到链表表头,时间复杂度为O(n)。如果缓存被占满，则从链表尾部的数据开始清理，时间复杂度为O(1)。 -
数组实现LRU缓存淘汰策略
方式一：首位置保存最新访问数据，末尾位置优先清理
当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉末尾的数据，且剩余数组元素需整体后移一位，时间复杂度为O(n)。方式二：首位置优先清理，末尾位置保存最新访问数据
当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最后一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）
六、设计思想
时空替换思想：“用空间换时间” 与 “用时间换空间”
当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高，时间复杂度小相对较低的算法和数据结构，缓存就是空间换时间的例子。如果内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间的思路。
七、课后习题
如何判断一个字符串是否是回文字符串的问题，我想你应该听过，我们今天的题目就是基于这个问题的改造版本。如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？你有什么好的解决思路呢？相应的时间空间复杂度又是多少呢？
方法一：半栈法
- 用快慢两个指针遍历，同时用栈copy慢指针指向的data。
- 完成后，慢指针指向中间节点，耗时为N/2.
- 最后用pop栈中的data和慢指针指向的data比较，耗时也是N/2.
所以时间复杂度为：Ｏ(N)，空间复杂度因栈额外存储了一半的data，故为O(N/2)
方法二：全栈法
- 全部遍历，data压栈，额外空间消耗N
- 再次全部遍历取data，同时pop栈取data, 二者比较，时间消耗2N。
所以时间复杂度为O(3N)，空间复杂度为O(N)。
该法算法最简单，但复杂度高。可以用栈存储节点指针，而非data来改进。
方法三：硬干法
1. 一个指针从头取data，另一个指针遍历到底取data，比较二者，删除尾部节点，重复１。
２
时间复杂度高达 O(N^2)，空间复杂度却最低Ｏ(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode prev = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
ListNode next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
if (fast != null) {
slow = slow.next;
}
while (slow != null) {
if (slow.val != prev.val) {
return false;
}
slow = slow.next;
prev = prev.next;
}
return true;
}
}
https://leetcode.wang/leetcode-234-Palindrome-Linked-List.html
04 链表(下): 如何实现LRU缓存淘汰算法?
一、理解指针或引用的含义
- 含义：指针是一个变量，该变量中存的是其它变量的地址。将某个变量（对象）赋值给指针（引用），实际上就是就是将这个变量（对象）的地址赋值给指针（引用）。
- 示例：
p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。
p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。
二、警惕指针丢失和内存泄漏（单链表）
在插入和删除结点时，要注意先持有后面的结点再操作，否者一旦后面结点的前继指针被断开，就无法再访 问，导致内存泄漏。
- 插入节点
在节点a和节点b之间插入节点x，b是a的下一节点，，p指针指向节点a，则造成指针丢失和内存泄漏的代码：p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。
正确的写法是2句代码交换顺序，即：x—>next = p—>next; p—>next = x; - 删除节点
在节点a和节点b之间删除节点b，b是a的下一节点，p指针指向节点a：p—>next = p—>next—>next;
三、利用“哨兵”简化实现难度
链表的插入、删除操作，需要对插入第一个结点和删除最后一个节点做特殊处理。利用哨兵对象可以不用边界判断，链表的哨兵对象是只存指针不存数据的头结点。
-
什么是“哨兵”？
链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。 -
未引入“哨兵”的情况
如果在p节点后插入一个节点，只需2行代码即可搞定：new_node—>next = p—>next; p—>next = new_node;但，若向空链表中插入一个节点，则代码如下：
if(head == null){ head = new_node;}如果要删除节点p的后继节点，只需1行代码即可搞定：
p—>next = p—>next—>next;
但，若是删除链表的最后一个节点（链表中只剩下这个节点），则代码如下：if(head—>next == null){ head = null;}从上面的情况可以看出，针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入“哨兵”节点来解决这个问题。
-
引入“哨兵”的情况
“哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。
四、重点留意边界条件处理
经常用来检查链表是否正确的边界4个边界条件：
- 如果链表为空时
- 如果链表只包含一个节点时
- 如果链表只包含两个节点时
- 代码逻辑在处理头尾节点时
五、举例画图，辅助思考
核心思想：释放脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。
六、多写多练，没有捷径
5个常见的链表操作：
- 单链表反转
- 链表中环的检测
- 两个有序链表合并
- 删除链表倒数第n个节点
- 求链表的中间节点
练习题LeetCode对应编号：206，141，21，19，876
哨兵代码优势: 代码2为什么比代码1性能更优? 为什么代码2少了一个比较?
原因如下,首先要明确作者举两个代码例子的目的是为了说明”哨兵”的优势.
我们先分析没有哨兵的代码1,逻辑很简单,在遍历数组的时候,挨个比较每一个元素是否等于key,另外我们要还判断循环条件i是否小于n,如果相等了,那么就退出循环遍历,所以针对每一个元素判断都进行了2次比较.
代码2,一开始就把数组中最后一个元素修改成了目标key,while一次循环中,循环条件仅仅判断当前数组元素是否等于key,对于跳出循环的条件是省略的,为什么呢?因为前面说了,数组最后一个元素改成了key,最后肯定会在数组中找到key,也就是定会跳出. 于是最后我们只关注i是不是n-1就可以了,是n-1代表”原始整个数组”元素中的确没有key.
05 栈：如何实现浏览器的前进和后退功能？
一、什么是栈？
1.后进者先出，先进者后出，这就是典型的“栈”结构。
2.从栈的操作特性来看，是一种“操作受限”的线性表，只允许在端插入和删除数据。
二、为什么需要栈？
- 栈是一种操作受限的数据结构，其操作特性用数组和链表均可实现。
- 特定数据结构是对特定应用场景的抽象，数组和链表虽然使用起来更加灵活，但却暴露了太多操作接口，更容易出错。
- 所以，当某个数据集合只涉及在某端插入和删除数据，且满足后进者先出，先进者后出的操作特性时，我们应该首选栈这种数据结构。
三、如何实现栈？
-
栈的API
public class Stack<Item> { //压栈 public void push(Item item){} //弹栈 public Item pop(){} //是否为空 public boolean isEmpty(){} //栈中数据的数量 public int size(){} //返回栈中最近添加的元素而不删除它 public Item peek(){} } -
数组实现（自动扩容）
时间复杂度分析：根据均摊复杂度的定义，可以得数组实现（自动扩容）符合大多数情况是O(1)级别复杂度，个别情况是O(n)级别复杂度，比如自动扩容时，会进行完整数据的拷贝。
空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量存储空间，所以O(1)级别。我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。实现代码：（栈的数组实现）
public class StackOfArray<Item> implements Iterable<Item>{ //存储数据的数组 Item[] a = (Item[])new Object[1]; //记录元素个数N int N = 0; //构造器 public StackOfArray(){} //添加元素 public void push(Item item){ //自动扩容 if (N == a.length ) resize(2*a.length ); a[N++] = item; } //删除元素 public Item pop(){ Item item = a[--N]; a[N] = null; if (N > 0 && N == a.length / 4) resize(a.length / 2); return item; } //是否为空 public boolean isEmpty(){ return N == 0; } //元素个数 public int size(){ return N; } //改变数组容量 private void resize(int length) { Item[] temp = (Item[])new Object[length]; for (int i = 0; i < N; i++) { temp[i] = a[i]; } a = temp; }//可直接用 System.arraycopy //返回栈中最近添加的元素而不删除它 public Item peek(){ return a[N-1]; } @Override public Iterator<Item> iterator() { return new ArrayIterator(); } //内部类 class ArrayIterator implements Iterator{ //控制迭代数量 int i = N; @Override public boolean hasNext() { return i > 0; } @Override public Item next() { return a[--i]; } } } -
链表实现
时间复杂度分析：压栈和弹栈的时间复杂度均为O(1)级别，因为只需更改单个节点的索引即可。
空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量存储空间，所以O(1)级别。我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
实现代码：（栈的链表实现）public class StackOfLinked<Item> implements Iterable<Item> { //定义一个内部类，就可以直接使用类型参数 private class Node{ Item item; Node next; } private Node first; private int N; //构造器 public StackOfLinked(){} //添加 public void push(Item item){ Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; N++; } //删除 public Item pop(){ Item item = first.item; first = first.next; N--; return item; } //是否为空 public boolean isEmpty(){ return N == 0; } //元素数量 public int size(){ return N; } //返回栈中最近添加的元素而不删除它 public Item peek(){ return first.item; } @Override public Iterator<Item> iterator() { return new LinkedIterator(); } //内部类：迭代器 class LinkedIterator implements Iterator{ int i = N; Node t = first; @Override public boolean hasNext() { return i > 0; } @Override public Item next() { Item item = (Item) t.item; t = t.next; i--; return item; } } }
四、栈的应用
- 栈在函数调用中的应用
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将其中的临时变量作为栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。 - 栈在表达式求值中的应用（比如：34+13*9+44-12/3）
利用两个栈，其中一个用来保存操作数，另一个用来保存运算符。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈，若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。 - 栈在括号匹配中的应用（比如：{}{()}）
用栈保存为匹配的左括号，从左到右一次扫描字符串，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果能匹配上，则继续扫描剩下的字符串。如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明未匹配的左括号为非法格式。 - 如何实现浏览器的前进后退功能？
我们使用两个栈X和Y，我们把首次浏览的页面依次压如栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据一次放入Y栈。当点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，说明没有页面可以继续后退浏览了。当Y栈没有数据，那就说明没有页面可以点击前进浏览了。
五、课后思考
1.我们在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？
其实，我们不一定非要用栈来保存临时变量，只不过如果这个函数调用符合后进先出的特性，用栈这种数据结构来实现，是最顺理成章的选择。
从调用函数进入被调用函数，对于数据来说，变化的是什么呢？是作用域。所以根本上，只要能保证每进入一个新的函数，都是一个新的作用域就可以。而要实现这个，用栈就非常方便。在进入被调用函数的时候，分配一段栈空间给这个函数的变量，在函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。
2.我们都知道，JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那 JVM 里面的“栈”跟我们这里说的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？
内存中的堆栈和数据结构堆栈不是一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。
内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。
- 代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。
- 静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。
- 栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
- 堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。
06 队列：队列在线程池等有限资源池中的应用
一、如何理解“队列”？
- 队列是一种操作受限的线性表数据结构。
- 队列最大的特点就是先进先出。
- 最基本的操作：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。
二、顺序队列和链式队列
1、用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。
2、队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。
3、随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。
4、基于链表的实现，同样需要两个指针：head 指针和 tail 指针。分别指向链表的第一个结点和最后一个结点。入队时，tail->next= new_node, tail = tail->next；出队时，head = head->next。
三、循环队列
1、循环队列，原本数组是有头有尾的，是一条直线。把首尾相连，扳成了一个环。
2、在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，需要像环一样的循环队列。
3、要想写出没有 bug 的循环队列的实现代码，最关键的是，确定好队空和队满的判定条件。
1）队列为空的判断条件仍然是 head == tail。
2）当队满时，(tail+1)%n=head。 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。
四、阻塞队列和并发队列
1、阻塞队列
1）阻塞队列就是在队列基础上增加了阻塞操作。
2）在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
3）基于阻塞队列实现的“生产者 – 消费者模型”，可以有效地协调生产和消费的速度。
当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，比如配置几个消费者，来应对一个生产者。
2、并发队列
1）在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。
2）最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。
3）实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
五、线程池资源排队处理策略
线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？
一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。
1、基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
2、基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
（除了前面讲到队列应用在线程池请求排队的场景之外，队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。）
【思考】
1.除了线程池这种池结构会用到队列排队请求，还有哪些类似线程池结构或者场景中会用到队列的排队请求呢？
- 像windows操作系统的消息队列，略高级一些带有优先级。还有qt中的信号与槽函数机制，使用connect链接，其中的参数就是设置为把窗口界面消息放到消息队列，然后一次取出。比如优先级消息，窗口系统关闭，优先级高，则就直接执行关闭操作。
- sockets网络连接队列。
- 数据库连接队列。
- 一种集群操作，很多客户端像服务端请求资源，处理高并发大量请求。把这些请求放到队列中。
- 分布式应用中的消息队列，也是一种队列结构。
2.今天讲到并发队列，关于如何实现无锁的并发队列，网上有很多讨论。对这个问题，你怎么看？
考虑使用CAS实现无锁队列，则在入队前，获取tail位置，入队时比较tail是否发生变化，如果否，则允许入队，反之，本次入队失败。出队则是获取head位置，进行cas。
队列的实现
1.队列API
public interface Queue<T> {
public void enqueue(T item); //入队
public T dequeue(); //出队
public int size(); //统计元素数量
public boolean isNull(); //是否为空
}
2.用数组实现的队列
老师的
// 用数组实现的队列
public class ArrayQueue {
// 数组：items，数组大小：n
private String[] items;
private int n = 0;
// head表示队头下标，tail表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为capacity的数组
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入队
public boolean enqueue(String item) {
// 如果tail == n 表示队列已经满了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}
//解决数据迁移问题的入队函数
// 入队操作，将item放入队尾
public boolean enqueue(String item) {
// tail == n表示队列末尾没有空间了
if (tail == n) {
// tail ==n && head==0，表示整个队列都占满了
if (head == 0) return false;
// 数据搬移
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之后重新更新head和tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
// 出队
public String dequeue() {
// 如果head == tail 表示队列为空
if (head == tail) return null;
// 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
String ret = items[head];
++head;
return ret;
}
}
同学的
public class ArrayQueue {
//存储数据的数组
private String[] items;
//记录数组容量
private int n;
private int size;
//head记录队头索引，tail记录队尾索引
private int head = 0;
private int tail = 0;
//申请一个指定容量的队列
public ArrayQueue(int capacity){
items = new String[capacity];
n = capacity;
}
/*
* 入队：
* 1.堆满的时，入队失败
* 1.1频繁出入队，造成数组使用不连续
* 1.2在入队的时候，集中触发进行数据搬移
* 2.在末尾插入数据，注意tail指向队尾元素的索引+1
*/
public boolean enqueue(String item){
//表示队满
if(head == 0 && tail == n)
return false;
//表示需要数据搬移
else if(head != 0 && tail == n){
for (int i = head; i < tail; i++) {
items[i-head] = items[i];
}
tail = tail - head;
head = 0;
}
//将数据加入队列
items[tail++] = item;
size++;
return true;
}
//出队：1.队空时，出队失败;2.出队，head索引+1
public String dequeue(){
String res = null;
if(head == tail) return res;
res = items[head++];
size--;
return res;
}
}
2.链表实现队列
public class LinkedQueue {
//定义一个节点类
private class Node{
String value;
Node next;
}
//记录队列元素个数
private int size = 0;
//head指向队头结点，tail指向队尾节点
private Node head;
private Node tail;
//申请一个队列
public LinkedQueue(){}
//入队
public boolean enqueue(String item){
Node newNode = new Node();
newNode.value = item;
if (size == 0) head = newNode;
else tail.next = newNode;
tail = newNode;
size++;
return true;
}
//出队
public String dequeue(){
String res = null;
if(size == 0) return res;
if(size == 1) tail = null;
res = head.value;
head = head.next;
size--;
return res;
}
}
3.循环队列
//老师的
public class CircularQueue {
// 数组：items，数组大小：n
private String[] items;
private int n = 0;
// head表示队头下标，tail表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为capacity的数组
public CircularQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入队
public boolean enqueue(String item) {
// 队列满了
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
// 出队
public String dequeue() {
// 如果head == tail 表示队列为空
if (head == tail) return null;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
}
//同学的
public class LoopArrayQueue {
//存储数据的数组
private String[] items;
//记录数组容量
private int n;
private int size = 0;
//head记录队头索引，tail记录队尾索引
private int head = 0;
private int tail = 0;
//申请一个指定容量的队列
public LoopArrayQueue(int capacity){
items = new String[capacity];
n = capacity;
}
//入队：关键在于队满的条件
public boolean enqueue(String item){
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
size++;
return true;
}
//出队：关键在于队空的条件
public String dequeue(){
String res = null;
if(head == tail) return res;
res = items[head];
head = (head + 1) % n;
size--;
return res;
}
}