《数据结构与算法-王争》学习笔记，记录备查

基本概念

队列，一种先进先出的线性数据结构。和栈一样，是一种操作受限的线性表数据结构。

用数组实现的队列叫做顺序队列，对链表实现的队列叫做链式队列。

循环队列，首位相连的一种顺序队列。

阻塞队列，在队列基础上加上了阻塞操作，当队列空时，出队阻塞，当队列满时，入队阻塞。

并发队列，线程安全的队列。两种实现：

• 简单的使用即为普通队列加了锁。
• 利用CAS原子操作，可以实现非常高效的并发队列。

操作

队列的主要操作有：入队（enqueue）和出队（dequeue）。在队头插入元素，在队尾删除元素。

操作顺序队列时，出队相当于操作队列尾的元素，为了我们能够保持队列可用，在删除元素之后，我们需要将数据往队尾移动。这样删除元素的时间复杂度为O(n)。插入元素的时间复杂度为O(1)。

在删除时，我们可以暂时不移动元素，待队列满，无法继续入队之后，再把所有的数据往队尾移动一次。这样出队的时间复杂度为O(1)。

操作链式队列时，存储结构不是连续的，不必移动元素，所以入队和出队的时间复杂度都是O(1)。

循环队列可以避免数据的迁移，但是会浪费一个存储元素的空间。循环队列需要注意判空和判满的条件：

• 判空：head == tail
• 判满：(tail+1)%n == head (n为队列长度)

应用

• 阻塞队列常用来解决一些因系统性能导致的问题。
• 循环并发队列常用来解决一些缓存的底层存储问题。