JavaScript 队列

队列是遵循先进先出（FIFO，也称先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

在现实中，最常见的队列的例子就是排队。在电影院，学校饭堂，我们都会排队。排在第一位的人会先接受服务。

4.1 创建队列

创建队列类Queue

我们规划一下队列可用的方法：

**enqueue(element)**：向队列尾部添加一个（或）多个新的项。

**dequeue()**：移除队列的第一项（即排在队列最前面的项）并返回被移除的元素

**peek()**：返回队列中第一个元素，即最先添加的元素

**isEmpty()**：如果队列中不包含任何元素，返回true，否则返回false

**size()**：返回队列包含的元素个数。

**clear()**：清空队列

**toString()**：转成String

class Queue {
    _count = 0; //用来记队列的大小
    _lowestCount = 0;   //因为队列需要操作第一个元素，需要一个变量来帮助追踪第一个元素
    _items = {};    // 存储队列元素
    constructor() {
    }

    /**
     * 向队列尾部添加一个（或）多个新的项
     * @param element
     */
    enqueue(element) {
        this._items[this._count] = element;
        this._count++;
    }

    /**
     * 移除队列的第一项（即排在队列最前面的项）并返回被移除的元素
     */
    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        let 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];
    }

    /**
     * 如果队列中不包含任何元素，返回true，否则返回false
     */
    isEmpty() {
        return this.size() === 0;
    }

    /**
     * 返回队列包含的元素个数
     */
    size() {
        return this._count - this._lowestCount;
    }

    /**
     * 清空队列
     */
    clear() {
        this._items = {};
        this._count = 0;
        this._lowestCount = 0;
    }

    toString() {
        if (this.isEmpty()) {
            return '';
        }
        let str = this._items[this._lowestCount];
        for (let i = this._lowestCount + 1; i < this._count; i++) {
            str += ',' + this._items[i];
        }
        return str;
    }
}

使用队列：

let queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue('张三');
queue.enqueue('李四');
console.log(queue.toString()) // 张三,李四
console.log(queue.size());  // 2
console.log(queue.peek()); // 张三
queue.dequeue();
console.log(queue.toString()) // 李四

4.2 双端队列

双端队列(deque，或称double-ended queue) 是一种允许我们同时从前端和后端添加和移除元素的特殊队列。

​ 双端队列在现实生活中的例子有电影院、餐厅中排队的队伍等。举个栗子，一个刚买了票的人如果只是还需要再问一些简单的信息，就可以直接回到队伍的头部。另外，在队伍末尾的人如果赶时间，他可以直接离开队伍。

​ 在计算机科学中，双端队列的一个常见应用是存储一系列的撤销操作。每当用户在软件中进行了一个操作，该操作会被存在一个双端队列中。当用户点击撤销按钮时该操作会被从双端队列中弹出，表示它被从后面移除了。在进行了预先定义的一定数量的操作后，最先进行的操作会被从双端队列的前端移除。由于双端队列同时遵守了先进先出****和后进先出**原则，可以说它是把对了和栈相结合的一种数据结构。

​ 既然双端队列是一种特殊的队列，我们可以看到其有多个方法的代码与队列相同

**isEmpty()**：如果队列中不包含任何元素，返回true，否则返回false

**size()**：返回队列包含的元素个数。

**clear()**：清空队列

**toString()**：转成String

我们再规划一下其他可用的方法：

**addFront(element)**：在双端队列前端添加新元素

**addBack(element)**：在双端队列后端新增新的元素

**removeFront()**：从双端队列前端移除第一个元素，并返回该元素

**removeBack()**：从双端队列后端移除第一个元素，并返回该元素

**peekFront()**：返回双端队列前端第一个元素

**peekBack()**：返回双端队列后端第一个元素

实现代码如下：

class Deque {
    _count = 0; //用来记队列的大小
    _lowestCount = 0;   //因为队列需要操作第一个元素，需要一个变量来帮助追踪第一个元素
    _items = {};    // 存储队列元素
    constructor() {
    }

