介绍

我们此处说的栈，是数据结构中的栈，而不是指系统层面的，系统层面说的栈区（ stack ），是指由编译器自动分配释放，存放函数的参数值，局部变量的值等区域。数据结构里面的栈是限定仅在表尾进行插入或者删除的线性表，所谓的表尾，其实就是我们所称的栈顶，相应的，我们可以称表头为栈底。栈的最重要的特性，是后进先出（Last in first out），也称为 LIFO 结构。

使用两个栈实现队列

解题思路

栈结构的特性是先进后出，而队列的特性是先进先出，也就是先进来的数据先出去，就像是水管一样，前面的水先流出来。

但是假如我们不想直接使用队列，想用栈实现队列，至少需求多少个栈可以实现一个队列呢？答案是两个，为什么呢？

因为栈本身是先进后出的，假设我们需要先进先出，那么势必需要另外一个堆栈保存数据。数据进入一个堆栈，出来时是逆序的，但是数据依次进入两个堆栈，出来是正序的。

有两个栈 stack1 和 stack2，如果有新的数据进入，那么我们可以直接 push 到 stack1 中。

如果需要取出数据，那么我们优先取出 stack2 的数据，如果 stack2 里面的数据是空的，那么我们需要把 stack1 全部的数据倒入 stack2，再从 stack2 取数据。

也就是放入数据永远都是放在 stack1，取出数据必须从 stack2 取。

代码实现

/**
 * Initialize your data structure here.
 */
 var MyQueue = function() {
     this.inStack=[]
     this.outStack=[]
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.inStack.push(x)
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    if(!this.outStack.length){
        this.in2out()
    }
    return this.outStack.pop()
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if(!this.outStack.length){
        this.in2out()
    }
    return this.outStack[this.outStack.length-1]
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.outStack.length===0 && this.inStack.length===0
};

MyQueue.prototype.in2out = function() {
    while(this.inStack.length){
        this.outStack.push(this.inStack.pop())
    }
};
/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

最小栈

问题描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

解题思路

最容易想到的方法是将栈中的所有元素取出，不断对比得到最小元素，然后又全部放回去栈中，但这明显不是一种好的处理方式，该算法时间复杂度为 O(n)。

如果只使用一个栈，明显是无法实现上面要求的，那我们不妨使用空间来换取时间的做法，使用两个栈，一个存储所有元素的 datas stack，另一个存储最小值 d 的 mins stack。

push 一个元素的时候，都需要 push 进 datas stack，但是 push 进入 mins stack 需要满足以下两个条件：

  • 当前的 mins stack 是空的，直接放入。
  • 当前的 mins stack 的栈顶元素大于或者等于 push 进来的值。

pop 一个元素的时候，如果栈为空则什么都不操作，如果栈不为空，则判断 datas stack 的第一个元素是否和 mins 的第一个元素相等。

  • 若相等，就需要将 mins stack 和 datas stack 中的第一个元素都 pop 出去。
  • 若不相等，则只需要将 datas stack 的第一个元素 pop 出去。
/**
 * initialize your data structure here.
 */
 var MinStack = function() {
     this.stack=[]
     //辅助栈
     this.stack2=[]
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.stack.push(val)
    if(this.stack2.length == 0 || this.stack2[this.stack2.length-1]>=val){
        this.stack2.push(val)
    }
};

