概念解释

栈 stack，相当于一个开放的容器。先存储的元素位于栈底位置，后存储的元素位于栈顶位置。因此栈内存放的数据，先进入的数据后出栈，后存入的数据先出栈，在同一端进行插入和删除操作，遵循先进后出，后进先出原则（LIFO：Last In First Out）。
存入数据：进栈、压栈 push
取出数据：出栈、弹栈 pop
【示例】一
比如我们生活中经常用到的浏览器的返回与前进，就类似栈结构的先进后出：我们依次搜索leetcode、羽毛球筒、渡一、算法，它们会依次存放在一个开放容器中，当我们点击返回时会倒序弹出。
【栈·生活示例】.jpg
【示例】二
比如我们程序中一个方法调用另一个方法，需要等待后者执行结束的返回结果去做下一步的处理，这样的逻辑实现也是借助于栈结构。当我们调用方法一时，是把方法一压入了栈中；当方法一中调用了方法二时，又重新把方法二压入栈中，方法二执行结束后会弹出，继续执行方法一。可见，栈具有可记忆的特性。
function test1(){
int result = functionTest2();
result++;
…..
}

相关算法

一、有效的括号

【描述】给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

解法①：键值对存入匹配情况

【分析】通过栈来记录出现的字符，如果是右括号，匹配栈顶元素能否匹配，能匹配上就抵消，匹配不上就无效。如果是左括号，直接将左括号压入栈中。当遍历完成之后如果剩余一个空栈，说明所有的括号都已经匹配上了，如果有剩余的括号，说明有左括号没有被匹配上。

 public static boolean isValid(String s){
        HashMap<Character, Character> map = new HashMap<>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
        Stack<Character> stack = new Stack<>();
        char[] arr = s.toCharArray();
        for (char c : arr) {
            if (map.containsKey(c)){
                stack.push(c);
            }else {
                if (stack.isEmpty()){
                    System.out.println("右括号出现，但是左括号尚未出现");
                    return false;
                }
                Character top = stack.peek();
                if (!map.get(top).equals(c)){
                    System.out.println("右括号出现，但是没有与之匹配的左括号");
                    return false;
                }
                stack.pop();
            }
        }
        if (!stack.empty()){
            System.out.println("左括号出现，但没有右括号与之抵消");
            return false;
        }
        return true;
    }

解法②：栈存入抵消情况

【分析】：判断是否为左括号，是的话直接压栈右括号。如果为右括号，直接取栈顶元素匹配

  public static boolean isValid1(String s){
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if ('(' == c){
                stack.push(')');
            }else if ('[' == c){
                stack.push(']');
            }else if ('{' == c){
                stack.push('}');
            }else if (stack.empty() || c != stack.pop()){
                return false;
            }
        }
        return stack.empty();
    }

二、栈的多种实现方式

按照实际存储数据方式不同，栈可以分为顺序栈和链栈，分别用数组和链表存储数据。

方式①：基于数组的实现（顺序栈）

public class MyStack {
    //盛放数据的数组
    int[] array;
    //栈的最大容量
    int maxSize;
    //栈顶元素的下标,即实际存储大小
    int top;
    public MyStack(int size){
        maxSize = size;
        array = new int[size];
        top = -1;
    }
    public void push(int value){
        if (top < maxSize - 1){
            top++;
            array[top] = value;
        }
    }
    public int pop(){
        int result = array[top];
        top--;
        return result;
    }
    public int peek(){
        return array[top];
    }
    public boolean isEmpty(){
        return top == -1;
    }
    public boolean isFull(){
        return top == (maxSize -1);
    }
}

方式②：基于队列的实现

通过队列的方式实现栈结构：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-stack-using-queues

解法①：使用临时队列

【分析】
队列是先进先出，栈是先进后出。思路为使用临时的额外队列存储队列内元素，直到遍历到队尾元素输出。操作之后再将临时队列里的元素放回队列中，依此循环。

public class MyStackByQueue {
    //存储数据的队列
    Queue<Integer> dataQueue = new LinkedList<>();
    //临时队列
    Queue<Integer> tmpQueue = new LinkedList<>();
    //栈顶元素
    int top;
    public void push(int x){
        dataQueue.add(x);
        top = x;
    }
    public int pop(){
        while (dataQueue.size() > 1){
            top = dataQueue.poll();
            tmpQueue.add(top);
        }
        Integer num = dataQueue.poll();
        Queue<Integer> tmp = dataQueue;
        dataQueue = tmpQueue;
        tmpQueue = tmp;
        return num;
    }
    public int top(){
        return top;
    }
    public boolean isEmpty(){
        return dataQueue.size() == 0;
    }
}

解法②：对换队首队尾元素顺序

【分析】不使用额外的临时队列，每次存入数据后都对换队首队尾元素顺序，保证每次取出数据符合栈结构的取出顺序。

public class MyStackByQueue2 {
    Queue<Integer> queue = new LinkedList<>();
    public void push(int x){
        int size = queue.size();
        queue.add(x);
        while (size > 1){
            Integer tail = queue.poll();
            queue.offer(tail);
            size--;
        }
    }
    public int pop(){
        return queue.poll();
    }
    public int top(){
        return queue.peek();
    }
    public boolean isEmpty(){
        return queue.isEmpty();
    }
}

