Javascript数据结构之队列和双端队列

队列数据结构

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

Queue 队列类

• enqueue（element(s)）：插入一个新元素到队列项
• dequeue()：移除队列的头元素，同时返回被移除的元素
• peek()：返回队列的头元素，不对队列做任何修改（该方法不会移除队列头元素，仅仅返回它）
• isEmpty()：如果队列里没有任何元素就返回 true，否则返回 false
• clear()：移除队列里所有元素
• size()：返回队列里的元素个数，该方法和数组的 length 属性很类似

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;
  }
  // 返回队列长度
  size() {
    return this.count - this.lowestCount;
  }
  // 清空队列
  clear() {
    this.items = {}
    this.count = 0;
    this.lowestCount = 0;
  }
  // toString 方法
  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;
  }
}

const queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue('john');
queue.enqueue('jack');
console.log(queue.toString()); //john,jack
queue.enqueue('camila');
console.log(queue.toString()); // john,jack,camila
console.log(queue.size()); // 3
console.log(queue.isEmpty()); // false
queue.dequeue();
queue.dequeue();
console.log(queue.toString()); // camila

双端队列数据结构

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

双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。

• addFront(element)：该方法在双端队列前端插入新的元素
• addBack(element)：该方法在双端队列后端插入新的元素
• removeFront()：该方法从双端队列前端移除第一个元素
• removeBack()：该方法从双端队列后端移除第一个元素
• peekFront()：该方法返回双端队列前端的第一个元素
• peekBack()：该方法返回双端队列后端的第一个元素
• isEmpty()：如果队列里没有任何元素就返回 true，否则返回 false
• clear()：移除队列里所有元素
• size()：返回队列里的元素个数，该方法和数组的 length 属性很类似

class Deque {
  constructor() {
    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];
  }
  // 检查队列是否为空
  isEmpty() {
    return this.size() === 0;
  }
  // 返回队列长度
  size() {
    return this.count - this.lowestCount;
  }
  // 清空队列
  clear() {
    this.items = {}
    this.count = 0;
    this.lowestCount = 0;
  }
  // toString 方法
  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;
  }
}

const deque = new Deque();
console.log(deque.isEmpty()); // true
deque.addBack('john');
deque.addBack('jack');
console.log(deque.toString()); // john, jack
deque.addBack('camila');
console.log(deque.size()); // 3
console.log(deque.isEmpty()); // false
deque.removeFront();
console.log(deque.toString()); // jack, camila
deque.removeBack();
console.log(deque.toString()); // jack
deque.addFront('john');
console.log(deque.toString()); // john, jack

队列和双端队列的运用

比如使用队列来模拟击鼓传花游戏，并使用双端队列来检查一个短语是否为回文。

• 队列之击鼓传花游戏

把参与者数据传入队列中，传递 num 次，每次把移除的人再重新加入队列。传递 num 次后，队列中最后一个人就是淘汰的，这个人退出游戏，如些直至队列中的人小于等于1为止，剩下的最后一个人即为胜利者。

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

  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());
    }
    eliminatedList.push(queue.dequeue())
  }
  return {
    eliminated: eliminatedList,
    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}`);
// camila在击鼓传花游戏中被淘汰
// jack在击鼓传花游戏中被淘汰
// carl在击鼓传花游戏中被淘汰
// ingrid在击鼓传花游戏中被淘汰
// 胜利者：john

• 回文检查器

利用双端队列数据结构，从最前端、最后端取值，检查是否相等，如果不相等则不是回文字符，直至双端队列数据小于等于 1

function isPalindrome(value) {
  if (value === undefined || value === null || (value !== null && value.length === 0)) {
    return false;
  }
  const deque = new Deque();
  const lowerString = value.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;
}

console.log('a', isPalindrome('a')); // true
console.log('aa', isPalindrome('aa')); // true
console.log('kayak', isPalindrome('kayak')); // true
console.log('1001', isPalindrome('1001')); // true
console.log('level', isPalindrome('level')); // true
console.log('levels', isPalindrome('levels')); // false