# 队列

# 队列数据结构

队列(queue)是一种遵从先进先出(FIFO)原则的受限线性表（受限表示对结点的操作受限制）。新添加的元素在队列尾部（只能添加不能删除），待删除的元素在队列的首部（只能删除不能添加）。队列中没有元素时，称为空队列。
队列的例子有很多，例如单向通道，打印机的打印队列等。

# 队列实现

队列实现代码细节：queue.ts (opens new window)

1.声明一个私有变量_items 用于存储元素，类型跟 stack 一样选用对象；再声明一个私有变量_count 用于记录队列的数量；最后声明一个私有变量_lowestIndex，用于记录下一个进来的元素即将使用的下标。

    2.队列的先进先出实现：
        新增尾部元素跟 stack 类似要用下标作为属性名，但这里用_lowestIndex 作为属性名（可以思考一下为什么不用_count），添加到对象中后更新_count 和_lowestIndex 的值。
        删除首部元素跟 stack 类似用 delete 运算符，但我们要在首部删除，所以拿到首部元素的下标也就是_lowestIndex 减去_count 所得的值，然后使用 delete 删除首部元素，最后更新_count 的值（_lowestIndex 不用更新，它不会受影响）。

3.队列的其他常用方法跟 stack 的其他常用方法实现类似。peek 查看队列首部元素、isEmpty 队列是否为空、size 队列的大小、clear 清空队列、toString 返回队列的字符串形式。

# 双端队列数据结构

双端队列(deque)是一种允许我们同时从首部和尾部添加和移除元素的特殊队列。
双端队列的例子有很多，例如餐厅或者电影院排队，软件中的撤销功能等。

# 双端队列实现

双端队列实现代码细节：deque.ts (opens new window)

1.声明一个私有变量_items 用于存储元素，类型跟 stack 一样选用对象；再声明一个私有变量_count 用于记录队列的数量；最后声明一个私有变量_lowestIndex，用于记录下一个进来的元素即将使用的下标。（跟 queue 一样）

    2.双端队列的双端删除和添加：         尾部添加新元素 addBack：跟队列一样的做法，在对象里插入属性名为_lowestIndex 的新元素，再更新_lowestIndex 和_count。
        首端添加元素 addFront：要分三种情况，1 队列为空那么直接往尾部添加新元素也就是调用 addBack；2 首部元素的下标为 0 那么要先将队列的元素集体右移再将新元素添加到下标为 0 的位置，更新_lowestIndex 和_count；3 首部元素的下标不为 0 那么将新元素添加到首部元素的前一位，更新_count。
        移除尾部元素 removeBack：先拿到尾部元素的下标也就是_lowestIndex 减去 1 所得的值，再用 delete 删除尾部元素，最后更新_count 和_lowestIndex。
        移除首部元素 removeFront：先拿到首部元素的下标也就是_lowestIndex 减去_count 所得的值，再用 delete 删除首部元素，最后更新_count（_lowestIndex 不用更新，它不会受影响）。

3.双端队列的其他常用方法跟 queue 的其他常用方法实现类似。peekFront 查看双端队列首部元素、peekBack 查看双端队列尾部元素、isEmpty 双端队列是否为空、size 双端队列的大小、clear 清空双端队列、toString 返回双端队列的字符串形式。

# 循环队列

循环队列实现代码细节：hot-potato.ts (opens new window)

击鼓传花思路：先构造一个队列（当然如果是双向的问题就用双端队列），将首部元素拿掉放到尾部重复 num 次，这 num 次算一轮，每轮结束将首部拿出存到临时数组里，继续循环每一轮直到剩余最后一项终止。最后一项就是胜利者，临时数组就是每轮的淘汰者。

# 回文检查器

回文检查器实现代码细节：palindrome-checker.ts (opens new window)

回文是正反都能读通的单词、词组、数或一系列字符的序列，例如 madam 或 racecar。

思路：字符串反转、栈存储一半字符等都可以解决，这里用双端队列来解决。先将目标字符串构造成一个双端队列，然后每次都从首部和尾部取出元素对比。

# JavaScript 任务队列

当我们在浏览器中打开新标签时，就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务，称为事件循环。浏览器要负责做个任务，如渲染 HTML、执行 JavaScript 代码、处理用户交互（用户输入、鼠标点击等）、执行和处理异步请求。 https://jakearchibald.com/2015/tasks-microtasks-queues-and-schedules/ (opens new window) 翻译文https://segmentfault.com/a/1190000014812771?utm_source=channel-hottest (opens new window)

← 2.栈 4.链表 →