队列数据结构

• 描述
  队列是遵行先进先出原则的一组有序项。队列在尾部添加元素，并从顶部移除元素，最新添加的元素排在队列的末尾。
• 队列的方法

1. enqueue():向队列尾部添加一个或多个新的项。
2. dequeue():移除队列的第一项并返回移除的元素。
3. peek():返回队列第一个添加的元素，对队列不做任何改动。
4. isEmpty():判断队列是否为空，是返回true,否返回false。
5. size():返回队列包含的元素个数。

• 实现代码

class Queue{
    constructor(){
        this.count=0
        this.lowestCount=0
        this.items={}
    }
    // 向队列中添加元素
    enqueue(element){
        this.items[this.count]=element
        this.count++
    }
    // 向队列中移除元素并返回移除的元素
    dequeue(){
        if(this.isEmpty()){
            return undefined
        }
        const result=this.items[this.lowestCount]
        delete this.items[this.lowestCount]
        this.lowestCount++
        return result
    }
    // 查看队列头元素
    peek(){
        if(this.isEmpty()){
            return undefined
        }
        return this.items[this.lowestCount]
    }
    // 检查队列是否为空
    isEmpty(){
        return this.count-this.lowestCount===0
    }
    // 检查队列长度
    size(){
        return this.count-this.lowestCount
    }
    // 清空队列
    clear(){
        this.items={}
        this.count=0
        this.lowestCount=0
    }
    toString(){
        if(this.isEmpty()){
            return undefined
        }
        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 failPeoples=[]
    for(let i=0;i<elementsList;i++){
        queue.enqueue(elementsList[i])
    }
    while(queue.size()>1){
        for(let i=0;i<num;i++){
            queue.enqueue(queue.dequeue())
        }
        failPeoples.push(queue.dequeue())
    }
    return{
        failure:failPeoples,
        winner:queue.dequeue()
    }
}

双端队列数据结构

• 描述
  双端队列是一种允许我们同时从前端和后端添加和移除元素的特殊队列。
• 方法

1. addFront():在双端队列前端添加新的元素。
2. addBack():在双端队列后端添加新的元素。
3. removeFront():从双端队列前端移除第一个元素并返回。
4. removeBack():从双端队列后端移除第一个元素并返回。
5. peekFront():返回双端队列前端第一个元素，不对双端队列做任何修改。
6. peekBack():返回双端队列后端第一个元素，不对双端队列做任何修改。

• 代码实现

class Deque{
    constructor(){
        this.count=0
        this.lowestCount=0
        this.items={}
    }
    // 检查队列是否为空
    isEmpty(){
        return this.count-this.lowestCount===0
    }
    // 判断队列长度
    size(){
        return this.count-this.lowestCount
    }
    // 将队列元素转化为字符串
    toString(){
    if(this.isEmpty()){
        return undefined
    }
    let objString=`${this.items[this.lowestCount]}`
    for(let i=this.lowestCount+1;i<this.count;i++){
        objString=`${objString},${this.items[i]}`
    }
    return objString
    }
    // 清空队列元素
    clear(){
    this.count=0
    this.lowestCount=0
    this.items={}
    }
    //双端队列前端添加新的元素
    addFront(element){
        if(this.isEmpty()){
           this.addBack() 
        }else{
        if(this.lowestCount>0){
        this.lowestCount--
        this.items[this.lowestCount]=element
        }else{
         for(let i=this.count;i>0;i--){
             this.items[i]=this.items[i-1]
         }
         this.count++
         this.lowestCount=0
         this.items[0]=element
        }
        }
    }
    // 向双端队列后端添加元素
    addBack(element){
        this.items[this.count]=element
        this.count++
    }
    // 双端队列的前端移除第一个元素
    removeFront(){
        if(this.isEmpty()){
            return undefined
        }
        const result=this.items[this.lowestCount]
        delete this.items[this.lowestCount]
        this.lowestCount++
        return result
    }
    // 双端队列的后端移除第一个元素
    removeBack(){
        if(this.isEmpty()){
            return undefined
        }
        this.count--
        const result=this.items[this.count]
        delete this.items[this.count]
        return result
    }
    // 返回双端队列前端的第一个元素
    peekFront(){
        if(this.isEmpty()){
            return undefined
        }
        return this.items[this.lowestCount]
    }
    // 返回双端队列后端的第一个元素
    peekBack(){
        if(this.isEmpty()){
            return undefined
        }
        return this.items[this.count-1]
    }
}

• 双端队列解决回文序列问题
  代码实现

function palindromeChecker(aString){
if(aString==undefined||aString==null||(aString!==null&&aString.length===0)){
    return false
}
const deque=new Deque()
const lowerString=aString.toLocaleLowerCase().split(' ').join('')
for(let i=0;i<lowerString.length;i++){
    deque.addBack(lowerString.charAt(i))
}
let isEqual=true
let firstchar,lastchar
while (deque.size()>1&&isEqual) {
    firstchar=deque.removeFront()
    lastchar=deque.removeBack()
    if(firstchar!=lastchar){
        isEqual=false
    }
}
return isEqual
}