队列(笔记)

1. 概念

        队列：其实就是排队。像我们在银行窗口取钱、车站买车票等都可以叫队列。
        特点：队列只允许在后端(rear)进行插入操作，在前端(front)进行删除操作(即先进先出，FIFO, First-In-First-Out, 跟stack正好相反。简单来说就是谁先来先给谁办理业务，后来的人在队伍后面排队，不允许插队。

(上图来源：wiki)

2. 实现方式

1> 单链表
① 优点：链表有头指针和尾指针，这正好满足了队列的条件(只需要处理头(前端)和尾(后端)，一个删除，一个插入)
② 缺点：没有index这个概念，查询中间任意一个节点的数值，都需要遍历链表，时间复杂度是O(n)
③ 使用链表实现队列的条件：只顾头尾，甚至只顾头(例如：银行办理业务时谁先来先办理谁的，不会说先挨个问一下每个人办理什么业务，突然让某个人插个队或者说因为队伍最后一个人前面的人太多，就先给最后那个人办理)
2> 动态数组
① 优点：有index这个概念，查询数组中间任意一个下标的元素，时间复杂度是O(1)。(例如：现在办理业务时，有位老人已经等很久了，考虑到老人的身体状况，可能会叫一下那个老人手中的号，先给老人办理)
② 缺点：每删除一个array[0]的元素都是o(n)的时间复杂度(因为数组中有补位这个概念的存在)，不适合庞大的队伍。除此之外，如果扩容，还需要考虑复杂度震荡的问题。

3. 复杂度

                                        (图片来源：wiki)
① search(搜索某个元素)：无论链表还是数组都需要遍历，因此平均和最差时间复杂度都是O(n)
注：搜索：给定元素判断有无或者找下标；查询：给定下标找元素
② insert：都是从后端直接插入，因此平均和最差时间复杂度都是o(1)
③ delete：都是从前端直接删除(数组先不考虑后续的补位，只说删除这个操作)，因此平均和最差时间复杂度都是o(1)

其他

search：好像指的是搜索
query：指的查询
peek：常用于stack或者queue查看最顶端(或最前面)的元素

4. 实际应用

① 操作系统中的进程管理：可以控制进程执行的优先级(例如(大概过程，实际情况比这个复杂)：后台同时挂着游戏和工作软件，现在想打游戏，就把游戏放在首位，CPU、显卡等硬件都先给它用；过了一会发现工作快到上交的截止日期了，马上把工作再放到首位，CPU、显卡等硬件都先给工作用。由此可见打游戏、工作这些事情可以被看作一个队伍。在计算机中，这些任务都是随机的，需要把它们存储到一个队列当中来表示它们的优先级顺序)
② 搜索算法中的广度优先算法
③ 网络编程中的缓存网络数据包：可以控制队列数据的传输速度
④ 计算机图形学中三维场景的遮挡剔除：可以提高图形的渲染效率
        由此可见，队列在计算机系统中非常重要(着重强调系统级)，尤其是任务调度、进程管理方面，目的就是为了把它们排队，维护任务的执行顺序。

5. 内容出处

直面数据结构