JavaScript数据结构（二）队列

队列是一个先进先出的数据结构

JavaScript中没有队列，但可以用Array实现队列的所有功能

队列常用操作：push、shift、queue[0]

1. 队列定义

先进先出（排队）

队列在尾部添加新元素，并从顶部移除元素

最新添加的元素必须排在队列的末尾

用途：

食堂排队打饭

JS异步中的任务队列

计算最近请求次数

……

2. 队列具体操作

创建

class Queue {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};  //使用对象来存储
    }
}
复制代码

方法

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

  enqueue(element(s)) {
      this.items[this.count] = element;
      this.count++;
  }
  复制代码

• dequeue()：移除队列的第一项，并返回被移除的元素

  dequeue() {
      if(this.isEmpty()) {
          return undefined;
      }
      const result = this.items[this.lowestCount];
  	delete this.items[this.lowestCount];
  	this.lowestCount++;
      return result;
  }
  复制代码

• peek()：返回队列中第一个元素，也将是最先被移除的元素（不移除元素，只返回元素信息）

  peek() {
      if(this.isEmpty()) {
          return undefined;
      }
      return this.items[this.lowestCount];
  }
  复制代码

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

  isEmpty() {
      return this.count - this.lowestCount === 0;
      //return this.size() === 0;
  }
  复制代码

• size()：返回队列包含的元素个数，与数组的length属性类似

  size() {
      return this.count - this.lowestCount;
  }
  复制代码

• clear(): 清空所有元素

  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;
  }
  复制代码

  由于Queue 类中的第一个索引值不一定为0，所以从索引值为lowestCount 的位置开始迭代队列

3.queue类使用

同stack

4. 双端队列定义

先进先出 + 后进先出

前后都能进行添加和移除元素的特殊队列

应用：

撤销操作

5. 双端队列的具体操作

创建

class Deque {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
}
复制代码

方法

和queue相同的： isEmpty、clear、size、toString

和queue不同的：

• addFront(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.lowestCount = 0;
          this.items[0] = element;
      }
  }
  复制代码

• addBack(element)：在后端添加新的元素（和enqueue()相同）

  addBack(element) {
      this.items[this.count] = element;
      this.count++;
  }
  复制代码

• removeFront()：从前端移除第一个元素（和dequeue 方法相同）

  removeFront() {
      if(this.isEmpty()) {
          return undefined;
      }
      const result = this.items[this.lowestCount];
  	delete this.items[this.lowestCount];
  	this.lowestCount++;
      return result;
  }
  复制代码

• removeBack()：从后端移除第一个元素（和Stack 类中的pop 相同）

  removeBack() {
  	return this.items.pop();
  }
  复制代码

• peekFront()：返回前端的第一个元素（和peek方法相同）

  peekFront() {
  	return this.items[this.items.length - 1];
  }
  复制代码

• peekBack()：返回后端的第一个元素（和Stack 类中的peek方法相同）

  peekBack() {
  	return this.items[this.items.length - 1];
  }
  复制代码

6. Deque类使用

同上

7. 解决问题

循环队列

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 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'];
const result = hotPotato(names, 10);
result.eliminated.forEach(name => {
	console.log(`${name}在击鼓传花游戏中被淘汰。`);
});
console.log(`胜利者： ${result.winner}`);
复制代码

回文

function palindromeChecker(aString) {
    if (
        aString === undefined || 
        aString === null ||
        (aString !== null && aString.length === 0)
    ) {
        return false;
    }
    const deque = new Deque();
    const lowerString = aString.toLocaleLowerCase();  //转换成小写
    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;
}
复制代码

一道LeetCode题

var RecentCounter = function() {
    this.q = [];
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
   this.q.push(t);
   while(this.q[0] < t - 3000){
       this.q.shift(); // 超出这个范围的就删除
   } 
   return this.q.length;
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */
复制代码