队列
- 一般情况,队列是一片连续的存储区,里面可以存储任意类型的数据
- 队列可以是数组,当然也可以是链表结构,如 leetcode 1670.设计前中后队列 就可以使用链表来实现前中后队列
- 队列有两个指针,通常情况下,一个指向头部元素,一个指向尾部元素的下一位
- 普通队列一般有两个操作,
- 出队:头指针,向后移动一位,完成头部元素的逻辑出队操作
- 入队:尾指针,在尾指针处插入新的元素,然后尾指针向后移动一位,完成入队操作
- 普通队列出队入队的顺序,一般是 FIFO,先入先出
- 普通队列可能出现假溢出的情况
- 经过几次入队出队操作后,尾指针可能已经移动到队尾,而头指针由于出队操作导致其不在队首
- 这样就出现了队列无法插入新元素,但实际的队列空间并没有满的情况
- 为了解决普通队列的假溢出,更高效的利用队列空间,就出现了 循环队列
- 无论是头指针还是尾指针,移动到队尾之后,判断一下队列元素个数是否等于队列长度,如队列还没有满,则将指针移动至队首
队列的实现
队列的典型应用场景
CPU 的超线程技术
- 一个 CPU 核心处理任务指令的速度非常快,往往任务指令输入的速度是跟不上 CPU 核心处理任务的速度的
- 为了能更高效的利用核心的计算资源,CPU 不必等待任务指令的输入过程,在 CPU 处理其他任务的同时,可以将输入的任务指令暂时缓冲在
任务队列
中,等 CPU 空闲时再从任务队列
中,取出任务进行计算 - 如下图所示,为了能高效的使用 CPU 资源,在硬件层面上,可以通过超线程技术,模拟出在外界看来是双倍虚拟核心的表象,其实就是单个核心从双倍的
任务队列
中读取任务进行计算,提高任务的执行效率
线程池的任务队列
- 进程是资源的总和,一个进程可以包含若干个线程
- 普通的多线程,会出现频繁的创建与销毁线程的情况,这个过程其实非常消耗性能
- 线程池可以很好的解决上述问题,但是线程池的线程数量是有限的,当有任务输入之后,会依次分配给空闲的线程进行计算,如果还有未被分配的任务,则会缓冲到
任务队列
中,当有线程空闲之后,再从任务队列
中取出来让该线程执行