本文由 发布，转载请注明出处，如有问题请联系我们！ 发布时间: 2021-08-10前端学习 数据结构与算法 快速入门 系列 —— 队列和双端队列

序列和双端队列

前边大家早已学了栈算法设计。序列和栈十分相近，栈的标准是先进先出，而序列则是先进先出法。与此同时，我们要学习培训双端队列，它是一种容许大家与此同时从前端和后端加上原素和清除原素的独特序列。

序列算法设计

序列遵循先进先出法（FIFO，也称之为先去先服务项目）标准的一组井然有序的项。序列在尾端加上原素，并从序列头顶部删掉原素。

现实生活中的序列有：

• 排长队购票，排在第一位的先接纳服务项目，刚来的人则排在队尾
• 打印出，例如有 10 份文本文档，先后对每一个文本文档点一下打印出，每一个文本文档将发送至打印出序列，第一个推送的文本文档最开始被打印出，排在最后的文本文档则最终才打印出

建立序列

最先大家建立一个自身的类来表明序列。

class Queue {
    constructor() {
        this.items = {}
        // 序列头顶部数据库索引
        this.startIndex = 0
        // 序列尾端数据库索引
        this.lastIndex = 0
    }
}

大家应用一个目标来储存序列中的原素，自然你还可以应用二维数组。因为必须 从序列头顶部删掉原素，及其从队尾插进原素，因此 这儿界定了2个自变量。

下面必须 申明一些序列必须 的方式 ：

• enqueue(element1[, element2, element3, ...])，给序列尾端插进一个或好几个值
• dequeue()，从序列头顶部删掉第一项，并回到被清除的原素
• isEmpty()，假如序列不包含一切原素则回到 true，不然回到 false
• size()，回到序列中原素的数量
• peek()，获得序列第一部第一个原素。该方式 在别的语言表达还可以称为 front 方式
• clear()，消除序列
• toString()，调用 toString() 方式

向序列插进原素

enqueue(...values) {
    values.forEach(item => {
        this.items[this.lastIndex  ] = item;
    })
}

查询序列是不是为空

isEmpty() {
    return Object.is(this.startIndex, this.lastIndex)
}

从序列清除原素

dequeue() {
    if (this.isEmpty()) {
        return undefined
    }
    const value = this.items[this.startIndex]
    delete this.items[this.startIndex  ]
    return value
}

查询序列头原素

peek() {
    return this.items[this.startIndex]
}
front() {
    return this.peek()
}

序列原素数量

size() {
    return this.lastIndex - this.startIndex
}

清除序列

clear() {
    this.items = {}
    this.startIndex = 0
    this.lastIndex = 0
}

调用 toString() 方式

toString() {
    if (this.isEmpty()) {
        return ''
    }
    return Object.values(this.items).join(',')
}

应用 Queue 类

class Queue {
    constructor() {
        this.items = {}
        // 序列头顶部数据库索引
        this.startIndex = 0
        // 序列尾端数据库索引
        this.lastIndex = 0
    }
    // 向序列插进原素
    enqueue(...values) {
        values.forEach(item => {
            this.items[this.lastIndex  ] = item;
        })
    }
    isEmpty() {
        return Object.is(this.startIndex, this.lastIndex)
    }
    // 从序列清除原素
    dequeue() {
        if (this.isEmpty()) {
            return undefined
        }
        const value = this.items[this.startIndex]
        delete this.items[this.startIndex  ]
        return value
    }
    peek() {
        return this.items[this.startIndex]
    }
    front() {
        return this.peek()
    }
    size() {
        return this.lastIndex - this.startIndex
    }
    clear() {
        this.items = {}
        this.startIndex = 0
        this.lastIndex = 0
    }
    toString() {
        if (this.isEmpty()) {
            return ''
        }
        return Object.values(this.items).join(',')
    }
}

