1.【算法训练营】 - 2、栈、队列、优先队列、双端队列 - 《技术》

栈 Stack
队列 Queue
双端队列 Deque(Double-End Queue)
- Stack、Queue、Deque 工程实现
优先队列（Priority Queue）
总结
预习题目
实战题目
课后作业

04 极客大学-算法训练营-覃超-第四课.pdf

栈 Stack

先入后出
添加、删除：O（1）
查询O（n）

最近相关性

队列 Queue

先进先出
添加、删除：O（1）
查询O（n）

先来后到

双端队列 Deque(Double-End Queue)

添加、删除：O（1）
查询O（n）

Stack、Queue、Deque 工程实现

优先队列（Priority Queue）

插入O（1）
取出O（logN）：按照元素的优先级取出
底层具体实现的数据结构较为复杂多样 heap、bst、treap

总结

2、栈、队列、优先队列、双端队列 - 图1

预习题目

有效的括号（亚马逊、JPMorgan 在半年内面试常考）

// 0、如果字符串是奇数，则肯定不合法
// 1、用map 以key:val的形式存储括号队
// 2、遍历字符串，将左侧括号存入栈中
// 3、匹配到右括号时，判断是否和栈里最后一个左括号匹配，匹配则pop出去，否则返回false
var isValid = function (s) {
if (s % 2) {
  return false;
}
let map = new Map([
  ["}", "{"],
  [")", "("],
  ["]", "["],
]);
let stack = [];
for (let i = 0; i < s.length; i++) {
  // 如果匹配到右括号, 去栈匹配是否有对应的右括号
  if (map.has(s[i])) {
    // 取栈头部元素，看是否匹配
    if (!stack.length || map.get(s[i]) !== stack[stack.length - 1]) {
      return false;
    }
    stack.pop();
  } else {
    // 如果匹配到左括号，入栈
    stack.push(s[i]);
  }
}
return !stack.length;
};

最小栈（亚马逊在半年内面试常考） ```javascript var MinStack = function() { this.x_stack = []; // 用数组模拟栈结构 this.min_stack = [Infinity]; // 维护一个最小栈 };

MinStack.prototype.push = function(x) { this.x_stack.push(x); // 每入一个新元素，都向最小栈中推入一个新元素和当前最小值中小的那个 this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x)); };

MinStack.prototype.pop = function() { this.x_stack.pop(); this.min_stack.pop(); // 每次pop一个元素 };

MinStack.prototype.top = function() { return this.x_stack[this.x_stack.length - 1]; };

MinStack.prototype.getMin = function() { return this.min_stack[this.min_stack.length - 1]; }; ```

实战题目

柱状图中最大的矩形（亚马逊、微软、字节跳动在半年内面试中考过）
滑动窗口最大值（亚马逊在半年内面试常考）

课后作业
用 add first 或 add last 这套新的 API 改写 Deque 的代码
分析 Queue 和 Priority Queue 的源码
设计循环双端队列（Facebook 在 1 年内面试中考过）
接雨水（亚马逊、字节跳动、高盛集团、Facebook 在半年内面试常考）

2、栈、队列、优先队列、双端队列