队列认识队列
受限的线性结构：
队列(Queue)多任务下的数据结构与算法 数据结构和算法-线性结构-队列，它是一种受限的线性表多任务下的数据结构与算法，先进先出(FIFO First In First Out)
image-生活中的队列
生活中类似的队列结构
image-开发中队列的应用
打印队列：
线程队列：
当然队列还有很多其他应用，我们后续的很多算法中也会用到队列（比如二叉树的层序遍历）。
队列如何实现呢?
队列的实现队列类的创建
队列的实现和栈一样，有两种方案：
我们需要创建自己的类，来表示一个队列
<pre style="box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px;border-radius: 4px;margin-top: 10px;margin-right: auto;margin-left: auto;">class Queue { private data: T[] = []; } </pre>
代码解析：
队列的常见操作
队列有哪些常见的操作呢?
实现队列的接口
<pre style="box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px;border-radius: 4px;margin-top: 10px;margin-right: auto;margin-left: auto;"> interface IQueue { // 入队方法 enqueue(element: T): void // 出队方法 dequeue(): T | undefined // peek peek(): T | undefined // 判断是否为空 isEmpty(): boolean // 元素的个数 size(): number } export default IQueue </pre>
实现队列
现在，我们来实现这些方法。
<pre style="box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px;border-radius: 4px;margin-top: 10px;margin-right: auto;margin-left: auto;"> import IQueue from './IQueue' class ArrayQueue implements IQueue { private data: T[] = [] enqueue(element: T): void { this.data.push(element) } dequeue(): T | undefined { return this.data.shift() } peek(): T | undefined { return this.data[0] } isEmpty(): boolean { return this.data.length === 0 } size(): number { return this.data.length } } export default ArrayQueue </pre>
List接口封装和继承关系
我们发现我们定义的栈接口和队列接口，都有相同的操作方法 peek， 和 size。
可以将这些抽取成接口，让栈和队列的接口继承。
<pre style="box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px;border-radius: 4px;margin-top: 10px;margin-right: auto;margin-left: auto;"> export default interface IList { // peek peek(): T | undefined // 判断是否为空 isEmpty(): boolean // 元素的个数 size(): number } </pre>
<pre style="box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px;border-radius: 4px;margin-top: 10px;margin-right: auto;margin-left: auto;"> import IList from '../types/IList' // 定义栈的接口 interface IStack extends IList { push(element: T): void pop(): T | undefined } export default IStack </pre>
<pre style="box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px;border-radius: 4px;margin-top: 10px;margin-right: auto;margin-left: auto;"> import IList from '../types/IList' interface IQueue extends IList { // 入队方法 enqueue(element: T): void // 出队方法 dequeue(): T | undefined } export default IQueue </pre>
队列面试题击鼓传花
击鼓传花 是一个常见的面试算法题：使用队列可以非常方便的实现最终的结果。
原游戏规则：
修改游戏规则:
封装一个基于队列的函数：
击鼓传花的代码实现
img
<p><pre style="box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px;border-radius: 4px;margin-top: 10px;margin-right: auto;margin-left: auto;"> import ArrayQueue from './01_实现队列结构-数组' function hotPotato(names: string[], num: number): number { if (names.length === 0) return -1 // 1. 定义一个队列 const queue = new ArrayQueue() // 2. 将数据放入到队列中 for (let i = 0; i 1) { // 1/2 不淘汰 for (let i = 0; i