let q1 = new Queue()
q1.enqueue('a', 'b', { c: 'c1' })
console.log(q1.items) // { '0': 'a', '1': 'b', '2': { c: 'c1' } }
console.log(q1.toString()) // a,b,[object Object]
console.log(q1.peek()) // a
console.log(q1.front()) // a
console.log(q1.dequeue()) // a
console.log(q1.dequeue()) // b
console.log(q1.items) // { '2': { c: 'c1' } }

双端队列算法设计

双端队列（deque，或称 double-ended queue）是一种容许大家与此同时从前端和后端加上原素和清除原素的独特序列。

双端队列在现实生活中的事例有排长队购票。举个事例，一个刚买完票的人假如还必须 回来资询一些事，就可以立即返回团队头顶部，而在队尾的人假如有急事，还可以立即离去团队

建立双端队列

双端队列做为一种独特的序列，有着以下方式 ：

• addFront(elemnt[, element2, element3, ...])，给序列前面加上一个或好几个原素
• addBack(elemnt[, element2, element3, ...])，给序列尾端加上一个或好几个原素
  • 完成与 Queue 类的 enqueue 方式 一样
• removeFront()，从序列头顶部删掉原素，并回到删掉的原素
  • 完成与 Queue 类的 dequeue 方式 一样
• removeBack()，从序列尾端删掉原素，并回到删掉的原素
• clear()，清除双端队列
  • 完成与 Queue 类中的 clear 方式 一样
• isEmpty()，双端队列中要是没有原素，则回到 true，不然回到 false
  • 完成与 Queue 类中的 isEmpty 方式 一样
• peekFront()，获得序列头顶部第一个原素
  • 完成与 Queue 类中的 peek 方式 一样
• peekBack()，获得序列尾端最后一个原素
• size()，获得序列中原素的数量
  • 完成与 Queue 类中的 size 方式 一样
• toString()，调用 toString() 方式

Tip：依据每一个人不一样的完成，会出现一部分编码与序列同样

大家最先申明一个 Deque 类以及构造方法：

class Deque {
    // 与 Queue 构造方法同样
    constructor() {
        this.items = {}
        this.startIndex = 0
        this.lastIndex = 0
    }
}

给序列前面加上

// 给序列头顶部加上一个或好几个原素
addFront(...values) {
    values.reverse().forEach(item => {
        this.items[--this.startIndex] = item;
    })
}

从序列尾端删掉原素

// 从序列尾端删掉原素
removeBack() {
    if (this.isEmpty()) {
        return undefined
    }
    this.lastIndex--
    const value = this.items[this.lastIndex]
    delete this.items[this.lastIndex]
    return value
}

获得序列尾端最后一个原素

peekBack() {
    return this.items[this.lastIndex - 1]
}

调用 toString() 方式

toString() {
    if (this.isEmpty()) {
        return ''
    }
    let { startIndex, lastIndex } = this
    const result = []
    while (!Object.is(startIndex, lastIndex)) {
        result.push(this.items[startIndex  ])
    }
    return result.join(',')
}

应用 Deque 类

/**
 * 双端队列
 *
 * @class Deque
 */
