队列

1. 队列是什么

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

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表

2. 用数组表示

JavaScript中没有队列，但可以用Array实现队列的所有功能

常用操作：

入队：push

出队：shift

队头元素：queue[0]

3. 队列的封装

使用对象，为了提高删除时的效率

obj = {0:1,1:2,2:3}
delete obj[0]
console.log(obj) //{1:2,2:3}

class Queue {
    #items = {}
    #count = 0
    #lowCount = 0 //记录队头索引

    dequeue() {
        if(this.isEmpty()){
            return undefined
        }
        let res = this.#items[this.#lowCount]
        delete this.#items[this.#lowCount]
        this.#lowCount++
        return res
    }

    enqueue(data) {
        this.#items[this.#count] = data
        this.#count++
    }

    front() {
        return this.#items[this.#lowCount]
    }

    isEmpty() {
        return this.size() === 0
    }

    size() {
        return this.#count-this.#lowCount
    }

    clear() {
        this.#items = {}
        this.#count = 0
        this.#lowCount = 0
    }

    toString() {
        let str = ""
        for(let i =this.#lowCount;i<this.#count;i++){
            str += `${this.#items[i]} `
            }
        return str
    }
}

4. 应用-击鼓传花

function game(list,num){
    let queue = new Queue()
    for(let i=0;i<list.length;i++){
        queue.enqueue(list[i])
    }

    while(queue.size()>1){
        for(let i=0;i<num;i++){
            queue.enqueue(queue.dequeue())
        }
        console.log(queue.dequeue(),"淘汰了")
    }

    return {
        winner:queue.dequeue()
    }
}

game(["kerwin","tiechui","xiaoming","gangdaner","guludunzi"],7)

5. 双端队列

class DeQueue {
        #items = {}
        #lowCount = 0 //记录队头索引
        #count = 0
        removeFront() {
          if (this.isEmpty()) {
            return undefined
          }
          let res = this.#items[this.#lowCount]
          delete this.#items[this.#lowCount]
          this.#lowCount++
          return res
        }

        addBack(data) {
          this.#items[this.#count] = data
          this.#count++
        }

        addFront(data) {
          if (this.isEmpty()) {
            this.addBack(data)
          } else {
            if (this.#lowCount > 0) {
              //#lowCount>0
              this.#lowCount--
              this.#items[this.#lowCount] = data
            } else {
              //#lowCount===0
              for (let i = this.#count; i > 0; i--) {
                this.#items[i] = this.#items[i - 1]
              }
              this.#count++
              this.#lowCount = 0
              this.#items[0] = data
            }
          }
        }

        removeBack() {
          if (this.isEmpty()) {
            return undefined
          }

          this.#count--
          const result = this.#items[this.#count]
          delete this.#items[this.#count]

          return result
        }

        peekFront() {
          return this.#items[this.#lowCount]
        }

        peekBack() {
          if (this.isEmpty()) {
            return undefined
          }
          return this.#items[this.#count - 1]
        }

        isEmpty() {
          return this.size() === 0
        }

        size() {
          return this.#count - this.#lowCount
        }

        clear() {
          this.#items = {}
          this.#count = 0
          this.#lowCount = 0
        }

        toString() {
          let str = ''
          for (let i = this.#lowCount; i < this.#count; i++) {
            str += `${this.#items[i]} `
          }
          return str
        }
      }