相思资源网 Design By www.200059.com
队列
- 队列
- 双端队列数据结构
- 应用
- 用击鼓传花游戏模拟循环队列
- 用双端对列检查一个词是否构成回文
- 生成 1 到 n 的二进制数
队列和双端队列
队列遵循先进后出(FIFO, 也称为先来先服务) 原则的. 日常有很多这样场景: 排队购票、银行排队等.
由对列的特性,银行排队为例, 队列应该包含如下基本操作:
- 加入队列(取号) enqueue
- 从队列中移除(办理业务离开) dequeue
- 当前排队号码(呼叫下一个人) peek
- 当前队列长度(当前排队人数) size
- 判断队列是不是空 isEmpty
class Queue {
constructor() {
// 队列长度, 类数组 length
this.count = 0
// 队列中所有项
this.items = {}
// 记录对列头, 类数组 index
this.lowestCount = 0
}
enqueue(ele) {
this.items[this.count++] = ele
}
dequeue() {
if (this.isEnpty()) {
return undefined
}
const ele = this.items[this.lowestCount]
delete this.items[this.lowestCount]
this.lowestCount++
return ele
}
peek() {
if (this.isEnpty()) {
return
}
return this.items[this.lowestCount]
}
size() {
/**
* 当队列为非空时:
* 1. count 是长度
* 2. lowestCount 是下标
* 两者关系应该 lowestCount = count - 1
*/
return this.count - this.lowestCount
}
isEnpty() {
return this.size() == 0
}
clear() {
this.items = {}
this.lowestCount = 0
this.count = 0
}
toString() {
if (this.isEnpty()) {
return ''
}
let objString = `${this.items[this.lowestCount]}`
for (let i = this.lowestCount + 1; i < this.count; i++) {
objString = `${objString}, ${this.items[i]}`
}
return objString
}
}
双端队列(deque 或 double-ended queue)
什么是双端队列"htmlcode">
constructor() {
this.items = {}
this.count = 0
this.lowestCount = 0
}
addFront(ele) {
if (this.isEmpty()) {
this.items[this.count] = ele
} else if (this.lowestCount > 0) {
this.lowestCount -= 1
this.items[this.lowestCount] = ele
} else {
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1]
}
this.items[0] = ele
}
this.count++
return ele
}
removeFront() {
if (this.isEmpty()) {
return
}
const delEle = this.items[this.lowestCount]
delete this.items[this.lowestCount]
this.lowestCount++
return delEle
}
addBack(ele) {
this.items[this.count] = ele
this.count++
}
removeBack() {
if (this.isEmpty()) {
return
}
const delEle = this.items[this.count - 1]
delete this.items[this.count - 1]
this.count--
return delEle
}
peekFront() {
if (this.isEmpty()) {
return
}
return this.items[this.lowestCount]
}
peekBack() {
if (this.isEmpty()) {
return
}
return this.items[this.count - 1]
}
size() {
return this.count - this.lowestCount
}
isEmpty() {
return this.size() === 0
}
clear() {
this.items = {}
this.count = 0
this.lowestCount = 0
}
toString() {
if (this.isEmpty()) {
return ''
}
let objString = `${this.items[this.lowestCount]}`
for (let i = this.lowestCount + 1; i < this.count; i++){
objString = `${objString}, ${this.items[i]}`
}
return objString
}
}
队列的应用
击鼓传花游戏
击鼓传花游戏: 简单描述就是一群人围成一个圈传递花,喊停的时花在谁手上就将被淘汰(每个人都可能在前端,每个参与者在队列位置会不断变化)，最后只剩下一个时就是赢者. 更加详细可以自行查阅.
下面通过代码实现:
function hotPotato(elementsList, num) {
// 创建一个容器
const queue = new Queue()
const elimitatedList = []
// 把元素(参赛者)加入队列中
for (let i = 0, len = elementsList.length; i < len; i++) {
queue.enqueue(elementsList[i])
}
/**
* 击鼓传花
* 首先队列规则: 先进先出
* 那么在传花过程中,任何一个元素都可能是前端, 在传花的过程中应该就是前端位置不断变化.
* 当喊停的时(num 循环完), 也就是花落在谁手(谁在前端)则会被淘汰*（移除队列）
*/
while (queue.size() > 1) {
for (let j = 0; j < num; j++) {
queue.enqueue(queue.dequeue())
}
elimitatedList.push(queue.dequeue())
}
return {
winer: queue.dequeue(),
elimitatedList
}
}
代码运行如下:
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // { winer: 5, elimitatedList: [4, 8, 2, 7, 3,10, 9, 1, 6]}
console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // { winer: 5, elimitatedList: [4, 8, 2, 7, 3,10, 9, 1, 6]}
console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // { winer: 8, elimitatedList: [10, 1, 3, 6, 2,9, 5, 7, 4]}
判断回文
上一篇栈中也有涉及回文的实现, 下面我们通过双端队列来实现同样的功能.
function palindromeChecker(aString) {
if (!aString || typeof aString !== 'string' || !aString.trim().length) {
return false
}
const deque = new Deque()
const lowerString = aString.toLowerCase().split(' ').join('')
// 加入队列
for (let i = 0; i < lowerString.length; i++) {
deque.addBack(lowerString[i])
}
let isEqual = true
let firstChar = ''
let lastChar = ''
while (deque.size() > 1 && isEqual) {
firstChar = deque.removeFront()
lastChar = deque.removeBack()
if (firstChar != lastChar) {
isEqual = false
}
}
return isEqual
}
下面通过代码演示下:
console.log(palindromeChecker('abcba')) // true 当前为回文
生成 1 到 n 的二进制数
function generatePrintBinary(n) {
var q = new Queue()
q.enqueue('1')
while (n-- > 0) {
var s1 = q.peek()
q.dequeue()
console.log(s1)
var s2 = s1
q.enqueue(s1 + '0')
q.enqueue(s2 + '1')
}
}
generatePrintBinary(5) // => 1 10 11 100 101
标签：
JS,双端队列,JS,,队列
相思资源网 Design By www.200059.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
相思资源网 Design By www.200059.com
暂无JS中队列和双端队列实现及应用详解的评论...
一口气升级7个大模型SaaS应用，百度智能云：突出一个“开箱即用” - 2024/11/5
这一波大模型产业落地浪潮里，不少企业其实处在 “干瞪眼“的状态。
一种情况是，很多大模型产品看得见却摸不着，在台上一个个遥遥领先——今天Sora技精四座，明天英伟达的机器人又赢得满堂彩，可是到了台下一问：啥时候能用上啊？答曰：遥遥无期。
另一种情况是，企业想用上大模型，却又难免瞻前顾后——既要考虑场景融合，又得兼顾安全性，还要考虑打通现有系统，再加上各种部署成本和繁琐的采购流程……最后只能拂袖：罢了，再等等吧。
这一波大模型产业落地浪潮里，不少企业其实处在 “干瞪眼“的状态。
一种情况是，很多大模型产品看得见却摸不着，在台上一个个遥遥领先——今天Sora技精四座，明天英伟达的机器人又赢得满堂彩，可是到了台下一问：啥时候能用上啊？答曰：遥遥无期。
另一种情况是，企业想用上大模型，却又难免瞻前顾后——既要考虑场景融合，又得兼顾安全性，还要考虑打通现有系统，再加上各种部署成本和繁琐的采购流程……最后只能拂袖：罢了，再等等吧。
稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！
昨天有一位朋友在大神群里分享，自己亚服账号被封号之后居然弹出了国服的封号信息对话框。
这里面让他访问的是一个国服的战网网址，com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后，确实是网易的网址，也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情，因为以前都没有出现这样的情况，现在突然提示跳转到国服战网的网址，是不是说明了简体中文客户端已经开始进行更新了呢？