| 我的GitHub | 我的博客 | 我的微信 | 我的邮箱 |
|---|---|---|---|
| baiqiantao | baiqiantao | bqt20094 | baiqiantao@sina.com |
目录
目录08 | 栈：如何实现浏览器的前进和后退功能？
栈是一种操作受限的线性表，只允许在一端插入和删除数据。
从功能上来说，数组或链表也可以替代栈，但特定的数据结构是对特定场景的抽象，数组或链表暴露了太多的操作接口，操作上的确灵活*，但使用时就比较不可控，自然也就更容易出错。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选栈这种数据结构。
如何实现一个“栈”？
栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; //栈的大小
// 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了，直接返回false，入栈失败。
if (count == n) return false;
// 将item放到下标为count的位置，并且count加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空，则直接返回null
if (count == 0) return null;
// 返回下标为 count-1 的数组元素，并且栈中元素个数count减一
String tmp = items[count-1];
--count;
return tmp;
}
}
在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是
O(1)
入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度是O(1)
支持动态扩容的顺序栈
要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中。
均摊时间复杂度为
O(1)
栈的应用场景
栈在函数调用中的应用
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成栈这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
为什么函数调用要用栈来保存临时变量呢？用其他数据结构不行吗？
其实，我们不一定非要用栈来保存临时变量，只不过如果这个函数调用符合后进先出的特性，用栈这种数据结构来实现，是最顺理成章的选择。
从调用函数进入被调用函数，对于数据来说，变化的是什么呢？是作用域。所以根本上，只要能保证每进入一个新的函数，都是一个新的作用域就可以。而要实现这个，用栈就非常方便。在进入被调用函数的时候，分配一段栈空间给这个函数的变量，在函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。
栈在表达式求值中的应用
编译器是如何利用栈来实现表达式求值的？
比如：3+5*8-6。实际上，编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。
我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较：
- 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈
- 如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较
栈在括号匹配中的应用
可以借助栈来检查表达式中的括号是否匹配。
解答开篇
用两个栈就可以非常完美的实现浏览器的前进、后退功能
- 我们使用两个栈，X 和 Y，我们把
首次浏览的页面依次压入栈 X- 当点击
后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y - 当我们点击
前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中
- 当点击
- 当栈 X 中没有数据时，那就说明没有页面可以继续
后退浏览了 - 当栈 Y 中没有数据，那就说明没有页面可以点击
前进按钮浏览了
内容小结
栈是一种操作受限的数据结构，只支持入栈和出栈操作。后进先出是它最大的特点。栈既可以通过数组实现，也可以通过链表来实现。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。除此之外，我们还讲了一种支持动态扩容的顺序栈，你需要重点掌握它的均摊时间复杂度分析方法。
09 | 队列：队列在线程池等有限资源池中的应用
CPU 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境来设置的。
对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过
队列这种数据结构来实现请求排队。
如何理解“队列”？
队列跟栈一样，也是一种操作受限的线性表数据结构。
栈只支持两个基本操作：入栈 push() 和出栈 pop() 。
队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。
作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
顺序队列和链式队列
跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
用数组实现的队列
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;
}
// 入队操作，将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;
}
}
均摊复杂度的使用的前提条件是，最好时间复杂的和最坏时间复杂度出现的频率很有规律，且有一定的前后时序关系。但这里，他的出现频率完全取决于调用者如何去在代码中进行出栈入栈操作，因此无法对均摊和平均进行复杂度分析。
用链表实现的队列
基于链表的实现，我们同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。
如图所示，入队时，tail.next= new_node, tail = tail.next；出队时，head = head.next。
循环队列
我们刚才用数组来实现队列的时候，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。使用循环队列就能够避免数据搬移。
当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费数组的一个存储空间。
最关键的是，确定好队空和队满的判定条件
- 队列为空的判断条件是
head == tail - 队列满的判断条件是
(tail+1)%n=head
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;
}
}
阻塞队列和并发队列
队列这种数据结构很基础，平时的业务开发不大可能从零实现一个队列，甚至都不会直接用到。而一些具有特殊特性的队列应用却比较广泛，比如阻塞队列和并发队列。
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
你应该已经发现了，上述的定义就是一个生产者 - 消费者模型！是的！
线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
内容小结
队列最大的特点就是先进先出，主要的两个操作是入队和出队。跟栈一样，它既可以用数组来实现，也可以用链表来实现。用数组实现的叫顺序队列，用链表实现的叫链式队列。在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，我们就需要像环一样的循环队列。
阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全。
如何实现无锁并发队列？
考虑使用CAS实现无锁队列
- 在入队前，获取 tail 位置，入队时比较 tail 是否发生变化，如果否，则允许入队，反之，本次入队失败
- 出队则是获取 head 位置，进行 cas