作者：whisper

链接：http://proprogrammar.com:443/article/594

声明：请尊重原作者的劳动，如需转载请注明出处

    本章节中，我们将介绍另一种处理顺序后入先出（LIFO），以及相应的数据结构，栈。

    完成本章节后，你将：

1. 理解 LIFO 和 栈的定义；
2. 能够用动态数组实现栈；
3. 熟悉内置栈结构；
4. 能够使用栈解决问题。

    后入先出的数据结构

    在 LIFO 数据结构中，将首先处理添加到队列中的最新元素。

    与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。

    示例 - 栈

    1. 入栈：你可以单击下面的 Push 按钮查看如何将新元素 6 添加到栈中。

    2. 退栈：你可以单击下面的 Pop 按钮查看当你从栈中弹出一个元素时将移除哪个元素。

    实现 - 栈

    栈的实现比队列容易。动态数组足以实现堆栈结构。这里我们提供了一个简单的实现供你参考：

// "static void main" must be defined in a public class.
class MyStack {
    private List<Integer> data;               // store elements
    public MyStack() {
        data = new ArrayList<>();
    }
    /** Insert an element into the stack. */
    public void push(int x) {
        data.add(x);
    }
    /** Checks whether the queue is empty or not. */
    public boolean isEmpty() {
        return data.isEmpty();
    }
    /** Get the top item from the queue. */
    public int top() {
        return data.get(data.size() - 1);
    }
    /** Delete an element from the queue. Return true if the operation is successful. */
    public boolean pop() {
        if (isEmpty()) {
            return false;
        }
        data.remove(data.size() - 1);
        return true;
    }
};

public class Main {
    public static void main(String[] args) {
        MyStack s = new MyStack();
        s.push(1);
        s.push(2);
        s.push(3);
        for (int i = 0; i < 4; ++i) {
            if (!s.isEmpty()) {
                System.out.println(s.top());
            }
            System.out.println(s.pop());
        }
    }
}

    栈 - 用法

    大多数流行的语言都提供了内置的栈库，因此你不必重新发明轮子。除了初始化，我们还需要知道如何使用两个最重要的操作：入栈和退栈。除此之外，你应该能够从栈中获得顶部元素。下面是一些供你参考的代码示例：

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // 1. Initialize a stack.
        Stack<Integer> s = new Stack<>();
        // 2. Push new element.
        s.push(5);
        s.push(13);
        s.push(8);
        s.push(6);
        // 3. Check if stack is empty.
        if (s.empty() == true) {
            System.out.println("Stack is empty!");
            return;
        }
        // 4. Pop an element.
        s.pop();
        // 5. Get the top element.
        System.out.println("The top element is: " + s.peek());
        // 6. Get the size of the stack.
        System.out.println("The size is: " + s.size());
    }
}

    从现在开始，我们可以使用内置的栈库来更方便地解决问题。 让我们从一个有趣的问题（最小栈）开始，帮助你复习有用的操作。 然后我们将看一些经典的栈问题。 当你想首先处理最后一个元素时，栈将是最合适的数据结构。

    算法-最小栈

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

• push(x) -- 将元素 x 推入栈中。
• pop() -- 删除栈顶的元素。
• top() -- 获取栈顶元素。
• getMin() -- 检索栈中的最小元素。

示例:

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

class MinStack {
    private final int MAXSIZE = 1000;
    private int[] data;
    private int length;
    private int min;
    
    /** initialize your data structure here. */
    public MinStack() {
        data  = new int[MAXSIZE];
        length = 0;
        min = Integer.MAX_VALUE;
    }
    
    public void push(int x) {
        if(length < MAXSIZE){
            data[length++] = x;
            if(x < min){
                min = x;
            }
        }
    }
    
    public void pop() {
        if(length > 0){ 
            int val = top();
            if(val == min){
                min = Integer.MAX_VALUE;
                if(length > 1){
                    for(int i = 0; i < length - 1; i++){
                        if(data[i] < min){
                            min = data[i];
                        }
                    }
                 }
            }
            length--;
        }
    }
    
    public int top() {
        if(length > 0){
            return data[length - 1];
        }
        
        return 0;
    }
    
    public int getMin() {
        return min;
    }
}

    与一般的栈不同的是可以获取最小元素，数组data放数据，length指示元素数量，min指示最小值，MAXSIZE是最大元素数量，定义的变量较多，多的好处是效率高些，多消耗一些空间，带来一些时间上的提升。

    再看另一种实现

//第二个方法，运用更改单链表的方法,在节点中加了一个属性  当前最小值min。
class MinStack {
    Node head;
    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int x) {
        if(head==null){
           head = new Node(x,x);
        }else{
            int m;
            m = x<head.min?x:head.min;
            Node n = new Node(x,m);
            n.next = head;
            head = n;
        }
    }
    
    public void pop() {
        if(head!=null){
            head = head.next;
        }
    }
    
    public int top() {
        return head.value;
    }
    
    public int getMin() {
        return head.min;
    }
}
class Node{
    int value;
    int min;
    Node next;//后继节点
    public Node(int value,int min){
        this.value = value;
        this.min=min;
        next=null;
    }

}

    这里使用链表实现，结点中的min表征从头结点到当前结点中的最小值，而不用像上面的方法循环查找最小值，提高了效率

    算法-有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

