后浪笔记一零二四

队列

如何实现一个队列？

队列是一种“操作受限”的线性表，只允许在一端插入(入队)，在另一端删除数据(出队)

队列既可以用数组来实现，也可以用链表来实现。用数组实现的队列，我们叫作 顺序队列，用链表实现的队列，我们叫作 链式队列。

 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

type ArrayQueue struct {
    q        []interface{}
    capacity int
    head     int
    tail     int
}

func NewArrayQueue(n int) *ArrayQueue {
    return &ArrayQueue{make([]interface{}, n), n, 0, 0}
}

func (this *ArrayQueue) EnQueue(v interface{}) bool {
    if this.tail == this.capacity {
        return false
    }
    this.q[this.tail] = v
    this.tail++
    return true
}

func (this *ArrayQueue) DeQueue() interface{} {
    if this.head == this.tail {
        return nil
    }
    v := this.q[this.head]
    this.head++
    return v
}

func (this *ArrayQueue) String() string {
    if this.head == this.tail {
        return "empty queue"
    }
    result := "head"
    for i := this.head; i <= this.tail-1; i++ {
        result += fmt.Sprintf("<-%+v", this.q[i])
    }
    result += "<-tail"
    return result
}

上面的算法中，随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。

这个问题该怎么解决呢？

  • 数据搬移：
    • 出队时可以不用搬移数据
    • 如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

    func (this *ArrayQueue) EnQueue(v interface{}) bool {
    // this.tail == this.capacity表示队列末尾没有空间了
    if this.tail == this.capacity {
        // this.tail == this.capacity && this.head == 0表示整个队列都占满了，无法执行数据搬移
        if this.head == 0 {
            return false
        }
        // 数据搬移
        for i := this.head; i < this.tail; i++ {
            this.q[i-this.head] = this.q[i];
        }
        // 搬完后重新更新head和tail
        this.tail -= this.head
        this.head = 0
    }
    this.q[this.tail] = v
    this.tail++
    return true
}
  • 循环队列
    • 基于数组实现的顺序队列，在队满的时候需要进行数据搬移，为了解决这个问题，就需要使用循环队列。
    • 要想写出没有 bug 的循环队列的实现代码，最关键的是，确定好队空和队满的判定条件。
      • 队空的判断条件仍然是 head == tail
      • 队满的判断条件是 (tail+1)%n=head
    • 当队列满时，图中的 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
58
59
60
61
62
63
64

    type CircularQueue struct {
    q        []interface{}
    capacity int
    head     int
    tail     int
}

func NewCircularQueue(n int) *CircularQueue {
    if n == 0 {
        return nil
    }
    return &CircularQueue{make([]interface{}, n), n, 0, 0}
}

// 栈空条件：head==tail为true
func (this *CircularQueue) IsEmpty() bool {
    if this.head == this.tail {
        return true
    }
    return false
}

// 栈满条件：(tail+1)%capacity==head为true
func (this *CircularQueue) IsFull() bool {
    if this.head == (this.tail+1)%this.capacity {
        return true
    }
    return false
}

func (this *CircularQueue) EnQueue(v interface{}) bool {
    if this.IsFull() {
        return false
    }
    this.q[this.tail] = v
    this.tail = (this.tail + 1) % this.capacity
    return true
}

func (this *CircularQueue) DeQueue() interface{} {
    if this.IsEmpty() {
        return nil
    }
    v := this.q[this.head]
    this.head = (this.head + 1) % this.capacity
    return v
}

func (this *CircularQueue) String() string {
    if this.IsEmpty() {
        return "empty queue"
    }
    result := "head"
    var i = this.head
    for true {
        result += fmt.Sprintf("<-%+v", this.q[i])
        i = (i + 1) % this.capacity
        if i == this.tail {
            break
        }
    }
    result += "<-tail"
    return result
}

阻塞队列和并发队列

  1. 阻塞队列

在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回； 如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

可以使用阻塞队列，轻松实现一个“生产者 - 消费者模型”！

  • 这种基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。
  • 可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。例如，可以多配置几个“消费者”，来应对一个“生产者”。
  1. 并发队列

在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，因为出队和入队操作都不是原子操作，存在间隙。

  • 基于数组的循环队列： 利用 CAS 原子操作，可以实现非常高效的并发队列
  • 基于链表的链式队列：一般直接在 enqueue()、dequeue() 方法上加锁，由于锁粒度大，所以并发度会比较低

线程池/协程池

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

  • 非阻塞的处理方式，直接拒绝任务请求

  • 阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理

  • 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。 =======

title: “队列” date: 2021-07-15 11:43:30 description: keywords:

  • 独立博客
  • 友链
  • 高质量外链 isCJKLanguage: true

nav: 数据结构与算法 categories:

  • 线性表 tags:
  • 线性表 weight: 5 image: ../../img/datastruct.jpg

如何实现一个队列？

队列是一种“操作受限”的线性表，只允许在一端插入(入队)，在另一端删除数据(出队)

