数据结构与算法 - 线性表 - 队列
约 521 字大约 2 分钟
数据结构与算法队列
2023-09-08
《数据结构与算法-王争》学习笔记，记录备查
基本概念
队列，一种先进先出的线性数据结构。和栈一样，是一种操作受限的线性表数据结构。
用数组实现的队列叫做顺序队列，对链表实现的队列叫做链式队列。
循环队列，首位相连的一种顺序队列。
阻塞队列，在队列基础上加上了阻塞操作，当队列空时，出队阻塞，当队列满时，入队阻塞。
并发队列，线程安全的队列。两种实现：
- 简单的使用即为普通队列加了锁。
- 利用CAS原子操作，可以实现非常高效的并发队列。
操作
队列的主要操作有：入队（enqueue）和出队（dequeue）。在队头插入元素，在队尾删除元素。
操作顺序队列时，出队相当于操作队列尾的元素，为了我们能够保持队列可用，在删除元素之后，我们需要将数据往队尾移动。这样删除元素的时间复杂度为O(n)。插入元素的时间复杂度为O(1)。
在删除时，我们可以暂时不移动元素，待队列满，无法继续入队之后，再把所有的数据往队尾移动一次。这样出队的时间复杂度为O(1)。
操作链式队列时，存储结构不是连续的，不必移动元素，所以入队和出队的时间复杂度都是O(1)。
循环队列可以避免数据的迁移，但是会浪费一个存储元素的空间。循环队列需要注意判空和判满的条件：
- 判空：head == tail
- 判满：(tail+1)%n == head (n为队列长度)
应用
- 阻塞队列常用来解决一些因系统性能导致的问题。
- 循环并发队列常用来解决一些缓存的底层存储问题。