经典算法之队列

队列

队列是一种数据结构，它遵循先进先出（FIFO）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。我们利用LeetCode的题目来看下队列在算法中的应用：

最近请求次数

这道题题目如下：

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，
并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数
保证 每次对 ping 的调用都使用比之前更大的 t 值。

示例：

输入：
inputs = ["RecentCounter", "ping", "ping", "ping", "ping"]
inputs = [[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

这道题其实不难，但是说实话我一开始也没看明白，这道题属于阅读理解题：看代码就能理解：

var RecentCounter = function() {
  this.q = [];    // 初始化队列
};

RecentCounter.prototype.ping = function(t) {
  this.q.push(t);   // 每次进来都放入队列
  while(this.q[0] < t - 3000){    // 遍历队列，如果值小于这次进来的值减去3000就移除出队列
    this.q.shift();
  }
  return this.q.length;   // 返回队列的长度
};

这道题没啥难度，能理解问题就行，但是这道题是最典型的队列问题，用来入门是相当好的。

字符串中的第一个唯一字符

题目如下：

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

 
示例：

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2
 

提示：你可以假定该字符串只包含小写字母。

这道题是LeetCode的一道很经典的题目，这道题有很多解法，这边我们了解两种解法就可以了，首先是哈希算法，不了解哈希算法可以看这里 (opens new window)，我以前写过哈希算法的文章。哈希版本：

var firstUniqChar = function(s) {
  let map = new Map();    // 声明一个Map
  let traget;
  // 首先把每个字符串的字符遍历，如果Map不存在就set，存在就+1
  for(let i = 0; i < s.length; i++) {
    if(map.has(s[i])){
      map.set(s[i], map.get(s[i])+1);
    }
    else{
      map.set(s[i], 1);
    }
  }
  // 遍历Map，只要找到了只存在过一次的字符立马返回它在字符串中的索引
  for (let [key, value] of map.entries()) {
    if(value === 1) {
      traget = key;
      return s.indexOf(traget);
    }
  }

  return -1
};

这个版本比较简单，而且很好看懂，所以大部分情况下都是用这个算法版本，接下来就是队列的版本：

var firstUniqChar = function(s) {
  const position = new Map();   // 声明Map结构
  const q = [];   // 声明一个队列
  // for...of循环字符串，如果Map中不存在这个字符，那么Map中set这个值和队列push进去一个数组。
  for (let [i, ch] of Array.from(s).entries()) {
    if (!position.has(ch)) {
      position.set(ch, i);
      // 队列是个二维数组，存的值是第一个值是字符，第二个值是这个字符在字符串中的索引的数组。
      q.push([s[i], i]);    
    } else {
      // 如果Map存在，证明这个字符重复了，那么Map中此值变为-1
      position.set(ch, -1);
      // 这里做了一个队列的优化处理，只要队列不是空的且第一个值不是-1（不是重复的）那么就不处理
      while (q.length && position.get(q[0][0]) === -1) {
        q.shift();    // 如果第一个是重复了的就在队列中移除掉
      }
    }
  }
  return q.length ? q[0][1] : -1;   // 如果队列不是空的，返回队列第一个的值的第二个值（即是索引）
};

这个版本相对于上面一个版本比较复杂，利用了队列，很多人难理解的应该是二维数组和为什么要while处理，二维数组自己在纸上手动代入值一下就知道了。while处理其实是队列的一个“延迟删除”技巧，因为题目要求是字符串中的第一个唯一字符，而我们是按顺序遍历的，所以只要不是队首的字符重复了，那么就不用去管。

队列的最大值

这道题在LeetCode中给出了中等：

请定义一个队列并实现函数 max_value 得到队列里的最大值，
要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

这道题有两种解法，第一种是暴力算法（BF）来处理队列： 算法代码如下：

var MaxQueue = function() {
    this.q = [];    // 声明一个队列
    this.bengin = 0;    // 队列的队头指针
    this.end = 0;   // 队列的队尾指针
};

MaxQueue.prototype.max_value = function() {
    let anx = -1;
    // 暴力遍历每个值，遍历出最大的返回
    for(let i = this.bengin; i < this.end; i++){
        anx = Math.max(anx,this.q[i])
    }
    return anx;
};

MaxQueue.prototype.push_back = function(value) {
    this.q[this.end++] = value;    // 队尾指针增加，并且入队
};

MaxQueue.prototype.pop_front = function() {
    if(this.bengin === this.end){
        return -1;
    }
    return this.q[this.bengin++];   //  队头指针增加
}

第二种解法则是利用双端队列和单调递减来解决：

var MaxQueue = function() {
    this.queue = [];    // 数值数组
    this.deque = [];    // 双端队列（指允许两端都可以进行入队和出队操作的队列）
};

MaxQueue.prototype.max_value = function() {
    return this.queue.length ? this.deque[0] : -1   // 双端队列第一个就是最大值
};

MaxQueue.prototype.push_back = function(value) {
  // 先放入数值数组里面
    this.queue.push(value);
    
    while(this.deque.length && this.deque[this.deque.length - 1] < value){
      // 只要队列不是空的且队尾的值小于传入的值，那么就把队尾出队，
      // 这样就能保证队头永远都是最大的值,而且队列是单调递减的。
        this.deque.pop();
    }
    this.deque.push(value);   // 把值入队到队尾
};

MaxQueue.prototype.pop_front = function() {
    if(this.queue.length === 0) return -1;
    const val = this.queue.shift();
    // 如果值跟队列的队头的值一样的，那么就需要把它出队
    if(this.deque[0] === val) {
         this.deque.shift();
    }
    return val
}