Chendi Wu

Appearance

定义 ​

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作， 和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

特点 ​

先进先出（First In First Out）

链队列 ​

javascript
/**
    队列的特点：先进先出 First In First Out

    链式队列不存在假溢出问题。

    空的链队条件：头指针front和尾指针rear均指向头节点，即front == rear

    入队操作：将新rear.next指向新元素节点，然后将rear.next设置为rear

    出队操作：修改队头front指向，front.next = front.next.next

 */

class Node {
  constructor(element) {
    this.element = element
    this.next = null
  }
}

class LinkQueue {
  constructor() {
    this.head = new Node(null)
    this.front = this.head
    this.rear = this.head
    this.length = 0
  }

  isEmpty() {
    return this.front.next === null
  }

  enqueue(element) {
    let node = new Node(element)
    this.rear.next = node // 在这里front与rear都是指向head,对rear操作其属性是对引用数据类型操作，他们都会改变
    this.rear = node // 在这里rear整个被重新赋值为node，引用数据类型指向node，此时之后对rear其属性操作不会改变front
    this.length++
  }

  dequeue() {
    if (this.isEmpty()) {
      return null
    }
    let element = this.front.next.element
    this.front.next = this.front.next.next
    this.length--
    if (this.front.next == null) {
      this.rear = this.front
    }
    return element
  }

  getFront() {
    if (this.isEmpty()) {
      return null
    }
    return this.front.next.element
  }

  toString() {
    let str = ''
    let node = this.front.next
    while (node !== null) {
      str += node.element + ','
      node = node.next
    }
    str = '[' + str.slice(0, -1) + ']'
    return str
  }

  size() {
    return this.length
  }

  /**
   * 使头指针和尾指针均指向头节点
   */
  clear() {
    this.front = this.head
    this.rear = this.head
    this.length = 0
  }
}

linkQueue = new LinkQueue()

console.log('getFront', linkQueue.getFront())
console.log('toString', linkQueue.toString())
console.log('size', linkQueue.size())

console.log('------------------------')
linkQueue.enqueue('A')
linkQueue.enqueue('B')
linkQueue.enqueue('C')
linkQueue.enqueue('D')
linkQueue.enqueue('E')

console.log('getFront', linkQueue.getFront())
console.log('toString', linkQueue.toString())
console.log('size', linkQueue.size())
console.log('------------------------')

console.log(linkQueue.dequeue(), '出队列')
console.log(linkQueue.dequeue(), '出队列')
console.log(linkQueue.dequeue(), '出队列')
console.log(linkQueue.dequeue(), '出队列')

console.log('getFront', linkQueue.getFront())
console.log('toString', linkQueue.toString())
console.log('size', linkQueue.size())

console.log('------------------------')
linkQueue.clear()
console.log('getFront', linkQueue.getFront())
console.log('toString', linkQueue.toString())
console.log('size', linkQueue.size())

console.log('------------------------')
linkQueue.enqueue('F')
linkQueue.enqueue('G')
console.log('getFront', linkQueue.getFront())
console.log('toString', linkQueue.toString())
console.log('size', linkQueue.size())

顺序队列 ​

javascript
/**
 *  队列特点：允许插入的一端是队尾，允许删除的一端是队列头，即先进先出,FIFO（First In First Out）
    顺序队列：用一组地址连续的存储单元依次存放从队列头到队列尾的元素的队列

    队列的基本操作：
    入队：将新元素追加到队列尾
    出队：删除队列头元素，并且返回元素值
    获取头元素：仅仅返回头元素的值
    求队列长度:求出队列中数据元素的个数
    判断空:判断当前队列是否为空
    输出队列：返回队列中所有的元素
    销毁:清空队列

    若果数组长度限制，那么顺序队列会存在假溢满问题，这样子可能需要进行数据迁移，这样是非常消耗性能的，
    由于js数组没有最大长度限制（除非内存溢出），所以js版本的顺序队列没有溢出问题

 */

class ArrayQueue {
  constructor() {
    this.datas = []
  }

  enqueue(item) {
    this.datas.push(item)
  }

  dequeue() {
    return this.datas.shift()
  }

  front() {
    if (this.isEmpty()) {
      return null
    }
    return this.datas[0]
  }

  isEmpty() {
    return this.datas.length === 0
  }

  size() {
    return this.datas.length
  }

  toString() {
    return '[' + this.datas.toString() + ']'
  }
}

const queue = new ArrayQueue()

console.log('isEmpty', queue.isEmpty())
console.log('size', queue.size())
console.log('front', queue.front())
console.log('toString', queue.toString())
console.log('----------------------------------')

queue.enqueue('A')
queue.enqueue('B')
queue.enqueue('C')
queue.enqueue('D')
queue.enqueue('E')

console.log('isEmpty', queue.isEmpty())
console.log('size', queue.size())
console.log('front', queue.front())
console.log('toString', queue.toString())
console.log('----------------------------------')

