先进者先出，这就是典型的"队列"。
1. 特性
我们知道，栈只支持两个基本操作：入栈 push()，出栈 pop()，队列与栈类似基本操作只有两个: 入队 enqueue() 向对尾添加一个数据，出队 dequeue() 从队列头部取出一个数据。
1.1 应用
队列的应用非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
队列可以应用在任何有限资源池中，用于排队请求。对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
1.2 阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作。它有两个显著特征:
- 队列空时，从队头取数据会被阻塞，直到队列中有了数据才能返回
- 队列满时，向队尾插入数据会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回我们可以使用阻塞队列轻松实现一个“生产者，消费者模型”。
1.3 并发队列
线程安全的队列我们叫作并发队列，最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。
实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
1.4 双端对列
双端对列是一种类对列数据结构，支持在对列的头部和尾部都能进行插入和删除操作。Python 中的 collections.deque 就是一个双端对列的实现。
2. 实现
跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
2.1 顺序队列
顺序队列的实现需要两个指针，head 指针指向队列头部，tail 指针指向队列尾部，即下一个入队元素将被保存的位置索引。显然随着不断的入队，出队 tail 指针出超过数组的索引范围，此时即便数组还有空闲位置也无法继续添加数据。此时借鉴在数组删除中介绍的方法，如果没有空间，我们只需要在下一次入队时集中触发以此数据移动操作，队列中的数据集中移动数组最前方即可。另一种解决方案则是使用循环队列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
class ArrayQueue(object):
__CAPACITY__ = 10
def __init__(self):
self.head = self.tail = 0
self._capacity = self.__CAPACITY__
self._buf = [0] * self._capacity
def __len__(self):
return self.tail - self.head
def is_empty(self):
return len(self) == 0
def is_end(self):
return self.tail == self._capacity
def is_full(self):
return len(self) == self._capacity
def enqueue(self, value):
if self.is_full():
self._resize(self._capacity * 2)
elif self.is_end():
self._move()
self._buf[self.tail] = value
self.tail += 1
def dequeue(self):
if self.is_empty():
raise ValueError('queue is empty')
h = self._buf[self.head]
self._buf[self.head] = 0
self.head += 1
if len(self) < self._capacity / 4:
self._resize(self._capacity / 2)
return h
def _resize(self, size):
buf = [0] * size
base = len(self)
for i in range(base):
vi = self.head + i
buf[i] = self._buf[vi]
self._capacity = size
self._buf = buf
self.head = 0
self.tail = base
def _move(self):
i = 0
base = len(self)
while i < base:
self._buf[i] = self._buf[self.head + i]
i ++
self.head = 0
self.tail = base
|
2.2 链式队列
基于单链表的队列，我们在链表那一章已经包含在单链表的实现中。这里我们就基于双链表来实现一个队列，也把之前遗留的循环链表的实现补上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class LinkedCircularQueue(object):
class _Node(object):
__slots__ = "_element", "_next", "_pre"
def __init__(self, element, nxt=None):
self._element = element
self._next = nxt
def __init__(self):
self._tail = None
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def dequeue(self):
if self.is_empty():
raise ValueError('queue is empty')
self._size -= 1
node = self._tail._next
if self.is_empty():
self._tail = None
else:
self._tail._next = node._next
node._next = None
value = node.element
return value
def enqueue(self, value):
node = self._Node(value)
if self.is_empty():
node._next = node
else:
node._next = self._tail._next
self._tail._next = node
self._tail = node
self._size += 1
|
2.3 循环对列
循环对列与顺序队列类似，但是通过循环利用底层的数组有效的避免了数据移动。循环队列实现相比顺序队列更复杂，有以下几点需要注意:
- 追加到队尾的元素的位置不在是 tail 而是要判断 tail 是否大于 n，如果大于插入位置则为
tail % n，同时更新 tail 应该更新为 tail % n + 1
- 队空的条件仍然是
tail == head 但是队列满的条件则为 (tail + 1) % n == head
下面是另外一种类似的实现方式，记录头节点和队列中的元素个数，而不是尾节点，个人觉得这种实现方式更加直观。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
class ArrayCircularQueue(object):
__CAPACITY__ = 10
def __init__(self):
self._head = 0
self._size = 0
self._capacity = self.__CAPACITY__
self._buf = [0] * self._capacity
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def is_full(self):
return self._size == len(self._buf)
def enqueue(self, value):
if self.is_full():
self._resize(self._capacity * 2)
vi = (self._head + self._size) % self._capacity
self._buf[vi] = value
self._size += 1
def dequeue(self):
if self.is_empty():
raise ValueError('queue is empty')
value = self._buf[self._head]
self._buf[self._head] = 0
self._head = (self._head + 1) % self._capacity
if self._size < self._capacity / 4:
self._resize(self._capacity / 2)
self._size -= 1
return value
def _resize(self, size):
buf = [0] * size
for i in range(self._size):
vi = (i + self._head) % self._capacity
buf[i] = self._buf[vi]
self._capacity = size
self._buf = buf
self._head = 0
|
2.4 双端对列
链表那一章，我们实现了一个双向链表，在此基础上我们来实现一个双端队列。前面对双向链表的抽象实现是非常重要的，因为我们后面很多数据结构都是建立在双向链表的基础上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
from double_link import DoubleLink
class LinkedDeque(DoubleLink):
def __init__(self):
super(LinkedDeque, self).__init__()
def insert_first(self, value):
self.insert_between(value, self._head, self._head._next)
def insert_last(self, value):
self.insert_between(value, self._tail._pre, self._tail)
def delete_first(self):
if self.is_empty():
raise ValueError('Deque is empty')
self.delete_node(self._head._next)
def delete_last(self):
if self.is_empty():
raise ValueError('Deque is empty')
self.delete_node(self._tail._pre)
|
2.5 并发对列
一个基于 CAS 的无锁并发队列实现起来是很复杂的，我们暂时先把这个放一放，在这个系列的结尾会用专门的一篇文章来讲解实现。
参考:
