队列

队列是一种线性存储结构，但是只能从队列前端front添加或入队，从队列尾端rear移除或出队数据。队列具有先进先出FIFO的特点。

队列是一种抽象的数据结构，可以用数组或者链表来实现队列。例如，[1,2,3,4,5,6,7,8,9] 使用队列来存储的示意图。

队列的应用

当某共享资源使用（或者处理）数量大于限制数量的时侯，这些请求（或者任务）需要先等待，待资源可用时按照先到先得原则处理，这种情况，这些请求（或者任务）经常会使用队列来保存。

• CPU调度的任务队列
• Web服务器请求队列
• 键盘按键事件队列
• 多个系统（应用）之间的通信的消息队列

另外，在广度优先搜索算法中我们也经常会用到队列。

常见的队列有以下这些

• 双端队列，两端都可以入队和出队的队列。
• 循环队列，在使用数组实现队列时，多次入队出队之后，前端和后端都指向数组末尾，而数组实际上使用率很低，所以引入循环队列，在数组还有空间的时候，继续在数组开始入队元素。
• 优先队列，每个队列元素都有一个优先级，根据优先级来确定出队的顺序。优先队列内部一般是使用堆来实现。

面试题 17.14. 最小K个数

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

这道题最容易想到的就是先排序，然后返回最小的k个数。但是实际面试中，面试官可能还会问，如果数据特别大，大到无法直接对整个数组进行排序，该怎么办？

我们可以将数组中前k个数加入到优先队列中，然后遍历数组中剩下的元素，如果元素小于队列中最大的数，则将最大的数出队，然后将元素入队，如果大于则跳过，直到遍历完成。

用栈实现队列

用栈来实现队列先进先出队列。栈的特点先进后出，怎么才能实现先进先出？