队列的结构
队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项，与栈正好相反。典型的就是排队买票，先来的先买，后来的人只能站末尾，不允许插队。
队列两个基本操作：入队，放一个数据到队列尾部；出队，从队列头部取一个元素。所以队列也是一种操作受限的线性表数据结构。
JS实现队列
队列跟栈一样，也是一种抽象的数据结构。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
Queue类和Stack类主要的区别在于dequeue方法和peek方法，这是由于先进先出和后进先出原则的不同所造成的。
数组实现队列
数组的实现方式是最简单的，通过shift和unshift方法，就能用数组模拟基本的队列数据结构。
/** @Author: xjp* @Date: 2022-06-24 11:20:07* @LastEditTime: 2022-06-24 11:21:14* @Description:*/class Queue {constructor() {this.items = [] // 队列数组}// 入队enqueue(item) {this.items.unshift(item)return true}// 出队dequeue() {return this.items.splice(0, 1)}// 查看队列长度size() {return this.items.length}// 查看队列最后一个元素getTailItem() {const len = this.items.lengthif (len <= 0) {return null}return this.items[len - 1]}// 清空队列clearQueue() {this.items = []return true}}// 测试代码const q = new Queue()q.enqueue(1)q.enqueue(2)q.enqueue(3)console.log(q) // Queue { items: [ 3, 2, 1 ] }console.log(q.dequeue()) // -> 1 -> [3, 2]
对象实现队列
使用对象实现队列，获取元素更加高效！
/*
* @Author: xjp
* @Date: 2022-06-24 11:06:25
* @LastEditTime: 2022-06-24 11:15:31
* @Description:
*/
class Queue {
constructor() {
this.head = 0 // 队头的key
this.tail = 0 // 队尾的key
this.items = {}
}
// 入队，向队尾添加新项，队尾的key++
enqueue(item) {
this.items[this.tail] = item // 放在最后
this.tail++
}
// 出队，移除队头的元素，队头的key++
dequeue() {
if (this.isEmpty()) {
return undefined
}
const result = this.items[this.head]
delete this.items[this.head]
this.head++
return result
}
// 查看队列的第一个元素
peek() {
if (this.isEmpty()) {
return undefined
}
return this.items[this.head]
}
// 查看队列是否为空
isEmpty() {
return this.head === this.tail
}
// 查看队列包含多少个元素
size() {
return this.tail - this.head
}
// 清空队列
clear() {
this.items = {}
this.head = 0
this.tail = 0
}
// toString方法，方便打印
toString() {
if (this.isEmpty()) {
return ""
}
let objString = `${this.items[this.head]}`
for (let i = this.head + 1; i < this.tail; i++) {
objString = `${objString},${this.items[i]}`
}
return objString
}
}
// 测试代码
const q = new Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
console.log(q) // Queue { head: 0, tail: 3, items: { '0': 1, '1': 2, '2': 3 } }
console.log(q.toString()) // '1,2,3'
console.log(q.peek()) // 第一个元素：'1'
console.log(q.size()) // 队列个数：3
console.log(q.dequeue()) // 出队：'1'
console.log(q.size()) // 队列个数：2
console.log(q.peek()) // 第一个元素：'2'
链表实现队列
/**
* 链表结点的类
*/
class Node {
constructor(item) {
this.item = item // 添加的元素
this.next = null // 指针
}
}
class Queue {
constructor() {
this.length = 0 // 队列 size
this.head = null // 队头的结点
this.tail = null // 队尾的结点
}
// 入队（先将尾结点的next指向新添的节点，然后再用尾结点存储新添的结点）
push(item) {
const node = new Node(item)
if (this.length == 0) { // 如果没有结点
this.head = this.tail = node
} else { // 否则，尾结点存储新添的结点
this.tail.next = node; // ⭐顺序不能颠倒！！先将当前尾结点的next指向新结点
this.tail = node // 再将新节点赋给尾结点
}
// 更新队列大小
this.length++
return true
}
// 出队(头结点取出来，再将头结点指向头结点的下一个结点)
pop() {
if (this.length == 0) {
this.head = null // 队头结点
this.tail = null // 队尾结点
return this.head
}
const item = this.head.item
// 更新队列头部结点
this.head = this.head.next
// 更新队列大小
this.length--
// 返回队列头部结点的值
return item
}
// 获取长度（返回 length 即可）
size() {
return this.length
}
// 获取最后一个结点
getTail() {
if (this.length == 0) {
return null
}
return this.tail
}
clear() {
this.length = 0 // 队列 size
this.head = null // 队头
this.tail = null // 队尾
}
}
const q = new Queue()
q.push(1)
console.log(q)
// Queue {
// length: 1,
// head: Node { item: 1, next: null },
// tail: Node { item: 1, next: null }
// }
q.push(2)
q.push(3)
q.push(4)
console.log(q)
// Queue {
// length: 4,
// head: Node { item: 1, next: Node { item: 2, next: [Node] } },
// tail: Node { item: 4, next: null }
// }
console.log(q.pop()) // 1
console.log(q)
// Queue {
// length: 3,
// head: Node { item: 2, next: Node { item: 3, next: [Node] } },
// tail: Node { item: 4, next: null }
// }
双端队列
双端队列（deque，或称double-ended queue）是一种允许同时从前端和后端添加和移除元素的特殊队列。
双端队列在现实生活中的例子有电影院、餐厅中排队的队伍等。举个例子，一个刚买了票的人如果只是还需要再问一些简单的信息，就可以直接回到队伍的头部。另外，在队伍末尾的人如果赶时间，他可以直接离开队伍。
在计算机科学中，双端队列的一个常见应用是存储一系列的撤销操作。每当用户在软件中进行了一个操作，该操作会被存在一个双端队列中（就像在一个栈里）。当用户点击撤销按钮时，该操作会被从双端队列中弹出，表示它被从后面移除了。在进行了预先定义的一定数量的操作后，最先进行的操作会被从双端队列的前端移除。由于双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构
class Deque {
constructor() {
this.head = 0
this.tail = 0
this.items = {}
}
// 在双端队列前端添加新的元素，相当于插队：有三种场景
addFront(element) {
if (this.isEmpty()) { // 一、如果双端队列为空，则元素默认会被添加到双端队列的后端
this.addBack(element)
} else if (this.head > 0) { // 二、head > 0说明已经有元素从双端队列的前端被移除
this.head--
this.items[this.head] = element
} else { // 三、head === 0，设置一个负值的键，同时更新用于计算双端队列长度的逻辑，使其也能包含负键值。
for (let i = this.tail; i > 0; i--) { // 要在前端第一位添加一个新元素，就需要将所有元素后移一位来空出第一个位置
this.items[i] = this.items[i - 1]
}
this.tail++
this.items[0] = element // 将新元素添加到第一个位置
}
}
// 在双端队列后端添加新的元素
addBack(element) {
this.items[this.tail] = element
this.tail++
}
// 从双端队列前端移除第一个元素
removeFront() {
if (this.isEmpty()) {
return undefined
}
const result = this.items[this.head]
delete this.items[this.head]
this.head++
return result
}
// 从双端队列后端移除第一个元素
removeBack() {
if (this.isEmpty()) {
return undefined
}
this.tail--
const result = this.items[this.tail]
delete this.items[this.tail]
return result
}
// 返回双端队列前端的第一个元素
peekFront() {
if (this.isEmpty()) {
return undefined
}
return this.items[this.head]
}
// 返回双端队列后端的第一个元素
peekBack() {
if (this.isEmpty()) {
return undefined
}
return this.items[this.tail - 1]
}
isEmpty() {
return this.size() === 0
}
clear() {
this.items = {}
this.tail = 0
this.head = 0
}
size() {
return this.tail - this.head
}
toString() {
if (this.isEmpty()) {
return ''
}
let objString = `${this.items[this.head]}`
for (let i = this.head + 1; i < this.tail; i++) {
objString = `${objString},${this.items[i]}`
}
return objString
}
}
// 测试
const deque = new Deque()
console.log(deque.isEmpty()) // true
deque.addBack('A')
deque.addBack('B')
console.log(deque.toString()) // A,B
deque.addBack('C')
console.log(deque.toString()) // A,B,C
deque.addFront('D')
console.log(deque.toString()) // D,A,B,C
deque.removeBack()
console.log(deque.toString()) // D,A,B
deque.removeFront()
console.log(deque.toString()) // A,B
数组实现循环队列
数组实现队列时候，当数据过多超出数组长度时会发生数据搬移操作，这对入队操作性能有所影响。循环队列就可以避免数据搬移：
关键思路：循环队列满队**max**后不能继续添加，必须要pop出队才可以继续添加，出队时将队首head指向下一个，入队时将队尾tail指向下一个，保证循环的关键是每次出入队更新头尾用这个：**(this.tail/head + 1) % this.max**
class CircularQueue {
constructor(maxSize) { // k 为队列数组长度
this.items = Array(maxSize) // 存储队列
this.head = 0 // 队头索引
this.tail = 0 // 队尾索引
this.max = maxSize
}
// 入队
enqueue(value) {
if (this.isFull()) {
return false
} else {
this.items[this.tail] = value // 往队尾加入元素
this.tail = (this.tail + 1) % this.max // ⭐更新队尾索引
return true
}
}
// 出队
dequeue() {
const item = this.items[this.head]
this.items[this.head] = ''
this.head = (this.head + 1) % this.max // ⭐更新队头索引
return item
}
getHead() {
return this.items[this.head] ? this.items[this.head] : -1
}
getTail() {
if (this.isEmpty()) {
return -1
} else {
const tailIndex = this.tail - 1 // 获取 index
const cur = tailIndex < 0 ? this.max - 1 : tailIndex // 判断当前的 index
return this.items[cur]
}
}
// 队空
isEmpty() {
return this.head === this.tail && !this.items[this.head]
}
// 队满
isFull() {
return this.head === this.tail && !!this.items[this.head]
}
}
const circularQueue = new CircularQueue(3) // 最多存三个元素
circularQueue.enqueue(1)
console.log(circularQueue) // CircularQueue { items: [ 1, <2 empty items> ], head: 0, tail: 1, max: 3 }
circularQueue.enqueue(2)
circularQueue.enqueue(3)
console.log(circularQueue.isFull()) // true
console.log(circularQueue) // CircularQueue { items: [ 1, 2, 3 ], head: 0, tail: 0, max: 3 }
console.log(circularQueue.enqueue(4)) // false，满了，不能继续添加
console.log(circularQueue) // CircularQueue { items: [ 1, 2, 3 ], head: 0, tail: 0, max: 3 }
console.log(circularQueue.getHead()) // 队首：1
console.log(circularQueue.getTail()) // 队尾：3
console.log(circularQueue.dequeue()) // 出队：1
console.log(circularQueue) // CircularQueue { items: [ '', 2, 3 ], head: 1, tail: 0, max: 3 }
circularQueue.enqueue(4)
console.log(circularQueue) // CircularQueue { items: [ 4, 2, 3 ], head: 1, tail: 1, max: 3 }
console.log(circularQueue.getHead()) // ⭐队首：2
console.log(circularQueue.getTail()) // ⭐队尾：4
console.log(circularQueue.dequeue()) // 出队：2
circularQueue.enqueue(5)
console.log(circularQueue) // CircularQueue { items: [ 4, 5, 3 ], head: 2, tail: 2, max: 3 }
console.log(circularQueue.getHead()) // ⭐队首：3
console.log(circularQueue.getTail()) // ⭐队尾：5
队列的应用
循环队列—击鼓传花
在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈、结束游戏。重复这个过程，直到只剩一个孩子（胜者）。
function hotPotato(elementsList, num) { // num表示击鼓传花游戏的每一轮的第num次停止
const queue = new Queue()
const elimitatedList = [] // 存储被淘汰的
for (let i = 0; i < elementsList.length; i++) {
queue.enqueue(elementsList[i]) // 把已知的数据全都加入队列
}
while (queue.size() > 1) {
for (let i = 0; i < num; i++) { // 每轮击鼓传花7次，每次把队列的第一个元素放到队尾，循环往复
queue.enqueue(queue.dequeue())
}
elimitatedList.push(queue.dequeue()) // 一轮结束后，把队列的第一个元素放到淘汰列表
}
return {
eliminated: elimitatedList,
winner: queue.dequeue()
}
}
const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl']
const result = hotPotato(names, 7)
result.eliminated.forEach(name => {
console.log(`${name}在击鼓传花游戏中被淘汰。`)
})
console.log(`胜利者： ${result.winner}`)
双端队列— 回文检查器
有不同的算法可以检查一个词组或字符串是否为回文：
- 最简单的方式是将字符串反向排列并检查它和原字符串是否相同。如果两者相同，那么它就是一个回文。
- 栈来解决
- 双端队列
import Deque from "./deque.js" function palindromeChecker(aString) { if (aString === undefined || aString === null || (aString !== null && aString.length === 0)) { // 需要检查传入的字符串参数是否合法 return false } const deque = new Deque() const lowerString = aString.toLocaleLowerCase().split(" ").join("") // 将所有字母转化为小写，同时移除所有的空格 let isEqual = true let firstChar, lastChar for (let i = 0; i < lowerString.length; i++) { // 对字符串中的所有字符入队 deque.addBack(lowerString.charAt(i)) } while (deque.size() > 1 && isEqual) { // 将从前端移除一个元素，再从后端移除一个元素。如果是回文，移除的两个字符必须相同 firstChar = deque.removeFront() lastChar = deque.removeBack() if (firstChar !== lastChar) { isEqual = false } } return isEqual } console.log(palindromeChecker("Step on no pets")) // true阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作。简单说就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。不仅如此，基于阻塞队列，还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。
并发队列
在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，线程安全的队列叫作并发队列。最简单直接的实现方式是直接在 push()、pop() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。
基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。线程池请求排队
当向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理，这个时候就需要队列来实现先进先出。
基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
队列除了应用在线程池请求排队的场景，还可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
若有收获，就点个赞吧
0 人点赞