三、栈中值最小的元素

解法①：使用额外栈

【分析】：使用额外的栈记录栈中出现的最小元素，每次push新元素时，拿出临时栈栈顶元素进行对比，如果新元素大于临时栈顶元素，将最小元素重新push进临时栈一次，如果小于临时栈栈顶元素，就将该新元素push进临时栈。
【描述】:
输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); —> 返回 -3.
minStack.pop();
minStack.top(); —> 返回 0.
minStack.getMin(); —> 返回 -2.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack

public class MinStack {
    //数据栈
    Stack<Integer> dataStack = new Stack<>();
    //存储最小值的额外栈
    Stack<Integer> minStack = new Stack<>();
    public MinStack(){
    }
    public void push(int x){
        dataStack.push(x);
        if (!minStack.isEmpty() && minStack.peek() < x){
            minStack.push(minStack.peek());
        }else {
            minStack.push(x);
        }
    }
    public void pop(){
        dataStack.pop();
        minStack.pop();
    }
    public int top(){
       return dataStack.peek();
    }
    public int getMin(){
        return minStack.peek();
    }
}

解法②：在同一栈中重复记录

public class MinStack1 {

    Stack<Integer> dataStack = new Stack<>();
    int min = Integer.MAX_VALUE;

    public void push(int x){
        //如果新存入的元素使最小值发生了变化，则存入两个元素（原来的最小值和新值）
        if (min >= x){
            //如果栈为空，说明是第一个元素，此时一定min > x
            if (!dataStack.isEmpty()){
                dataStack.push(min);
            }
            //最小值重新赋值
            min = x;
        }
        dataStack.push(x);
    }

    public void pop(){
        if (dataStack.isEmpty()) {return;}
        if (dataStack.size() == 1){
            min = Integer.MAX_VALUE;
        }else if (min == dataStack.peek()){
            dataStack.pop();
            min = dataStack.peek();
        }
        dataStack.pop();
    }

    public int top(){
        return dataStack.peek();
    }

    public int getMin(){
        return min;
    }
}

四、下一个最大值

【描述】：
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个比 x 大的元素。
给你两个没有重复元素的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的下一个更大元素。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的下一个更大元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-greater-element-i
【示例】：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

解法：
【分析】暂时忽略nums1，直接求取nums2中每一个元素的下一个最大值
```
public static int[] nextGreaterNum(int[] nums1, int[] nums2){
      //临时栈
      Stack<Integer> stack = new Stack<>();
      HashMap<Integer, Integer> map = new HashMap<>();

      for (int i = 0; i < nums2.length; i++) {
          while ( !stack.isEmpty() && stack.peek() < nums2[i]){
              map.put(stack.pop(),nums2[i]);
          }
          stack.push(nums2[i]);
      }
      while (!stack.isEmpty()){
          map.put(stack.pop(),-1);
      }
      int[] result = new int[nums1.length];
      for (int i = 0; i < nums1.length; i++) {
          result[i] = map.get(nums1[i]);
      }
      return result;
  }
```
五、经典应用之逆波兰表达式

类型一、后缀
【描述】
根据逆波兰表示法，求表达式的值。
有效的算符包括 +、-、、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = [“2”,”1”,”+”,”3”,”“]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：
输入：tokens = [“4”,”13”,”5”,”/“,”+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
【分析】
逆波兰表达式是自带优先级的，出现数字就存入栈中，出现运算符就取出栈中的两个数值进行运算符对应的运算，并将运算结果再次入栈。
[“2”,”1”,”+”,”3”,”“]
stack[2,1] -> +
stack[3]
stack[3,3] ->
stack[9]
【代码实现】:

public class ReversePolishNotation {

    public static void main(String[] args) {
        String[] tokens = {"2","3","+","5","*"};
        System.out.println(evalRPN(tokens));
    }

    public static int evalRPN(String[] tokens){
        Stack<String> stack = new Stack<String>();
        int nums1,nums2;
        for (int i = 0; i < tokens.length; i++) {
            switch (tokens[i]){
                case "+":
                    nums1 = Integer.parseInt(stack.pop());
                    nums2 = Integer.parseInt(stack.pop());
                    stack.push(nums2 + nums1 + "");
                    break;
                case "-":
                    nums1 = Integer.parseInt(stack.pop());
                    nums2 = Integer.parseInt(stack.pop());
                    stack.push(nums2 - nums1 + "");
                    break;
                case "*":
                    nums1 = Integer.parseInt(stack.pop());
                    nums2 = Integer.parseInt(stack.pop());
                    stack.push(nums2 * nums1 + "");
                    break;
                case "/":
                    nums1 = Integer.parseInt(stack.pop());
                    nums2 = Integer.parseInt(stack.pop());
                    stack.push(nums2 / nums1 + "");
                    break;
                default:stack.push(tokens[i]);

            }

        }

        return Integer.parseInt(stack.pop());
    }
}

类型二：中缀表达式

声明两个栈结构S1，和S2分别存入

数据结构与算法

栈结构相关概念及算法