09、队列

思考：队列在线程池等有限资源池中的应用，比如线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？

主要内容

队列定义：一种“操作受限”的线性表，支持队头出队，队尾入队，符合“先进先出、后进后出”的特性。

用数组实现“队列”

缺点：有长度限制

class Queue {
  constructor(len) {
    this.array = new Array(len)
    this.len = len
    this.head = 0 // 队头下标
    this.tail = 0 // 队尾下标
  }

  // 入队(队尾)
  push(value) {
    if(this.count === this.len) {
      // 队伍已满
      return false
    }

    this.array[this.tail] = value
    this.tail++

    return true

  }

  // 出队(队头)
   pop() {
    if(this.count === 0) {
      // 队伍已空
      return false
    }

    const value = this.array[this.head]
    this.head++

    return value
  }
}

用链表实现“队列”

优点：无限长度

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class Queue {
  constructor(head) {
    this.head = null // 队头指针
    this.tail = null // 队尾指针
  }

  // 入队(队尾)
  enqueue(value) {
    const newNode = new Node(value);

    this.tail.next = newNode
    this.tail = newNode

    return true

  }

  // 出队(队头)
  dequeue() {
    if(this.head === null) {
      // 队伍已空
      return false
    }

    const value = this.head.value
    this.head = this.head.next

    return value
  }
}

循环队列

正常队列是线性的，有头有尾。
循环队列指的是：当尾结束后，它下一个指向队头。

队空判断：head === tail
队满判断：(tail + 1) % len = head

队列应用

阻塞队列

当队伍空时，出队阻塞，直到队伍有数据。当队伍满时，入队阻塞，直到队伍又空闲。

并发队列

在多个操作对队伍进行操作时，可以给入队、出队加锁，让同一时刻只允许入或出队操作

解答思考

思考：队列在线程池等有限资源池中的应用，比如线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？
一种非阻塞，直接拒绝请求；
一种阻塞，现将请求排队，等到空闲线程产生，取出给排队的请求使用。
使用大小有限的队列，并考虑请求队伍的阻塞

新的思考

还有哪些设计或实现是采用队列的？

JS 中的任务队列