队列-单端队列

队列和栈非常类似, 栈的一端是封闭的, 类似一口深井, 遵循先进后出原则 FILO.

队列则两端是放开的, 抽象于现实世界的排队现象, 遵循先进先出原则 FIFO.

队列在尾部进行元素的新增, 称为 "入队", 然后从头部移除元素, 成为 "出队". 生活中我们去坐火车进站检票, 去某个机关办理业务, 去用打印机印一叠文件等都是需要 "排队", 先来的先处理, 后来的往后站, 不允许插队哦.

创建队列

最简单方式可直接用 js 数组实现, 队尾用 arr.push(), arr.pop() , 队首用 arr.unshift(), arr.shift()

但从元素获取层面希望能更高效, 还是觉得用 js对象 来实现更合适一些呢.

class Queue {
  constructor() {
    this.count = 0  // 控制队列大小, 非长度
    this.fontIndex = 0  // 队首第一个元素索引
    this.obj = {}
  }
}

然后是要给队列声明一些常用方法

• enqueue () 向队尾添加元素
• dequeue () 向队首移除元素, 并返回
• peek () 返回队首元素
• isEmpty () 检查是否为空队列, 返回 true 或者 false
• size () 返回队列的元素个数, 即队列长度, 类似数组的 length

元素入队

即元素必须要从队尾进行添加, 因为用的底层是 JS对象, 即用 count 作为键, 添加后自增 1 即可.

class Queue {
  constructor() {
    this.count = 0 
    this.frontIndex = 0  
    this.obj = {}
  }
  // 元素入队
  enqueue(item) {
    this.obj[this.count] = item 
    this.count += 1
  }
}

队列长度

即队列中元素个数, 即用队列的长度 减去 队首元素的索引即可, 当这个值为0 , 则说明是空队列了.

class Queue {
  constructor() {
    this.count = 0 
    this.frontIndex = 0  
    this.obj = {}
  }
  // 队列长度
  size() {
    return this.count - this.frontIndex
  }
  // 队列是否为空
  isEmpty() {
    this.size() == 0
  }
}

还是来简单模拟一下,直观理解一波这个长度的计算.

假设左边是队尾, 右边是队首, 而且是有序的

先入队a: { 0:a },
再入队b: { 1:b,  0:a },
再入队c: { 2:c, 1:b,  0:a }

此时的     this.count = 3;  
队首索引是: this.frontIndex = 0

根据先进先出, 对 a 进行出队

此时到对首元素是0, 动态表示为 obj[this.frontIndex], 值是 a
然后进行删除后, 此时的队列是 { 2:c, 1:b }, 即当前队首元素索引 从 0 变到 1
动态表示即 this.frontIndex + 1 表示此时队首的元素

元素出队

只要弄清楚了如何计算队列长度, 非空下的 frontIndex 就是队首长度, 删掉它即可.

class Queue {
  constructor() {
    this.count = 0 
    this.frontIndex = 0  
    this.obj = {}
  }
  // 队列是否为空
  isEmpty() {
    this.count - this.frontIndex == 0
  }
  // 元素出队
  dequeue() {
    if (this.isEmpty()) return undefined 

    let frontItem = this.obj[this.frontIndex]
    delete this.obj[this.frontIndex]

    this.frontIndex += 1 // 更新队首元素索引
    return frontItem
  }
}

清空队列元素

粗暴方式是直接指向空, 或者一直进行 dequeue() 直到返回 undefined 为止.

  // 清空队列
  clear() {
    this.obj = {}
    this.frontIndex = 0
    this.count = 0
  }
}

查看队首元素和全队列

队首就是索引为 this.frontIndex 的值, 查看全部可以类似栈封装一个 toString 方法

class Queue {
  constructor() {
    this.count = 0 
    this.frontIndex = 0  
    this.obj = {}
  }
  // 查看队首元素
  peek() {
    if (this.isEmpty()) return undefined
    return this.obj[this.frontIndex]
  }
  // 查看全队列
  toString() {
    if (this.isEmpty()) return undefined

    let objString = `${this.obj[this.frontIndex]}`
    for (let i = this.frontIndex + 1; i < this.count; i++) {
      objString = `${objString}, ${this.obj[i]}`
    }
    return objString
  }
}

这样以来,我们的队列就基本建好了, 然后我们来整体测试一波

class Queue {
  constructor() {
    this.count = 0 
    this.frontIndex = 0  
    this.obj = {}
  }
  // 元素入队
  enqueue(item) {
    this.obj[this.count] = item 
    this.count += 1
  }
  // 队列长度
  size() {
    return this.count - this.frontIndex
  }
  // 队列是否为空
  isEmpty() {
    this.count - this.frontIndex == 0
  }
  // 元素出队
  dequeue() {
    if (this.isEmpty()) return undefined 

    let frontItem = this.obj[this.frontIndex]
    delete this.obj[this.frontIndex]

    this.frontIndex += 1 // 更新队首元素索引
    return frontItem
  }
  // 清空队列
  clear() {
    this.obj = {}
    this.frontIndex = 0
    this.count = 0
  }
  // 查看队首元素
  peek() {
    if (this.isEmpty()) return undefined
    return this.obj[this.frontIndex]
  }
  // 查看全队列
  toString() {
    if (this.isEmpty()) return undefined

    let objString = `${this.obj[this.frontIndex]}`
    for (let i = this.frontIndex + 1; i < this.count; i++) {
      objString = `${objString}, ${this.obj[i]}`
    }
    return objString
  }
}


// test 
const queue = new Queue()

queue.enqueue('youge')
queue.enqueue('yaya')
queue.enqueue('jack')

// 检验入队
console.log('此时的队列是: ', queue.toString());
console.log('队列长度是: ', queue.size());
console.log('队首元素是: ', queue.peek());

// 检验出队
console.log('出队的元素是: ', queue.dequeue());

console.log('此时的队列是: ', queue.toString());
console.log('队列长度是: ', queue.size());
console.log('队首元素是: ', queue.peek());

// 剩下元素出队
console.log('出队的元素是: ', queue.dequeue());
console.log('出队的元素是: ', queue.dequeue());

// 空了
console.log('此时的队列是: ', queue.toString());
console.log('队列长度是: ', queue.size());
console.log('队首元素是: ', queue.peek());

查看一下结果:

PS F:\algorithms> node queue.js

此时的队列是:  youge, yaya, jack
队列长度是:  3
队首元素是:  youge

出队的元素是:  youge
此时的队列是:  yaya, jack
队列长度是:  2
队首元素是:  yaya

出队的元素是:  yaya
出队的元素是:  jack

此时的队列是:  undefined
队列长度是:  0
队首元素是:  undefined

这样就实现了一个单端的队列, 后面接着会再来实现一个双端的队列哦.