let item = null
item = queue.dequeue()
for (let i = 0; i < 3; i++) {
  console.log(item, '出队列')
  item = queue.dequeue()
}
console.log('isEmpty', queue.isEmpty())
console.log('size', queue.size())
console.log('front', queue.front())
console.log('toString', queue.toString())

循环队列 ​

javascript
/**
 使用限制数组长度实现的循环队列，循环队列的优点是不存在队列假溢满问题，不需要进行数据迁移

 length:存储循环队列的长度
 datas:存储循环队列数据的数组
 front:指向队列的队头元素，初始值0
 rear:指向队列的队尾元素，初始值0


 入队操作：入队的时候将队尾指针rear+1，再将元素按rear指示位置加入，但当rear指向最后一个位置的时候，
 如果可以再加入元素（0位置元素已经出队列），则rear应该指向0，故队尾指示器加1的操作应该改为  this.rear = ( this.rear +1 ) % this.length

 出队操作：先将队头指针front+1,再将front所指示的元素取出，但当front指向队列最后一个位置并且仍然可以有元素可以出队，
 则front应该指向0，故队头指示器加1操作应该改为  this.front = (this.front + 1) % this.length

 求队列元素长度操作： return ( this.rear - this.front + this.length ) % this.length

 取出队列头元素：如果队列不为空，返回 this.datas[ (this.front + 1 ) % this.length ]

 判满操作：在做判断队列是否满约定少使用一个队列存储空间，而不是设立一个flag计算队列数据个数判断，如果数据非常大这样可以减少系统开销
 那么队列为满的条件是：(this.rear+1) % this.length === this.front

 判空操作，front == rear
 */

class SequenceQueue {
  constructor(length) {
    this.length = length + 1 // 约定少用一个数组存储空间来判断队列是否满，为了满足用户需要length个数据，将length+1处理
    this.datas = []
    this.front = 0
    this.rear = 0
  }

  isEmpty() {
    return this.rear === this.front
  }

  isFull() {
    return (this.rear + 1) % this.length === this.front
  }

  /**
   * 入队的时候将队尾指针rear+1，再将元素按rear指示位置加入
   * @param item
   * @returns {boolean}
   */
  enqueue(item) {
    if (this.isFull()) {
      return false
    }
    this.rear = (this.rear + 1) % this.length
    this.datas[this.rear] = item
  }

  /**
   * 先将队头指针front+1,再将front所指示的元素取出
   * @returns {*}
   */
  dequeue() {
    if (this.isEmpty()) {
      return null
    }
    this.front = (this.front + 1) % this.length
    let result = this.datas[this.front]
    delete this.datas[this.front]
    return result
  }

  /**
   * 取出队列头元素
   * @returns {*}
   */
  getFront() {
    if (this.isEmpty()) {
      return null
    }
    return this.datas[(this.front + 1) % this.length]
  }

  /**
   * 队列中数据元素个数
   * @returns {number}
   */
  size() {
    return (this.rear - this.front + this.length) % this.length
  }

  /**
   *
   * @returns {string}
   * 注意这里toString不能简单地见this.datas元素直接遍历输出，要根据队列实际有效数据输出
   */
  toString() {
    let i,
      j = this.front
    let str = ''
    for (i = 0; i < this.size(); i++) {
      j = (j + 1) % this.length
      str += this.datas[j] + ','
    }
    str = str.slice(0, -1)
    return str
  }

  clear() {
    this.front = this.rear = 0
    this.datas = []
  }
}

const sequenceQueue = new SequenceQueue(5)

console.log('isEmpty', sequenceQueue.isEmpty())
console.log('isFull', sequenceQueue.isFull())

let front = sequenceQueue.getFront()
console.log('front', front)

let size = sequenceQueue.size()
console.log('size', size)

let toStr = sequenceQueue.toString()
console.log('toStr', toStr)
console.log('---------1------------')

sequenceQueue.enqueue('A')
sequenceQueue.enqueue('B')
sequenceQueue.enqueue('C')
sequenceQueue.enqueue('D')
sequenceQueue.enqueue('E')
sequenceQueue.enqueue('F')

console.log('isEmpty', sequenceQueue.isEmpty())
console.log('isFull', sequenceQueue.isFull())

size = sequenceQueue.size()
console.log('size', size)

front = sequenceQueue.getFront()
console.log('front', front)

toStr = sequenceQueue.toString()
console.log('toStr', toStr)
console.log('--------2-------------')

let item = sequenceQueue.dequeue()
console.log(item, '出队列')
item = sequenceQueue.dequeue()
console.log(item, '出队列')
item = sequenceQueue.dequeue()
console.log(item, '出队列')

front = sequenceQueue.getFront()
console.log(item, '出队列之后front', front)

toStr = sequenceQueue.toString()
console.log('toStr', toStr)
console.log('---------3------------')

console.log('队列数组真实元素', sequenceQueue.datas)

console.log('---------4------------')
sequenceQueue.clear()
toStr = sequenceQueue.toString()
console.log('after clear toStr', toStr)
console.log('----------5-----------')
console.log('after clear  队列数组真实元素', sequenceQueue.datas)