数据结构与算法学习总结--队列_数据结构实验四队列的实现及应用实验心得体会

定义

队列是一种操作受限的线性表数据结构，具有先进先出的特性，支持在一端（队尾）插入元素，在另一端（队头）删除元素

特点

先进先出

实现方式

用数组实现的队列叫顺序队列
用链表实现的队列叫链式队列

常见操作性能

入队enqueue 时间复杂度O(1) 空间复杂度O(1)
出队dequeue 时间复杂度O(1) 空间复杂度O(1）

应用场景

• 循环队列

循环队列可以解决数组实现的队列的数据搬移问题，使用更为广泛
循环队列实现的关键是正确判断队列空、队列满的条件

• 阻塞队列

在队列的基础上增加阻塞操作
在队列为空的时候，从队头取数据会被阻塞，直到队列中有数据
在队列满的时候，从队尾插入数据会被阻塞，直到队列有空闲位置，再插入数据，然后再返回
这实际上实现了一个生产者-消费者模型，并且还可以有效协调生产和消费的速度

• 并发队列

线程安全的队列称为并发队列
最直接的实现方式的在入队、出队时加锁
基于数组的循环队列，利用CAS原子操作，可以实现非常高效的并发队列
如何实现无锁并发队列：CAS+数组实现方式
入队前获取tail位置，入队时比较tail是否发生变化，如果没有变化，则允许入队，否则，本次入队失败。出队前获取head位置，出队时比较head是否发生变化，如果没有变化，则允许出队，否则，本次出队失败。

• 消息队列
• 线程池队列

新任务请求线程资源时，如果当时线程池没有空闲线程，如何处理？
非阻塞处理方式：直接拒绝任务请求
阻塞处理方式：将请求排队，等到有空闲线程时，取出排队的请求继续处理。如何存储请求（要保证公平地处理排队的请求，先进先服务）–队列。
基于链表的实现方式和基于数组的实现方式的区别：基于链表的实现方式，可以实现一个无限排序的无界队列，但是可能导致过多的队列请求排队，请求处理的响应时间过长。基于数组的实现方式，可以实现队列大小有限的有界队列，排队请求超过队列大小的时候，接下来的请求就会被拒绝，适用于对响应时间敏感的系统。但是合理的设置队列的大小，也是非常有讲究的。