队列

  • 一般情况，队列是一片连续的存储区，里面可以存储任意类型的数据
  • 队列有两个指针，通常情况下，一个指向头部元素，一个指向尾部元素的下一位
  • 普通队列一般有两个操作，
    • 出队：头指针，向后移动一位，完成头部元素的逻辑出队操作
    • 入队：尾指针，在尾指针处插入新的元素，然后尾指针向后移动一位，完成入队操作
  • 普通队列出队入队的顺序，一般是 FIFO，先入先出
  • 普通队列可能出现假溢出的情况
    • 经过几次入队出队操作后，尾指针可能已经移动到队尾，而头指针由于出队操作导致其不在队首
    • 这样就出现了队列无法插入新元素，但实际的队列空间并没有满的情况
  • 为了解决普通队列的假溢出，更高效的利用队列空间，就出现了 循环队列
    • 无论是头指针还是尾指针，移动到队尾之后，判断一下队列元素个数是否等于队列长度，如队列还没有满，则将指针移动至队首

队列的实现

队列的典型应用场景

CPU 的超线程技术

  • 一个 CPU 核心处理任务指令的速度非常快，往往任务指令输入的速度是跟不上 CPU 核心处理任务的速度的
  • 为了能更高效的利用核心的计算资源，CPU 不必等待任务指令的输入过程，在 CPU 处理其他任务的同时，可以将输入的任务指令暂时缓冲在 任务队列 中，等 CPU 空闲时再从 任务队列 中，取出任务进行计算
  • 如下图所示，为了能高效的使用 CPU 资源，在硬件层面上，可以通过超线程技术，模拟出在外界看来是双倍虚拟核心的表象，其实就是单个核心从双倍的 任务队列 中读取任务进行计算，提高任务的执行效率

队列 (Queue) - 图1

线程池的任务队列

  • 进程是资源的总和，一个进程可以包含若干个线程
  • 普通的多线程，会出现频繁的创建与销毁线程的情况，这个过程其实非常消耗性能
  • 线程池可以很好的解决上述问题，但是线程池的线程数量是有限的，当有任务输入之后，会依次分配给空闲的线程进行计算，如果还有未被分配的任务，则会缓冲到 任务队列 中，当有线程空闲之后，再从 任务队列 中取出来让该线程执行

队列 (Queue) - 图2