队列既可以用数组来实现，也可以用链表来实现。用数组实现的队列，我们叫作 顺序队列，用链表实现的队列，我们叫作 链式队列。

 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

type ArrayQueue struct {
    q        []interface{}
    capacity int
    head     int
    tail     int
}

func NewArrayQueue(n int) *ArrayQueue {
    return &ArrayQueue{make([]interface{}, n), n, 0, 0}
}

func (this *ArrayQueue) EnQueue(v interface{}) bool {
    if this.tail == this.capacity {
        return false
    }
    this.q[this.tail] = v
    this.tail++
    return true
}

func (this *ArrayQueue) DeQueue() interface{} {
    if this.head == this.tail {
        return nil
    }
    v := this.q[this.head]
    this.head++
    return v
}

func (this *ArrayQueue) String() string {
    if this.head == this.tail {
        return "empty queue"
    }
    result := "head"
    for i := this.head; i <= this.tail-1; i++ {
        result += fmt.Sprintf("<-%+v", this.q[i])
    }
    result += "<-tail"
    return result
}

上面的算法中，随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。

这个问题该怎么解决呢？

  • 数据搬移：
    • 出队时可以不用搬移数据
    • 如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

    func (this *ArrayQueue) EnQueue(v interface{}) bool {
    // this.tail == this.capacity表示队列末尾没有空间了
    if this.tail == this.capacity {
        // this.tail == this.capacity && this.head == 0表示整个队列都占满了，无法执行数据搬移
        if this.head == 0 {
            return false
        }
        // 数据搬移，将数据整体平移到队头
        for i := this.head; i < this.tail; i++ {
            this.q[i-this.head] = this.q[i];
        }
        // 搬完后重新更新head和tail
        this.tail -= this.head
        this.head = 0
    }
    this.q[this.tail] = v
    this.tail++
    return true
}
  • 循环队列
    • 基于数组实现的顺序队列，在队满的时候需要进行数据搬移，为了解决这个问题，就需要使用循环队列。
    • 要想写出没有 bug 的循环队列的实现代码，最关键的是，确定好队空和队满的判定条件。
      • 队空的判断条件仍然是 head == tail
      • 队满的判断条件是 (tail+1)%n=head
    • 当队列满时，图中的 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
58
59
60
61
62
63
64

    type CircularQueue struct {
    q        []interface{}
    capacity int
    head     int
    tail     int
}

func NewCircularQueue(n int) *CircularQueue {
    if n == 0 {
        return nil
    }
    return &CircularQueue{make([]interface{}, n), n, 0, 0}
}

// 栈空条件：head==tail为true
func (this *CircularQueue) IsEmpty() bool {
    if this.head == this.tail {
        return true
    }
    return false
}

// 栈满条件：(tail+1)%capacity==head为true
func (this *CircularQueue) IsFull() bool {
    if this.head == (this.tail+1)%this.capacity {
        return true
    }
    return false
}

func (this *CircularQueue) EnQueue(v interface{}) bool {
    if this.IsFull() {
        return false
    }
    this.q[this.tail] = v
    this.tail = (this.tail + 1) % this.capacity
    return true
}

func (this *CircularQueue) DeQueue() interface{} {
    if this.IsEmpty() {
        return nil
    }
    v := this.q[this.head]
    this.head = (this.head + 1) % this.capacity
    return v
}

func (this *CircularQueue) String() string {
    if this.IsEmpty() {
        return "empty queue"
    }
    result := "head"
    var i = this.head
    for true {
        result += fmt.Sprintf("<-%+v", this.q[i])
        i = (i + 1) % this.capacity
        if i == this.tail {
            break
        }
    }
    result += "<-tail"
    return result
}

阻塞队列和并发队列

  1. 阻塞队列

在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回； 如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

可以使用阻塞队列，轻松实现一个“生产者 - 消费者模型”！

  • 这种基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。
  • 可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。例如，可以多配置几个“消费者”，来应对一个“生产者”。
  1. 并发队列

在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，因为出队和入队操作都不是原子操作，存在间隙。

  • 基于数组的循环队列： 利用 CAS 原子操作，可以实现非常高效的并发队列
  • 基于链表的链式队列：一般直接在 enqueue()、dequeue() 方法上加锁，由于锁粒度大，所以并发度会比较低

线程池/协程池

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

  • 非阻塞的处理方式，直接拒绝任务请求

  • 阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理

  • 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。

  • 基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。

专题: 线性表

本文发表于 2021-07-15，最后修改于 2021-07-15。

本站永久域名「 jiavvc.top 」，也可搜索「 后浪笔记一零二四 」找到我。

上一篇 « 栈 下一篇 » O(n^2)

赞赏支持

请我吃鸡腿 =^_^=

i ysf

云闪付

i wechat

微信

推荐阅读

栈

发表于2021-07-15， 阅读约4分钟

Untitled

发表于0001-01-01， 阅读约1分钟

Untitled

发表于0001-01-01， 阅读约11分钟

Big Image