class Deque {
    // 与 Queue 构造方法同样
    constructor() {
        this.items = {}
        this.startIndex = 0
        this.lastIndex = 0
    }
    // 给序列头顶部加上一个或好几个原素
    addFront(...values) {
        values.reverse().forEach(item => {
            this.items[--this.startIndex] = item;
        })
    }
    // 完成与 Queue 类的 enqueue 方式 一样
    addBack(...values) {
        values.forEach(item => {
            this.items[this.lastIndex  ] = item;
        })
    }
    // 完成与 Queue 类的 dequeue 方式 一样
    removeFront() {
        if (this.isEmpty()) {
            return undefined
        }
        const value = this.items[this.startIndex]
        delete this.items[this.startIndex  ]
        return value
    }
    // 从序列尾端删掉原素
    removeBack() {
        if (this.isEmpty()) {
            return undefined
        }
        this.lastIndex--
        const value = this.items[this.lastIndex]
        delete this.items[this.lastIndex]
        return value
    }
    // 完成与 Queue 类中的 peek 方式 一样
    peekFront() {
        return this.items[this.startIndex]
    }
    peekBack() {
        return this.items[this.lastIndex - 1]
    }
    // 与 Queue 类中的 isEmpty 方式 一样
    isEmpty() {
        return Object.is(this.startIndex, this.lastIndex)
    }
    // 完成与 Queue 类中的 size 方式 一样
    size() {
        return this.lastIndex - this.startIndex
    }
    // 完成与 Queue 类中的 clear 方式 一样
    clear() {
        this.items = {}
        this.startIndex = 0
        this.lastIndex = 0
    }
    // 调用 toString() 方式 
    toString() {
        if (this.isEmpty()) {
            return ''
        }
        let { startIndex, lastIndex } = this
        const result = []
        while (!Object.is(startIndex, lastIndex)) {
            result.push(this.items[startIndex  ])
        }
        return result.join(',')
    }
}

let deque = new Deque()
// 序列头顶部加上
deque.addFront('a')
deque.addFront('c', 'd')
console.log(deque.toString()) // c,d,a

// 序列尾端加上
deque.addBack(3)
deque.addBack(4, 5)
console.log(deque.toString()) // c,d,a,3,4,5

// 从头顶部和尾端删掉原素
console.log(deque.removeBack()) // 5
console.log(deque.removeFront()) // c
console.log(deque.toString()) // d,a,3,4

// 查询序列头顶部和尾端的原素
console.log(deque.peekFront()) // d
console.log(deque.peekBack()) // 4

// 序列中原素数量
console.log(deque.size()) // 4

// 清除序列
deque.clear()

// 序列是不是为空
console.log(deque.isEmpty()) // true
// 序列原素数量
console.log(deque.size()) // 0

应用序列和双端队列解决困难

循环队列 —— 击鼓传花

击鼓传花手机游戏：

小朋友排成一个圆形，把花尽量地传送给边上的人，某一時刻，花在谁手上，谁就撤出圆形。反复这一全过程，直至只剩一个小孩（获胜）。

例如：

// 有五个小孩子
const people = ['p1', 'p2', 'p3', 'p4', 'p5']
// 进入游戏
击鼓传花(people)

传送频次:  3
p4 取代
传送频次:  5
p1 取代
传送频次:  1
p3 取代
传送频次:  1
p2 取代
p5 获胜

小编完成以下：

// 转化成 1 ~ 5 的随机数字
function getRandomInt(max = 5) {
    return Math.floor(Math.random() * max)   1;
}

function 击鼓传花(people, count = getRandomInt) {
    const queue = new Queue()
    // 进到序列
    people.forEach(item => queue.enqueue(item))

    // 传送 size - 1 次
    let number = queue.size() - 1
    while (number--) {
        let _count = count()
        console.log('传送频次: ', _count);
        while (_count--) {
            queue.enqueue(queue.dequeue())
        }
        console.log(queue.dequeue()   ' 取代');
    }

    // 剩余的便是胜者
    console.log(queue.peek()   ' 获胜');
}

回文查验器

wiki百科对回文的表述：

回文是正反面都能读通的英语单词、短语、数或一系列标识符的编码序列，比如 madam 或 racecar。

有不一样的优化算法查验一个短语或字符串数组是不是为回文。

非常简单的方法是将字符串数组反方向排序并查验它和原先字符串数组是不是同样。假如二者同样，那麼它便是一个回文。

运用算法设计来处理此难题非常简单的方法是应用双端队列。

小编完成以下：

/**
 * 回文查验器
 *
 * @param {String} str
 * @return {Boolean} 
 */