/**
 * @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]
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

括号匹配

问题描述

输入一串只包含 “(“ “)” “[” “]” “{” “}“ 的字符串，如何判断这里面的括号是否匹配完整，比如：“[()]{}{[()()] ()}” 程序应该输出 true，对于 [(]) 则输出 false。

解题思路

由于栈天然具有先进后出的特性，那么我们按照每个字符来读取字符串，针对每一个字符，如果是左括号（ ( 或者 [ 或者 { ），那么就压入堆栈中。如果是右括号，就弹出堆栈的栈顶第一个元素，进行匹配，( 和 )，{ 和 }，[ 和 ]，如果不匹配，则说明括号不匹配，返回 false，否则说明括号匹配，接着执行下一个字符。

代码实现

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  const len = s.length;
  if (len % 2 === 1) {
    return false;
  }
  const paris = new Map([
    [")", "("],
    ["]", "["],
    ["}", "{"],
  ]);
  const stk = [];
  for (let ch of s) {
    if (paris.has(ch)) {
      if (!stk.length || stk[stk.length - 1] !== paris.get(ch)) {
        return false;
      }
      stk.pop();
    } else {
      stk.push(ch);
    }
  }
  return !stk.length;
};

逆波兰表达式

问题描述

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家 J・卢卡西维兹（J・ Lukasiewicz）于 1929 年首先提出的一种表达式的表示方法。后来，人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面，把算符写在后面。

我们平时使用的是一种中缀表达式，比如 1 + (2 * 3) - 4，而逆波兰表达式可以表达成为 (( 1 ( 2 3 * ) + ) 4 - )。

那么如果我们给定一个数组，数组的元素是逆波兰表达式的顺序，可能是 +、 -、 *、 /，也可能是数值，该如何计算出该表达式的数值呢？（除法保留整数部分即可，不包含括号）

解题思路

例如：[ "4", "14", "7", "/", "+"]，输出为：4 +（14 / 7）= 6。

其实从上面来看，符号总是在两个数值后面出现，也就是当我们发现操作符号时，前面肯定有需要的两个数值。计算出来的数值同样作为操作数，与前面的数值进行计算。那么针对这种情况，我们可以直接借助堆栈，针对里面的每一个元素：

  • 如果是操作数，则将操作数压入栈中。
  • 如果是运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

直到整个逆波兰表达式遍历完成，堆栈里面只有一个元素，该元素就是为逆波兰表达式的值。

代码实现

/**
 * @param {string[]} tokens
 * @return {number}
 */
 var evalRPN = function(tokens) {
    let stack=[]
    for(token of tokens){
        if(token === "+" ||token==="-"||token==="*"|| token==="/"){
            let y=stack.pop()
            let x=stack.pop()
            let z=calc(x,y,token)
            stack.push(z)
        }else{
            stack.push(parseInt(token))
        }
    }
    return stack[0]
};
var calc=function(x,y,op){
    if(op==="+") return x+y
    if(op==="-") return x-y
    if(op==="*") return x*y
    if(op==="/") return parseInt(x / y, 10);
    return 0
}

每日温度

问题描述

小明暑假去一个气象站当志愿者，每天都要负责测量山上的气温，爬山可是个体力活。众所周知，温度变化也是监测的一个重要的点，因此除了每天测量出气温之外，小明还得负责数据统计，其中有一项，要根据一段时间内的气温，输出还要等多久，气温才会比今天高的天数。

比如给定一个列表 temperatures = [63, 54, 76, 56, 37, 89, 23, 74]，输出应该是 [2, 1, 3, 2, 1, 0, 1, 0]。

求解思路

这个题目的求解，其实我们可以借助栈来求解，但是这个栈有点特殊，名为单调栈。栈里面存储的不是温度本身，而是索引下标，但是要求从栈顶到栈底的元素（索引）对应数组中的温度依次递增，也就是栈顶的元素作为索引的温度，必须是最低的。

具体的操作如下：

遍历温度列表，对于温度数组里面的每一个元素 t[i]。

  • 如果栈为空，那么直接将 i 压入栈中。
  • 如果栈不为空，比较栈顶元素（假设为curIndex）对应的温度t[curIndex]和当前温度t[i]的大小：
    • 如果 t[i]>t[curIndex]，curIndex 从堆栈中弹出，并将 curIndex 对应的等待天数 res[curIndex] 赋值为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。
    • 如果 t[i]<=t[curIndex]，不做任何操作。

代码实现

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
 var dailyTemperatures = function(temperatures) {
     const len=temperatures.length
     const stack=[]
     const res=(new Array(len)).fill(0)
     for(let i=0;i<len;i++){
         while(stack.length && temperatures[i]>temperatures[stack[stack.length-1]]){
             const top=stack.pop()
             res[top]=i-top
         }
         stack.push(i)
     }
     return res
};

退格字符处理

问题描述

我们平时在电脑上输入，很容易就输入了，并且删除也很简单，但是假设现在有个电脑的删除键坏掉了，我们只能使用 # 来代替退格，那么输入两个包含 # 的字符串，如何判断两个字符串是不是一样呢？

譬如 AB###CAD#，最终字符应该是 CA，只要借助堆栈结构，读取每一个字符。如果不是 #，就选择压入栈中，如果是 #，就看堆栈是不是为空，如果不为空，就弹出一个元素，相当于删除。处理完之后，堆栈里面剩下的元素，就是处理完退格键之后的元素。

代码实现

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function (s, t) {
  const build = (str) => {
    let res = [];
    for (let a of str) {
      // 如果为退格键就出栈，否则就入栈
      a == "#" ? res.pop():res.push(a)
    }
    return res.join("");
  };
  // 比较经过处理后的俩字符串 s 及 t 是否相同
  return build(s) == build(t);
};