    /**
     * 在双端队列前端添加新元素
     * @param element
     */
    addFront(element) {
        if (this.isEmpty()) {   //空队列
            this.addBack(element);
        } 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._items[0] = element;
        }
    }

    /**
     * 在双端队列后端新增新的元素
     * @param element
     */
    addBack(element) {
        this._items[this._count] = element;
        this._count++;
    }

    /**
     * 从双端队列前端移除第一个元素，并返回该元素
     */
    removeFront() {
        if (this.isEmpty()) {
            return undefined;
        }
        let result = this._items[this._lowestCount];
        delete this._items[this._lowestCount];
        this._lowestCount++;
        return result;
    }

    /**
     * 从双端队列后端移除第一个元素，并返回该元素
     */
    removeBack() {
        if (this.isEmpty()) {
            return undefined;
        }
        this._count--
        let result = this._items[this._count];
        delete this._items[this._count];
        return result;
    }

    /**
     * 返回双端队列前端第一个元素
     */
    peekFront() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this._items[this._lowestCount];
    }

    /**
     * 返回双端队列后端第一个元素
     */
    peekBack() {
        return this._items[this._count - 1];
    }

    /**
     * 如果队列中不包含任何元素，返回true，否则返回false
     */
    isEmpty() {
        return this.size() === 0;
    }

    /**
     * 返回队列包含的元素个数
     */
    size() {
        return this._count - this._lowestCount;
    }

    /**
     * 清空队列
     */
    clear() {
        this._items = {};
        this._count = 0;
        this._lowestCount = 0;
    }

    toString() {
        if (this.isEmpty()) {
            return '';
        }
        let str = this._items[this._lowestCount];
        for (let i = this._lowestCount + 1; i < this._count; i++) {
            str += ',' + this._items[i];
        }
        return str;
    }
}

使用双端队列Deque类

let deque = new Deque();
console.log(deque.isEmpty()); //true
deque.addBack('张三');
deque.addBack('李四');
deque.addFront('王五');
console.log(deque.toString()) // 王五,张三,李四
deque.removeFront();
console.log(deque.toString()); // 张三,李四
deque.removeBack();
console.log(deque.toString()); // 张三

4.3 使用队列和双端队列来解决问题

4.3.1 击鼓传花游戏

击鼓传花游戏：孩子们围成一个圆圈，把花尽快地传给旁边的人。某一时刻传花停止。这个时候花在谁手里，谁就退出圆圈，结束游戏。重复这个过程，直到只剩一个孩子（胜者）。

/**
 * 击鼓传花游戏
 * @param list 参与者列表
 * @param num 传花次数
 * @return {{winner: *, eliminate: []}}
 */
function hotPotato(list, num) {
    let queue = new Queue();
    let eliminatedList = [];
    //把所有参与者加入队列中
    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())
        }
        eliminatedList.push(queue.dequeue());
    }
    return {
        eliminate: eliminatedList,
        winner: queue.dequeue()
    }
}

应用hotPotato()算法：

const names = ['张三','李四','王五','John','Jack'];
const result = hotPotato(names,8);
result.eliminate.forEach(name => {
    console.log(name + '在击鼓传花游戏中被淘汰。')
})
console.log('胜利者：' + result.winner)

以上输出如下：

4.3.2 回文检查器

回文是正反都能读通的单词，词组、数或一系列字符的序列，例如：madam或racecar。

​ 有不同的算法可以检查一个词组或字符串是否为回文。最简单的方式是将字符串反向排列并检查它和原字符串是否相同。如果两者相同，那么它就是一个回文。我们也可以用栈来完成，但是利用数据结构来解决这个问题的最简单方法就是使用双端队列

/**
 * 回文检查器
 * @param content 需要检查的字符串
 * @return {boolean}
 */
function palindromeDetector(content) {
    if (content === undefined || content === null || content.length === 0) {
        return false;
    }
    let deque = new Deque();
    let lowerString = content.toLocaleLowerCase().split(' ').join(''); // 全转成小写并移除空格
    let isEqual = true;
    let firstChar, lastChar;
    for (let i = 0; i < lowerString.length; i++) {
        deque.addBack(lowerString.charAt(i));
    }
    while (deque.size() > 1 && isEqual) {
        firstChar = deque.removeFront();
        lastChar = deque.removeBack();
        if (firstChar !== lastChar) {
            isEqual = false;
        }
    }
    return isEqual;

}

我们来应用一下**palindromeDetector()**算法：

console.log('a',palindromeDetector('a')); // true
console.log('aa',palindromeDetector('aa')); // true
console.log('kayak',palindromeDetector('kayak')); // true
console.log('hello',palindromeDetector('hello')); // false