敲黑板！线性结构设计的知识要点

      童鞋们好，昨天的直播课你学会了吗？今天，我们一起来复习一下昨天的知识点吧，敲黑板了！做好笔记哦，记得回答课后作业！

      1. 线性结构的定义

      线性结构是一个有序数据元素的集合。

      常用的线性结构有：线性表，栈，队列。

      本节要讲解的栈和队列通常都是使用线性表来实现的。

      2. 线性结构的要素

      1) 集合中必存在唯一的一个"第一个元素"；

      2) 集合中必存在唯一的一个"最后的元素"；

      3) 数据元素至多有一个"后继"；

      4) 数据元素至多有一个"前驱"。

      3. 线性表

      3.1 一维数组

      一维数组在内存中是连续存储的，它是一种典型的顺序存储结构。

      3.2 链表

      链表在内存中是分散存储的，可以通过节点上的后继来寻址下一个节点。它是一种典型的链式存储结构。

      链表又分为单向链表，双向链表，循环链表和双向循环链表。

      4. 栈

      4.1栈的特征

      栈的特征很明显：只有一个口，数据项的进出都是通过这个口完成，先入栈的数据保存在栈的底部（栈底），后入栈的数据保存在栈的顶部（栈顶）。因此栈的特征经常被描述为先进后出或后进先出。

      栈的操作主要有3个

      1) 入栈（push）：将一个数据项放入栈中

      2) 出栈（pop）：将处于栈顶的数据项从栈顶移除

      3) 查看栈顶（peek）：查看当前栈顶的数据项，但不从栈中移除

      4.2栈的实现

      从JDK1.0版本开始，JDK中的Stack类就模拟实现了栈的相关功能，它的底层是基于一维数组实现的。

      我们也可以自己利用数组来实现一个栈

      4.3栈的应用

      1) 有入栈顺序①②③④⑤，入栈过程中允许出栈，以下哪个出栈顺序不正确？

A. ⑤④③②①         B. ①②③④⑤         C. ①③②⑤④          D. ①②⑤③④

      分析：

      A选项：①②③④⑤全部入栈后再依次出栈得到⑤④③②①

      B选项：①入然后立刻出，②入然后立刻出…  得到①②③④⑤

      C选项：①入然后立刻出，②③入然后③出②出，④⑤入然后⑤出④出, 得到①③②⑤④

      D选项：①入然后立刻出，②入然后立刻出, ③④⑤入，然后⑤出， 此时栈顶是④，不可能是③。所以此选项是不正确的。

      答案是：D

      2) 计算一个四则运算表达式的值

      思路：设计两个栈，一个表示操作数栈，一个表示运算符栈，依次将数字和运算符入栈。并根据运算符的优先级进行计算。

      运算符优先级

       () > 乘除法 > 加减法

      运算符的处理

      符号入栈前先检查栈顶，如果当前入栈符号低于栈顶符号优先级，则取出栈顶符号对操作数栈进行计算,将计算结果放入操作数栈,再将当前入栈符号入符号栈。

      括号的处理

      遇到左括号直接将其入栈。

      遇到右括号立刻计算操作数和运算符，直至遇到左括号出栈结束。

      时间原因课上不现场编写代码实现了，详细分析和代码参照作者简书： https://www.jianshu.com/p/3b42150bcc33。

      5. 队列

      5.1 队列的特征

      队列的特征很明显：有两个口，数据项的进出都是通过的口完成，先入队的数据保存在队列的头部（队头），后入队的数据保存在队的尾部（队尾）。因此队列的特征经常被描述为先进先出或后进后出 。

      队列的操作主要有3个

      1) 入队（offer）：将一个数据项放入队列中

      2) 出队（poll）：将处于队头的数据项从队列中移除

      3) 查看队头（peek）：查看当前对头的数据项，但不从队列中移除

      5.2 队列的实现

      从JDK1.0版本开始，JDK中的LinkedList类就模拟实现了队列的相关功能，它的底层是基于链表实现的。

      我们也可以自己利用链表来实现一个队列

      5.3 优先队列

      优先队列是一种特殊的队列，数据项在入队时，由于存在优先度的情况，可能出现后入队的插入在前面的情况，这种设计在现实中是比较常见的。比如操作系统的短时间优先任务调度，电梯按键操作指令。

      优先队列不再遵循先入先出的原则，而是分为两种情况：

      最大优先队列，无论入队顺序，当前最大的元素优先出队。

      最小优先队列，无论入队顺序，当前最小的元素优先出队。

      优先队列可以使用线性结构实现，但是效率不高，最坏情况下时间复杂度是O（n）。通常情况下优先队列使用二叉堆实现，二叉堆实现的时间复杂度为O（logn）,二叉堆不是一种线性结构,因为它其中的某个数据项可能存在两个后继，但由于二叉堆的数据管理由一定规律可循，我们也可以通过数组进行模拟。

      1) 二叉堆的性质

      根据层次,从左向右依次添加数据。由此推到出

      一个子节点的下标是n，它的父节点的下标为：（n+1）/  2 - 1

      一个父节点的下标是n，他的子节点的下标分别是：n*2+1和n*2+2

      二叉堆根据排序方式分为：最大堆和最小堆

      最大堆的堆顶是整个堆中的最大元素，最小堆的堆顶是整个堆中的最小元素。

      以最大堆为例

      入队操作

      在结尾处插入新节点5

      新节点5上浮到合适位置(父节点大于等于5)

      出队操作

      移除堆顶的节点10

      使用最后一个节点1替代堆顶

      节点1下沉至合适位置（每次选择子节点较大一方下沉），节点1与节点9交换。节点9成为新堆顶，节点1继续下沉交换，直至到达合适位置。

      2) 利用二叉堆实现优先队列

      二叉堆的性质很好的满足了优先权队列的特征，出队时选择堆顶数据即可，然后将结尾数据放在栈顶做下沉操作。

      入队时放在结尾，通过上浮操作将数据放在堆中合适的位置上。

      代码实现

      1. 课后作业

      1) 判断一个字符串类型的内容中“括号”是否匹配

      思路：当遇到左括号就入栈，如果遇到右括号就出栈。括号包括大括号”{}”，中括号”[]”和小括号”()”。

      括号不匹配的情况 ：

      a. 如果左右两个括号不匹配，比如“｛”遇到了“]”。

      b. 栈中已经空了，仍然遇到了右括号，证明没有左括号与该右括号匹配

      c. 全部数据已经校验完毕，栈中仍然有左括号，证明这些左括号没有右括号匹配

      括号匹配的情况

      比较过程中所有的括号都能正确匹配且全部数据校验完毕后栈中是空的。

      2) 短时间优先任务队列的实现

      以时间为优先度的任务队列，任务所需时间越短，其优先级越高。

      比如

      任务1    300ms

      任务2    25ms

      任务3    1250ms

      任务4    125ms

      这时，如果4个任务依次进入队列

      其输出顺序应为

      任务2

      任务4

      任务1

      任务3

      可以参考最大堆的实现。利用一个最小堆来实现短时间优先任务队列。