数据结构与算法-队列

《学习JavaScript数据结构与算法(第3版)》

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

队列数据结构

export default 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.size() === 0;
    }

    // 清除队列
    clear() {
        this.items = {};
        this.count = 0;
        this.lowestCount = 0;
    }

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

    // 队列输出
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        let objString = `${this.items[this.lowestCount]}`;
        for (let i = this.lowestCount + 1; i < this.count; i++) {
            objString = `${objString},${this.items[i]}`;
        }
        return objString;
    }
}

双端队列

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

同时，遵循了先进先出和后进先出原则。

export default class Deque {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
    
    // 在双端队列前端添加新的元素
    addFront(element) {
        if (this.isEmpty()) {
            this.addBack(element);
        } else if (this.lowestCount > 0) { 
            // 如果双端队列删除过前端元素，只需要lowestCount属性减1并将新的值放在这个键的位置上
            this.lowestCount--;
            this.items[this.lowestCount] = element;
        } else {
            // lowestCount为0
            // 方法一：设置一个负值键，同时更新用于计算双端队列长度的逻辑，使其也包含负值。这种情况下，添加一个新元素的操作仍然能保持最低的计算成本。
            // 方法二：类似数组，将所有元素后移一位来空出第一个位置。然后将新元素覆盖第一个位置。如下。
            for (let i = this.count; i > 0; i--) {
                this.items[i] = this.items[i - 1];
            }
            this.count++;
            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];
    }

    // 双端队列是否为空
    isEmpty() {
        return this.size() === 0;
    }

    // 清除双端队列
    clear() {
        this.items = {};
        this.count = 0;
        this.lowestCount = 0;
    }

    // 返回双端队列元素数量
    size() {
        return this.count - this.lowestCount;
    }

    // 输出双端队列元素
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        let objString = `${this.items[this.lowestCount]}`;
        for (let i = this.lowestCount + 1; i < this.count; i++) {
            objString = `${objString},${this.items[i]}`;
        }
        return objString;
    }
}

用队列解决问题

击鼓传花游戏——循环列表

n个同学坐着围成一个圆圈，指定一个同学手里拿着一束花，每个同学都需要将花传给下一个同学，将花传递m次，得到花的人出局，然后再将花向下传递m次，得到花的人出局，以此类推，最后剩下的是哪位同学？（传递过程中不考虑已经出局的人）

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

import Queue from '../queue';

export function hotPotato(elementsList, num) {
  const queue = new Queue();
  const elimitatedList = [];

  for (let i = 0; i < elementsList.length; i++) {
    queue.enqueue(elementsList[i]); // 把所有同学加入队列
  }

  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    elimitatedList.push(queue.dequeue());
  }

  return {
    eliminated: elimitatedList,
    winner: queue.dequeue()
  };
}

使用算法：

const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
const result = hotPotato(names, 7);
result.eliminated.forEach(name => {
    console.log(`${name}在击鼓传花游戏中淘汰。`);
});

console.log(`胜利者：${result.winner}`);

检查短语是否为回文——回文检查器, 双端队列

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

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

import Deque from '../deque';

export 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(''); // 将所有字母转化为小写，同时移除空格
    let firstChar;
    let lastChar;
    let isEqual = true;

    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;
}