什么是队列

  • 先进者先出

    与栈的区别

  • 栈只支持两个基本操作：入栈 push()和出栈 pop()

  • 队列最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素

    1.                            ![image.png](https://cdn.nlark.com/yuque/0/2021/png/12492651/1628752042344-e02638f8-9684-486b-a0c5-d608f5868c81.png#clientId=uee85d50d-ed94-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=216&id=u2e0f3110&margin=%5Bobject%20Object%5D&name=image.png&originHeight=514&originWidth=702&originalType=binary&ratio=1&rotation=0&showTitle=false&size=166948&status=done&style=none&taskId=ub568e704-e787-4442-aed3-ab7d0683dfb&title=&width=295)

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

    顺序队列和链式队列

  • 用数组实现的队列叫作顺序队列，

  • 用链表实现的队列叫作链式队列。

    顺序队列

  • 入队出队时间复杂度为O(1)

  • 不足：队列满的时候要数据搬移，时间复杂度就会从原来的 O(1) 变为 O(n) ```typescript // 数组实现顺序队列 class ArrayQueue { constructor(initLen) { this.head = 0 this.tail = 0 this.items = [] this.items.length = initLen }

    // 入队（队尾添加元素） enqueue(item) { /**考虑的事情

    • 1.队头 队尾 的位置，可以画图，节省脑容量
    • 2.队列满了如何处理 — 数据搬移 / if (this.tail === this.items.length) { // 表示元素已经加到队尾位置 // 考虑是否搬移数据 if (this.head === 0) { // 表示队满了 无法入队 return false } // 搬移数据 整体向前搬 到 对头位置 0 for (let i = this.head; i < this.tail; i++) { this.items[i - this.head] = this.items[i] } /*
      • 更新队头 队尾 指针
      • 先更新 队尾, 再更新 队头 */ this.tail = this.tail - this.head this.head = 0 } // 正常添加元素 this.items[this.tail] = item this.tail++ return true }

    /**

    • 出队(从对头取出元素)
    • 1.永远从队头 head 取元素
    • 1.考虑队空清空 */ dequeue() { if (this.tail === 0) { //表示队空 return null } const res = this.items[this.head] this.head++ return res } } const arrqueue = new ArrayQueue(10)

arrqueue.enqueue(‘1’) arrqueue.enqueue(‘2’) arrqueue.enqueue(‘3’) console.log(arrqueue.dequeue()); console.log(arrqueue.dequeue()); console.log(arrqueue.dequeue());

  1. <a name="PwMuc"></a>
  2. #### 循环队列
  4. - 避免数据搬移
  5. - **入队出队时间复杂度为O(1)**
  6. - **队满条件 (tail+1)%n=head**
  7. - **队空条件 tail=tail**
  8. - 当队列满时，tail 指向的位置实际上是没有存储数据的。所以，**循环队列会浪费一个数组的存储空间**
  9.    - 如果不浪费一个数组空间，可能需要引入其他变量，去记录队列的实际容量，也是需要额外的内存空间
  10. ```javascript
  11. class CircularQueue {
  12.   constructor(initLen) {
  13.     this.head = 0
  14.     this.tail = 0
  15.     this.items = []
  16.     this.items.length = initLen
  17.   }
  18.   /**
  19.    * 入队
  20.    * 考虑 队满条件
  21.    * 1.tail与head的关系 (tail + 1) % length === this.head
  22.    */
  23.   enqueue(item) {
  24.     if ((this.tail + 1) % this.items.length === this.head) {
  25.       return false
  26.     }
  27.     this.items[this.tail] = item
  28.     this.tail = (this.tail + 1) % this.items.length
  29.     return true
  30.   }
  31.   /**
  32.    * 出队
  33.    * 考虑 队空条件
  34.    * 1.tail与head的关系: tail===head
  35.    */
  36.    dequeue() {
  37.      if (this.tail === this.head) {
  38.        return null
  39.      }
  40.      const res = this.items[this.head]
  41.      this.head = (this.head + 1) % this.items.length
  42.      return res
  43.    }
  44. }
  46. const circularQueue = new CircularQueue(10)
  47. circularQueue.enqueue('1')
  48. circularQueue.enqueue('2')
  49. circularQueue.enqueue('3')
  50. console.log(circularQueue.dequeue());
  51. console.log(circularQueue.dequeue());
  52. console.log(circularQueue.dequeue());

阻塞队列

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

    并发队列

  • 多个线程同时操作队列

    思考

    线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？

  1. 我们希望公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求
  2. 队列有基于链表和基于数组这两种实现方式
    1. 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的
    2. 基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能