特点
先进先出
队头出队 < data < 队尾入队
一种操作受限的线性表数据结构
两种操作
入队enqueue: 放一个数据到队列尾部
出队dequeue: 从队列头部取一个元素
复杂度分析
空间复杂度为O(1)
时间复杂度为O(1)
队列分类
顺序队列: 用数组实现的有界队列
链式队列: 用链表实现的无界队列
循环队列
可以避免顺序队列入队时的数据搬移操作,提升入队性能
基于数组的循环队列,利用CAS原子操作,可以实现非常高效的并发队列
阻塞队列
队列基础上增加了阻塞操作
应用场景: 生产者-消费者模型
在队列为空的时候,队头读取数据会被阻塞,直到队列有了数据才能返回;
在队列已满的时候,数据插入操作会被阻塞,直到队列中有位置后插入数据然后返回
并发队列
线程安全的队列
采用入队enqueue和出队dequeue方法上加锁来实现,同一时刻仅允许一个存或者取操作
总结
对于大部分资源有限的场景,当没有空闲资源时,基本都可以通过队列数据结构来实现请求排队