什么是队列&&队列的使用场景

引言

对于一台机器来说,任务的处理速度与线程个数并不是线性正相关。相反,过多的线程反而会导致 CPU 频繁切换,处理性能的下降。所以,线程池的大小一般都是综合考虑要处理任务的特点和硬件环境,来事先设置。

当我们向一个固定大小的线程池中请求一个线程时,如果线程池中没有空闲资源了,这个时候线程池会如何处理这个请求?是拒绝请求还是排队请求?各种处理策略又是怎么事先的呢?

什么是队列?

队列这个概念非常好理解。当你在食堂排队买饭时,先来的先买,后来的排队等待。先进先出,这就是队列

与栈一样,队列最基本的操作也是两个:入队 enqueue()出队 dequeue

队列和栈一样,也是一种操作受限的线性表数据结构

队列作为一种非常基础的数据结构,队列的应用也非常广泛:

  • 循环队列
  • 阻塞队列
  • 并发队列

顺序队列和链式队列

数组实现顺序队列

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

class Queue(object):
def __init__(self, n):
self.queue = []
self.capacity = n

def enqueue(self, item):
if self.size() > self.capacity:
raise Exception("queue is full")
self.queue.append(item)

def dequeue(self):
if self.size() < 0:
return
self.queue.pop(0)

def size(self):
return len(self.queue)

def first(self):
return self.queue[0]

def end(self):
return self.queue[-1]


if __name__ == '__main__':
queue = Queue(10)
for i in range(11):
queue.enqueue(i)

print(queue.first(), queue.end())
queue.enqueue(11)


链表实现队列

direct

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Pointer(object):
def __init__(self):
self.head = None
self.tail = None


class ListNode(object):
def __init__(self, data):
self.data = data
self.next = None


class Queue(object):
def __init__(self):
self.pointer = Pointer()

def enqueue(self, data):
node = ListNode(data)
_p = self.pointer
if _p.head:
# 队列中有元素
tmp = _p.tail
_p.tail = node
tmp.next = node
else:
# 队列中没有元素, 插入第一个元素
_p.head, _p.tail = node, node

def dequeue(self):
_p = self.pointer
if _p.head and (_p.head == _p.tail):
# 队列中有一个元素
tmp = _p.head
_p.head = _p.tail = None
return tmp.data
elif _p.head and (_p.head != _p.tail):
# 队列中不止一个元素
tmp = _p.head
_p.head = tmp.next
return tmp.data
else:
# 队列中没有元素
raise Exception("queue is empty")

def is_empty(self):
return self.pointer.head == None

def top(self):
if self.pointer.head:
return self.pointer.head.data

else:
raise LookupError("queue is empty")

def travel(self):
_p = self.pointer
tmp = _p.head
while tmp != None:
print("-->{}".format(tmp.data), sep="")
tmp = tmp.next



if __name__ == '__main__':
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)

q.travel()
print("---------")
q.dequeue()
q.dequeue()
q.dequeue()

q.travel()

print(q.top())

循环队列

direct

循环队列,顾名思义,它像一个环,在实现过程中,最关键的是确定好队空和队满的判定条件

direct

总结如下:

  • 队列为空的判断条件:

head == tail

  • 队列为满的情况
    (tail + 1) % cap == head

  • 队列长度的计算公式:
    (tail - head + cap)%cap == length

  • 尾指针计算
    tail = (tail + 1) % cap

  • 头指针计算
    head = (head + 1) % cap

  • 队列为满时,图中的 tail 指向的位置实际上没有存储数据。

python 实现

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
class MyCircularQueue:

def __init__(self, k: int):
self._queue = [None] * (k+1)
self.cap = k+1
self.front = 0
self.rear = 0


def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self._queue[self.rear] = value
self.rear = (self.rear + 1) % self.cap
return True

def deQueue(self) -> bool:
if self.isEmpty():
return False
data = self._queue[self.front]
self._queue[self.front] = None
self.front = (self.front + 1) % self.cap
return True

def Front(self) -> int:
if self.isEmpty():
return -1
data = self._queue[self.front]
return data

def Rear(self) -> int:
if self.isEmpty():
return -1
data = self._queue[self.rear - 1]
return data

def isEmpty(self) -> bool:
return self.front == self.rear

def isFull(self) -> bool:
return self.front == (self.rear + 1) % self.cap


阻塞队列

阻塞队列实则就是在队列的基础上增加了阻塞操作。

  • 队列为空的时候,从队头取数据就会被阻塞
  • 队列满的时候,插入数据就会被阻塞

img_2.png

python 阻塞队列实现的生产者-消费者模型

在 python 中,queue 模块中实现了一个线程安全的队列,并发队列

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
import time
import queue
import threading

q = queue.Queue(5) # 生成一个队列,用来保存“包子”,最大数量为10

def productor(i):
# 厨师不停地每2秒做一个包子
while True:
q.put("厨师 %s 做的包子!" % i)
time.sleep(2)


def consumer(j):
# 顾客不停地每秒吃一个包子
while True:
print("顾客 %s 吃了一个 %s" % (j, q.get()))
time.sleep(1)


if __name__ == '__main__':

# 实例化了3个生产者(厨师)
for i in range(2):
t = threading.Thread(target=productor, args=(i,))
t.start()
# 实例化了10个消费者(顾客)
for j in range(3):
v = threading.Thread(target=consumer, args=(j,))
v.start()

总结

线程池没有空闲线程时,新任务请求线程资源时,线程池该如何处理?

一般有两种处理策略:

  • 非阻塞的处理方式
    直接拒绝任务请求
  • 阻塞方式
    将请求排队,等到有空闲线程时,取出排队的请求继续处理

实际上,对于大部分资源有限的场景,当没有空闲资源时,基本上都可以通过队列这种资源来实现请求排队。

队列总结

队列的最大特点就是:先进先出,主要的两个操作是入队和出队

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

CAS 实现无锁队列

参考:https://coolshell.cn/articles/8239.html

-------------THANKS FOR READING-------------