***** ## 栈与队列 ### 如何理解“栈”？ 关于“栈”，我有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。**后进者先出，先进者后出，这就是典型的“栈”结构。**  从栈的操作特性上来看，**栈是一种“操作受限”的线性表**，只允许在一端插入和删除数据 <br>大家有没有觉得，相比链表，栈带给我的只有限制，并没有任何优势。那我直接使用数组或者链表不就好了吗？为什么还要用这个“操作受限”的“栈”呢？ <br>事实上，从功能上来说，链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。 <br>**当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。** ### 如何实现一个“栈”？ 从刚才栈的定义里，我们可以看出，栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。理解了栈的定义之后，我们来看一看如何用代码实现一个栈。 <br>实际上，栈既可以用顺序表来实现，也可以用链表来实现。用顺序表实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。 ### 栈的操作 - Stack() 创建一个新的空栈 - push(item) 添加一个新的元素item到栈顶 - pop() 弹出栈顶元素 - peek() 返回栈顶元素 - is_empty() 判断栈是否为空 - size() 返回栈的元素个数 ## 案例 浏览器的前进、后退功能，我想你肯定很熟悉吧？ <br>当你依次访问完一串页面 a-b-c 之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a，点击前进按钮，就可以重新查看页面 b 和 c。但是，如果你后退到页面 b 后，点击了新的页面 d，那就无法再通过前进、后退功能查看页面 c 了。 <br>假设你是 Chrome 浏览器的开发工程师，你会如何实现这个功能呢？ ## 队列 队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。**先进者先出，这就是典型的“队列”。** <br>我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。  所以，队列跟栈一样，也是一种操作受限的线性表数据结构。 队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。 ### 队列的实现 - Queue() 创建一个空的队列 - enqueue(item) 往队列中添加一个item元素 - dequeue() 从队列头部删除一个元素 - is_empty() 判断一个队列是否为空 - size() 返回队列的大小 ## 双端队列 双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。 双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。  ### 操作 - Deque() 创建一个空的双端队列 - add_front(item) 从队头加入一个item元素 - add_rear(item) 从队尾加入一个item元素 - remove_front() 从队头删除一个item元素 - remove_rear() 从队尾删除一个item元素 - is_empty() 判断双端队列是否为空 - size() 返回队列的大小 ### 阻塞队列 阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。 ## 案例 我们知道，CPU 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。 <br>当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？