class Solution {
    // 想法：数据结构基本题，遇左括号入栈，遇右括号出栈，看是否匹配，字符串结束时栈要为空
    public boolean isValid(String s) {
        if(s.length() == 0){
            return true;
        }
        
        char[] arr = s.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        char temp;
        
        for(char c: arr){
            if(c == '}' || c == ']' || c == ')'){
                if(stack.isEmpty()){
                    return false;
                }else{
                    temp = stack.pop();
                    if(temp + 1 != c && temp + 2 != c){
                        return false;
                    }
                }
            }else{
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
}

    括号匹配常会用到栈，解释在代码注释里

    下面看一个效率更高的算法

class Solution {
    public boolean isValid(String s) {
        char [] t = new char [s.length()+1];
        int p = 1;
        for(char c:s.toCharArray())
        {
            if(c == '(' || c == '[' || c == '{')
                t[p++] = c;
            else
            {
                --p;
                if(
                    (c == ')' && t[p] != '(')
                    ||
                    (c == ']' && t[p] != '[')
                    ||
                    (c == '}' && t[p] != '{')
                )
                    return false;
            }
        }
        return p == 1;
    }
}

    提高效率的方法是自己用数组实现栈

算法-每日温度

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

class Solution {
    // 想法：找到后面比它大的，记录距离，没有记0
    public int[] dailyTemperatures(int[] T) {
        int j, sum;
        int[] result = new int[T.length];
        
        continueLoop:
        for(int i = 0; i < T.length - 1; i++){
            sum = 1;
            j = i + 1;
            while(j < T.length){
                if(T[i] >= T[j]){
                    sum++;
                }else{
                    result[i] = sum;
                    continue continueLoop;
                }
                
                j++;
            }
            
            result[i] = 0;
        }
        
        return result;
    }
}

     简单的使用二重循环来做的，下面看一种效率更高的做法

*用栈的常规做法
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] res= new int[len];
        Stack<Integer> stack = new Stack<>();
        for(int i=len-1;i>=0;i--)
        {   while(!stack.isEmpty() && T[stack.peek()]<=T[i])
            {   stack.pop();}
            if(stack.isEmpty()){ res[i]=0;}
            else{  res[i]= stack.peek()-i;}
            stack.push(i); 
        }
        return res;
    }
}

    这里使用了栈，数组从后向前的顺序入栈，对数组中第i个元素，栈中的元素是在i之后比第i个元素大且依次增大的

    再看一种解法

class Solution {//类dp做法
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] res= new int[len];
        int max_til_now = T[len-1];//最高温

        for(int i=len-2;i>=0;i--)//倒数第二天开始 最后一天必定是0
        {   if(T[i]<T[i+1]){res[i]=1;}//小于后一天 那就是1
            else//大于前一天 就看看前一天的将来升温时刻
            {   if(T[i]>=max_til_now){  res[i]=0; max_til_now=T[i];}//高于最高温直接结束
                else
                {   int pre = i+1;//往前循环找前一天的升温时刻 往前跳转
                    while( T[ pre+res[pre]] <= T[i] )
                    {    pre =  pre+res[pre];}//前一天的 升温时刻那天的 升温时刻
                    res[i] = pre+res[pre]-i;
                }
            }
            
        }
        return res;
    }
}

    这里主要的思想是利用已有的部分结果，如果当前cur比后一个next高，那么要找比后一个更高的气温日期，哪个比后一个高呢，next后第res[next]是求得的比next高的，那天的气温是T[next+res[next]]，T[cur]与T[next+res[next]]比较，不满足的化T[cur]与比next+res[next]高的那天比较，重复此过程（这中间考虑最高温的情况，如果不比最高温低，直接为0）

    算法-逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9

示例 2：

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

示例 3：

输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

class Solution {
    // 数据结构基本题：遇数入栈，遇操作符出栈，计算结果入栈
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        List<String> op = Arrays.asList("+", "-", "*", "/");
        int num1, num2;
        
        for(String token: tokens){
            if(op.contains(token)){
                num2 = stack.pop();
                num1 = stack.pop();
                
                if("+".equals(token)){
                    stack.push(num1 + num2);
                }else if("-".equals(token)){
                    stack.push(num1 - num2);
                }else if("*".equals(token)){
                    stack.push(num1 * num2);
                }else{
                    stack.push(num1 / num2);
                }
            }else{
                stack.push(Integer.parseInt(token));
            }
        }
        
        return stack.pop();
    }
}

    栈的基本题，遇操作数入栈，遇操作符出栈两个操作数，计算，结果入栈，可以自己实现栈以提高效率，就不多说了

亲爱的读者：有时间可以点赞评论一下