function palindromeChecker(str) {
    if (typeof str !== 'string') {
        throw new Error('输入您字符串数组')
    }
    let flag = true
    // 忽视英文大小写及其清除全部空格符
    str = str.toLowerCase().replace(/\s/g, '')
    // 变为双端队列
    let deque = new Deque()
    deque.addBack(...str)

    // 比照频次
    let count = Math.floor(deque.size() / 2)
    while (count-- && flag) {
        if (deque.removeFront() !== deque.removeBack()) {
            flag = false
        }
    }
    // 回到結果

    return flag
}

// 全部輸出全是 true
console.log('a', palindromeChecker('a'))
console.log('aa', palindromeChecker('aa'))
console.log('kayak', palindromeChecker('kayak'))
console.log('level', palindromeChecker('level'))
console.log('Was it a car or a cat I saw', palindromeChecker('Was it a car or a cat I saw'))
console.log('Step on no pets', palindromeChecker('Step on no pets'))

Tip：小编将回文的范畴放比较宽松了一些，例如忽视英文大小写，与此同时清除全部空格符。假如想要，你要能够忽视全部特殊符号。

序列详细编码

class Queue {
    constructor() {
        this.items = {}
        // 序列头顶部数据库索引
        this.startIndex = 0
        // 序列尾端数据库索引
        this.lastIndex = 0
    }
    // 向序列插进原素
    enqueue(...values) {
        values.forEach(item => {
            this.items[this.lastIndex  ] = item;
        })
    }
    isEmpty() {
        return Object.is(this.startIndex, this.lastIndex)
    }
    // 从序列清除原素
    dequeue() {
        if (this.isEmpty()) {
            return undefined
        }
        const value = this.items[this.startIndex]
        delete this.items[this.startIndex  ]
        return value
    }
    peek() {
        return this.items[this.startIndex]
    }
    front() {
        return this.peek()
    }
    size() {
        return this.lastIndex - this.startIndex
    }
    clear() {
        this.items = {}
        this.startIndex = 0
        this.lastIndex = 0
    }
    toString() {
        if (this.isEmpty()) {
            return ''
        }
        return Object.values(this.items).join(',')
    }
}

/**
 * 双端队列
 *
 * @class Deque
 */
class Deque {
    // 与 Queue 构造方法同样
    constructor() {
        this.items = {}   this.startIndex = 0
        this.lastIndex = 0
    }
    // 给序列头顶部加上一个或好几个原素
    addFront(...values) {
        values.reverse().forEach(item => {
            this.items[--this.startIndex] = item;
        })
    }
    // 完成与 Queue 类的 enqueue 方式 一样
    addBack(...values) {
        values.forEach(item => {
            this.items[this.lastIndex  ] = item;
        })
    }
    // 完成与 Queue 类的 dequeue 方式 一样
    removeFront() {
        if (this.isEmpty()) {
            return undefined
        }
        const value = this.items[this.startIndex]
        delete this.items[this.startIndex  ]
        return value
    }
    // 从序列尾端删掉原素
    removeBack() {
        if (this.isEmpty()) {
            return undefined
        }
        this.lastIndex--
        const value = this.items[this.lastIndex]
        delete this.items[this.lastIndex]
        return value
    }
    // 完成与 Queue 类中的 peek 方式 一样
    peekFront() {
        return this.items[this.startIndex]
    }
    peekBack() {
        return this.items[this.lastIndex - 1]
    }
    // 与 Queue 类中的 isEmpty 方式 一样
    isEmpty() {
        return Object.is(this.startIndex, this.lastIndex)
    }
    // 完成与 Queue 类中的 size 方式 一样
    size() {
        return this.lastIndex - this.startIndex
    }
    // 完成与 Queue 类中的 clear 方式 一样
    clear() {
        this.items = {}
        this.startIndex = 0
        this.lastIndex = 0
    }
    // 调用 toString() 方式 
    toString() {
        if (this.isEmpty()) {
            return ''
        }
        let { startIndex, lastIndex } = this
        const result = []
        while (!Object.is(startIndex, lastIndex)) {
            result.push(this.items[startIndex  ])
        }
        return result.join(',')
    }
}