概念

• Stack:先入后出；添加、删除皆为 O(1),查询为O(n)

• Queue: 先入先出；添加、删除皆为O(1),查询为O(n)

若题目中涉及括号问题，则很有可能和栈相关

高频题

最小栈

const MinStack = function() {
    this.stack = [];
    // 定义辅助栈
    this.stack2 = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    // 若入栈的值小于当前最小值，则推入辅助栈栈顶
    if(this.stack2.length == 0 || this.stack2[this.stack2.length-1] >= x){
        this.stack2.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    // 若出栈的值和当前最小值相等，那么辅助栈也要对栈顶元素进行出栈，确保最小值的有效性
    if(this.stack.pop() == this.stack2[this.stack2.length-1]){
        this.stack2.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length-1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    // 辅助栈的栈顶，存的就是目标中的最小值
    return this.stack2[this.stack2.length-1];
};

用栈实现队列

/**
 * 初始化构造函数
 */
const MyQueue = function () {
  // 初始化两个栈
  this.stack1 = [];
  this.stack2 = [];
};

/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
  // 直接调度数组的 push 方法
  this.stack1.push(x);
};

/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
  // 假如 stack2 为空，需要将 stack1 的元素转移进来
  if (this.stack2.length <= 0) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length !== 0) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  // 为了达到逆序的目的，我们只从 stack2 里出栈元素
  return this.stack2.pop();
};

/**
* Get the front element.
* @return {number}
* 这个方法和 pop 唯一的区别就是没有将定位到的值出栈
*/
MyQueue.prototype.peek = function () {
  if (this.stack2.length <= 0) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length != 0) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  // 缓存 stack2 的长度
  const stack2Len = this.stack2.length;
  return stack2Len && this.stack2[stack2Len - 1];
};

/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
  // 若 stack1 和 stack2 均为空，那么队列空
  return !this.stack1.length && !this.stack2.length;
};

判断有效括号(简单)

//用stack实现
const isValid= function (s){
    if(!s)return true;
    let map={
        '{':'}',
        '[':']',
        '(':')'
    }
    let stack=[];
    for(let i =0;i<s.length;i++){
        //缓存单个字符
        const ch=s[i];
        //判断是否是左括号，这里我为了实现加速，没有用数组的includes方法，手写判断逻辑
        if(ch==='{'||ch==='['||ch==='('){
            stack.push(map[ch])
        }
        //若不是左括号，且栈顶的左括号没有和当前字符匹配上，那么判为无效
        else{
            //若栈不为空，且栈顶的左括号没有和当前字符匹配上，那么判为无效
            if(!stack.length||stack.pop()!==ch){
                return false
            }
        }
    }
    return !stack.length
}

//简写
const isValid= function(s){

    let map={
        '{':'}',
        '(':')',
        '[':']'
    }
    let stack=[]
    for(let i=0;i<s.length;i++){
        if(map[s[i]]){
            stack.push(s[i])
        }else if(s[i] !== map[stack.pop()]){
            return false
        }
    }
    return stack.length === 0
}

每日温度(中等) (opens new window)

• 单调栈

const dailyTemperatures = function (array){
    const len =array.length
    const stack=[]
    const res=(new Array(len).fill(0))// 初始化结果数组。注意数组定长，占位为0
    for(let i= 0; i<len; i++){
        //若栈不为0，且存在打破递减趋势的温度值
        while(stack.length&& array[i]> array[stack[stack.length-1]]){
            //将栈顶温度值对应的索引出栈
            const top= stack.pop();
            //计算 当前栈顶温度值与第一个离于它的温度值的索引差值
            res[top]=i-top
        }
        // 注意栈里存的不是温度值，而是索引值，这是为了后面方便计算
        stack.push(i)   
    }
    //返回数组结果
    return res
}

简化路径（中等) (opens new window)

• 思路

这题看似很复杂，但是其实用栈来做还是蛮简单的，先用 / 来分割路径字符串，然后不停的把分割后的有效值 push 到栈中即可，

1. 有效值的定义是：非 '..'、'.'、'' 这些特殊值以外的值。
2. 遇到 .. 字符，说明要回退一级目录，把栈中弹出一个值即可。
3. 最后返回的字符串值要特殊处理下，如果最后是空字符的话，直接返回 '/'，否则把末尾的 '/' 给去掉后返回

