Tyrone 的博客

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

发表于 更新于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟
什么是队列？

引言

对于一台机器来说，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 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-------------