数据结构_栈与队列

快来打我* 2022-02-04 04:57 322阅读 0赞

## 一、栈 ##

**1.1、什么是栈？**  
1）.后进者先出，先进者后出，这就是典型的“栈”结构。  
2）.从栈的操作特性来看，是一种“操作受限”的线性表，只允许在端插入和删除数据。

**1.2、为什么需要栈？**  
1）.栈是一种操作受限的数据结构，其操作特性用数组和链表均可实现。  
2）.但，任何数据结构都是对特定应用场景的抽象，数组和链表虽然使用起来更加灵活，但却暴露了几乎所有的操作，难免会引发错误操作的风险。  
3）.所以，当某个数据集合只涉及在某端插入和删除数据，且满足后进者先出，先进者后出的操作特性时，我们应该首选栈这种数据结构。

**1.3 实现代码**  
[https://github.com/wangzheng0822/algo/tree/master/java/08\_stack][https_github.com_wangzheng0822_algo_tree_master_java_08_stack]

## 二、队列 ##

**2.1、队列 定义**  
队列是一种先进先出的数据结构，跟栈类似，队列是一种操作受限的线性表。  
队列同样可以由数组和链表来实现。  
队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

**2.2、队列分类**

**1）.顺序队列**  
顺序队列存在一个问题， tail 指针移动到数组最大下标时，即使数组中还有空闲空间，也无法继续往队列中添加数据了。  
解决方法是在入队列时，如果没有空闲空间，就触发一次搬运，将 head 到 tail 之间的数据，整体搬运到数组的 0 到 tail - head 位置。

**2）.链式队列**  
链式队列与顺序队列的区别是没有容量限制，在请求排队的场景下，如果排队的请求数量过多，请求处理的响应时间会过长。

**3）.循环队列**  
循环队列是为了解决顺序队列在 tail == n 时，需要数据搬运操作的问题。  
队列为空时可以根据 head == tail 来判断。循环队列满时，tail 指针位置不存储数据，所以队满判断公式为：  
(tail + 1) % n = head

**4）.阻塞和并发队列**  
阻塞队列在队列为空的时候，从队头取数据会被阻塞，直到队列中有数据才会返回；如果队列已经满了，插入数据操作会被阻塞，直到队列中有空闲的位置后再插入，然后再返回。

**2.3 实现代码**  
[https://github.com/wangzheng0822/algo/tree/master/java/09\_queue][https_github.com_wangzheng0822_algo_tree_master_java_09_queue]

[https_github.com_wangzheng0822_algo_tree_master_java_08_stack]: https://github.com/wangzheng0822/algo/tree/master/java/08_stack
[https_github.com_wangzheng0822_algo_tree_master_java_09_queue]: https://github.com/wangzheng0822/algo/tree/master/java/09_queue