const simplifyPath= function (path){
    let tokens = path.split("/")
    let stack = []

    for(let index=0; index<tokens.length;index++){
        let token =tokens[index]
        if(token === ".."){
            if(stack.length>0){
                stack.pop()
            }
        }
        else if( token !==""&& token !=="."){
            stack.push(token)
        }
    }
    let res ="/"
    for(let token of stack){
        res+= `${token}/`
    }
    if(res !== "/"){
        res= res.substr(0,res.length -1)
    }
    return res
}

删除字符串中的所有相邻重复项（简单） (opens new window)

• 栈

1. 扫描过的字符入栈暂存
2. 如果扫描的当前字符与栈顶元素相同，则将栈顶元素出栈
3. 将栈中剩余的字符转换成字符串

const removeDuplicates= function(s){
    const stack =[]
    for(const i of s){
        if(stack.length&& stack[stack.length -1]===i){
            stack.pop()
        }else{
            stack.push(i)
        }
    }
    return stack.join('')
}

删除字符串中的所有相邻重复项 II（中等） (opens new window)

• 栈

解题思想： 遍历字符串依次入栈，入栈时，判断当前元素与栈头元素是否一致，如果不一致则入栈，如果一致，判断栈头字符是否长度为 k - 1 ，如果为 k-1 ，即加入该字符时，满足连续相同字符 k 个，此时，需要栈头出栈，当前字符不进栈，如果小于 k-1 ，则取出栈头字符，加上当前字符，重新入栈

const removeDuplicates =function (s,k){
    let stack =[]
    for(let i of s){
        let prev =stack.pop()
        if(!prev || prev[0] !==i){
            stack.push(prev)
            stack.push(i)
        }else if(prev.length < k-1){
            stack.push(prev+i)
        }
    }
    return stack.join('')
}
// 时间复杂度：O(n)
// 空间复杂度：O(n)

柱状图中的最大矩形(困难) (opens new window)

• 单调递增栈

我们来思考一个问题，我们究竟想要求的最大面积是什么？

不妨拿起笔画画图，我这里帮你画好了，观察上图，便可以得出：

其实就是以 i 为中心，分别向左、向右找到第一个小于 heights[i] 的两个边界，也就是以当前这根 i 柱子所能勾勒出的最大面积。

那么，我们为什么要借助单调递增栈这种数据结构呢？

单调递增，也就是我们可以通过 O(1) 的时间复杂度确定柱体 i 的左边界！

又是以空间换时间的套路！

如何确定右边界？

只需遍历一次柱体数组，将大于等于当前柱体的柱子们推入栈中，而当遍历到的柱子高度小于栈顶的柱子高度时，这时我们找到了右边界，可以将栈顶的柱子，弹出栈，来计算矩形面积了！

处理特殊边界情况？

引入前后边界，在柱体数组前后各放入一根高度为 0 的柱子。这样便无需考虑栈空以及栈中还有剩余柱子的情况

const largestRectangleArea = function(heights) {

let maxArea=0
let stack= []
heights.push(0)
heights.unshift(0)
for(let i=0; i<heights.length;i++){
    while(stack.length>0 && heights[stack[stack.length-1]]>heights[i]){
        maxArea= Math.max(maxArea,heights[stack.pop()]*(i-stack[stack.length-1] -1))
    }
    stack.push(i)
}
return maxArea
}

滑动窗口最大值(困难) (opens new window)

• 单调队列

1. 维护一个单调递减队列，从大到小，左边是出口，右边是入口
2. 每次 pop 时需要判断当前队列是否为空，并且如果当前要弹出的数值等于队列出口元素时，队列移除出口元素
3. 每次 push 的元素如果大于入口元素，将队列后端的数值弹出，直到 push 的元素数值小于队列入口元素，保证单调性
4. max 可以获取当前队列的最大值

const maxSlidingWindow = function(nums, k) {
    const n = nums.length
    class slideWindow {
        constructor() {
            this.data = []
        }
        push(val) {
            let data = this.data
            while (data.length > 0 && data[data.length - 1] < val) {
                data.pop()
            }
            data.push(val)
        }
        pop(val) {
            let data = this.data
            if (data.length > 0 && data[0] === val) {
                data.shift()
            }
        }
        max() {
            return this.data[0]
        }
    }
    let res = []
    let windows = new slideWindow()
    for (let i = 0; i < n; i++) {
        if (i < k - 1) {
            windows.push(nums[i])
        } else {
            windows.push(nums[i])
            res.push(windows.max())
            windows.pop(nums[i - k + 1])
        }
    }
    return res
}

//时间复杂度：O(n)
//空间复杂度：O(n)