华山资源网

JS中队列和双端队列实现及应用详解
网络编程 2024/12/23 佚名
3 1

队列

  • 队列
  • 双端队列数据结构
  • 应用
    • 用击鼓传花游戏模拟循环队列
    • 用双端对列检查一个词是否构成回文
    • 生成 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 当前为回文

JS中队列和双端队列实现及应用详解

生成 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
华山资源网 Design By www.eoogi.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
华山资源网 Design By www.eoogi.com
www.eoogi.com 华山资源网
120,135影音资源
344,641技术资源
22,817软件资源
435,032站长资源

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接
华山资源网 Design By www.eoogi.com