概述：
6.1 栈
6.1.1概述
-
栈的容量一般都很小，生命周期也很短。
6.1.2使用数组实现栈这种数据结构
使用数组实现栈这种数据结构：包括push()、pop()、peek()方法
P88 stack.java
6.1.3使用链表实现栈这种数据结构
P156
6.1.4程序员会如何使用栈（什么情况下使用栈来完成特定的功能）
栈的应用场景：
-
-
分隔符匹配程序的功能是：对输入的字符串进行检查，如果字符串中分隔符没有完全匹配则报错，如下图
想到使用栈来实现这样的功能，下面是使用栈实现分隔符匹配功能的思路
-
6.2队列（按照时间先后顺序排序，先来先入队先被处理）
6.2.1概述
-
可以使用数组 或者 链表 来实现队列。
队列的三个基本操作：
-
循环队列：
删除队头元素后，若是让后面的元素依次前移，那么效率会非常低下，所以实现循环队列不使用移动队列中元素的方法，那么应该如何实现循环队列呢？
答：使用两个指针，队头指针和队尾指针，指针循环
6.2.2使用数组实现队列这种数据结构
实现方法有两种：使用nElements属性（该属性表示队列中现有元素数目） P103 queue.java
不使用nElements属性 P106 class Queue.java
两种方法各有优缺点，实际项目中可以根据需要选择不同的实现方法：
项目中如果添加、删除队列元素的操作较多，最好不使用nElements属性
项目中如果判断队列是否为空、是否满、访问队列中现有元素个数的操作相对较多，最好使用nElements属性
使用nElements属性实现队列时，每次添加、删除一个元素时，都要操作nElements属性，这对于项目中
6.2.3使用链表实现队列这种数据结构
P160
6.3优先级队列（按照关键字(如紧急程度)的值排队）
6.3.1概述
-
- 应用场景：如信件处理事件中，收取信件时将新得的信件按照紧急程度选择它应该被摆放的位置，紧急程度高的放在队列偏队首的位置，紧急程度越低则放在队列相对偏后的位置。
- （也就是说将即将入队的元素按照“紧急程度”这个“关键字”来决定该元素在队列中的插入位置）
- 优先级队列可以使用数组这种数据结构来实现，也可以使用堆这种数据结构来实现。使用数组实现的优先级队列 元素插入队列的速度较慢。
6.3.2 可以使用数组来实现优先级队列
数组实现优先级队列：
-
-
- 关键技术点：待入队元素比照着关键字 “按序插入”，而不是插入队列的尾部
- 优先级最高的元素放在数组的靠近尾部的位置（也就是队列的队首）
- 数组的尾部也就是优先级队列的队首元素（所以优先级队列并不需要实现循环机制）
- （或者也可以使用另外一种实现思路：插入时直接插到队尾，但是删除时要慢，因为每次删除都要在队列现有元素中查找到关键字最小（最大）的元素来删除，然后还要移动其他的元素来填补空出的洞）
- P111 priorityQ.java
-
6.3.3 可以使用堆来实现优先级队列
使用堆实现的优先级队列插入和删除的时间复杂度都是O(logN)
6.3.4 实现优先级队列的各种方法的比较
| 实现优先级队列的方法 | 对手元素删除时间复杂度 | 新元素的插入 |
| 使用数组实现优先级队列 | O(1) | O(N) |
| 使用堆实现优先级队列 | O(logN) | O(logN) |
应用场景：当有很多插入操作时，可以选用堆来实现优先级队列。
6.4解析算术表达式（栈的应用场景举例，可以不掌握）
6.4.1关于中缀表达式和后缀表达式
什么是中缀表达式，什么是后缀表达式？
-
-
人类计算中缀表达式的过程其实是分两步的，看到表达式之后，人脑的潜意识里其实就已经将中缀表达式转换成了后缀表达式，
-
那么如何使计算机拥有和人类一样的解析算术表达式的能力？
答：让计算机模仿人类大脑的运行过程，
step1:赋予计算机“中缀表达式转换成后缀表达式的算法”；
step2:赋予计算机“计算后缀表达式的值的算法”
-
6.4.2计算机算法解析算术表达式
编程思想：
让计算机模仿人类大脑的运行过程，
step1:赋予计算机“中缀表达式转换成后缀表达式的算法”；
step2:赋予计算机“计算后缀表达式的值的算法
Java代码：（计算机程序实现算术表达式的解析与计算功能）
P123 infix.java(计算机实现中缀表达式转换成后缀表达式的操作)
P129 postfix.java(计算机来计算后缀表达式)
小结：
-
-
本章遗留问题
P135 4.2 - 4.5 题