栈是一个操作受限的线性表,它只涉及表的一端的操作,而且满足了先进后出的性质。

这个数据结构可以想象成一叠盘子?一层一层地放着,然后你拿一只,只能从顶上拿,然后放一个新的盘子,只能放在顶上,把这个抽象一下就是栈了。

它可以使用数组实现栈,只需一个指向栈顶的指针即可,这种栈叫做顺序栈;也可以使用链表实现栈,这种栈叫做链式栈

它的实现并不难,具体可以参考Java中的ArrayDeque。

它的实战应用例子有:函数调用栈、符号匹配校验、计算器等等。在文章中,他还说到网页的前进后退,原来那个也是栈,没想到啊。

中缀转后缀

为了实现一个有+-*/()的计算器,需要先把表达式转换成后缀表达式,让计算机更好地对式子进行计算。

(要做这个,就要知道为什么计算机能更好地计算后缀表达式,而不是中缀,并且要对它的过程了解透彻)

例子:把49*(45+23453-12)/4+56转换为后缀表达式49#45#23453#+*12#-4#/56#+

思路:

遍历中缀表达式,使用StringBuilder sb临时保存后缀表达式

  1. 若是数字,检测多位数,加入结果集中

  2. 若是左括号,入栈

  3. 若是右括号,把除左括号外的栈中其它运算符出栈,加入结果集中

  4. 若是加号或减号,把栈中优化级大于等于它的元素出栈(即全部),加入结果集中。

    出栈的是+或-,说明运算符优先级相同,则从左到右运算;

    出栈的是*或/,它们的优先级更高,应该先运算。

  5. 若是乘号或除号,把栈中优先级大于等于它的元素出栈(即乘除),加入结果集中。

    出栈的是*或/,说明运算符优先级相同,则从左到右运算;

/**
 * 中缀转后缀
 */
private void trans() {
    Deque<Character> stack = new ArrayDeque<>();
    int i = 0;
    char ch;
    char top;
    StringBuilder sb = new StringBuilder();
    while (i < exp.length()) {
        ch = exp.charAt(i);
        if (ch == '(') {
            stack.push(ch);
        } else if (ch == ')') {
            while (!stack.isEmpty() && (top = stack.pop()) != '(') {
                sb.append(top);
            }
        } else if (ch == '+' || ch == '-') {
            // 把该符号之前的所有符号出栈
            // 因为是从左到右运算
            while (!stack.isEmpty() && (top = stack.pop()) != '(') {
                sb.append(top);
            }
            stack.push(ch);
        } else if (ch == '*' || ch == '/') {
            // 之前有乘除,才先算它们,否则进栈(同从左到右运算)
            while (!stack.isEmpty() && (top = stack.peek()) != '('
                    && (top == '*' || top == '/')) {
                sb.append(stack.pop());
            }
            stack.push(ch);
        } else {
            // 计算数字(感觉代码有点丑,不知道怎么优化)
            while (ch >= '0' && ch <= '9') {
                sb.append(ch);
                if (++i < exp.length()){
                    ch = exp.charAt(i);
                }else{
                    break;
                }
            }
            i--;
            // 分隔每个数字
            sb.append("#");
        }
        i++;
    }
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    postExp = sb.toString();
}

leetcode上关于栈的题目大家可以先做20,155,232,844,224,682,496.

20. 有效的括号

比较常见的栈的应用,栈的特性是先进后出,如果一组完全匹配的符号,如果在它的中间划条线,那么线的左右两边应该是一样的。

因此,对于“左符号”,直接入栈;对于“右符号”,判断一下栈中元素是否与它匹配,如果不匹配,则说明这组符号乱了。依此类推,继续判断。

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '[' || c == '{'){
            stack.push(c);
        }else if (c == ')'){
            if (stack.isEmpty() || stack.pop() != '('){
                return false;
            }
        }else if (c == ']'){
            if (stack.isEmpty() || stack.pop() != '['){
                return false;
            }
        }else if (c == '}'){
            if (stack.isEmpty() || stack.pop() != '{'){
                return false;
            }
        }
    }
    return stack.isEmpty();
}

155. 最小栈

双栈解决

在O(1)的时间复杂度中找到栈中最小的元素。

可以使用两个栈进行操作,一个栈正常放元素,另一个栈放到当前元素为止最小的元素(就是根据入栈的元素来更新)。

取最小栈中元素,直接在最小栈中找即可。

class MinStack { 
    Deque<Integer> stack;
    Deque<Integer> min;

    public MinStack() {
        stack = new ArrayDeque<>();
        min = new ArrayDeque<>();
    }

    public void push(int val) {
        stack.push(val);
        if (min.isEmpty() || min.peek() >= val) {
            min.push(val);
        }
    }

    public void pop() {
        int val = stack.pop();
        if (!min.isEmpty() && min.peek() >= val) {
            min.pop();
        }
    }

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

    public int getMin() {
        return min.peek();
    }
}

一栈双元素

一个栈连续存放两个元素,一个是入栈的正常元素,另一个是当前元素中最小值。

当入栈时,保存一下栈此前的最小元素,然后入栈正常元素。在此判断,如果当前元素比栈此前的最小元素还要小,那就更新最小元素,否则最小元素还是之前的元素。

public class MinStack {
    Deque<Integer> stack;

    public MinStack() {
        stack = new ArrayDeque<>();
    }


    public void push(int val) {
        if (stack.isEmpty()){
            stack.push(val);
            stack.push(val);
        }else{
            int min = stack.peek();
            stack.push(val);
            if (val < min){
                stack.push(val);
            }else{
                stack.push(min);
            }
        }
    }

    public void pop() {
        stack.pop();
        stack.pop();
    }

    /**
     * ArrayDeque严格限制元素的存取,还想使用类似get(index)的api获取倒数第二个 
     */
    public int top() {
        int min = stack.pop();
        int top = stack.peek();
        stack.push(min);
        return top;
    }

    public int getMin() {
        return stack.peek();  
    }
}

链式栈

在链表中增加一个min的属性存储最小元素,然后每次插入元素都使用头插法,并且根据头指针指向的结点的min属性判断当前新结点的min属性。

public class MinStack{
    class Node{
        int val;
        int min;
        Node next;

        public Node(int val, int min) {
            this.val = val;
            this.min = min;
        }

        public Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }

    Node head;

    public MinStack() {

    }

    public void push(int val) {
        if (head == null){
            head = new Node(val, val);
        }else{
            // 新结点使用构造赋值val、min、next
            // min则是当前元素与栈此前最小元素比较
            // next指向原head,即头插法
            head = new Node(val, Math.min(head.min, val), head);
        }
    }

    public void pop() {
        Node h = head;
        head = h.next;
        // 如果是对象,这样清理利于GC
        h.val = 0; 
        h.min = 0;
        h.next = null;
    }

    public int top() {
        return head.val;
    }

    public int getMin() {
        return head.min;
    }
}

232. 用栈实现队列

使用双栈法,设置正常栈stack和临时栈temp。

当入队列时,直接入栈stack。

出队列时,因为要把元素“反过来”,所以需要把stack中的元素放到temp中,这样直接从temp中取,即为先进先出的队列。

当然,这也要看看temp中是否有元素,如果已经有元素,就说明已经翻转过了,先把翻转完的元素用完,然后再继续从stack中放新的过来。

class MyQueue {
    Deque<Integer> stack = new ArrayDeque<>();
    Deque<Integer> temp = new ArrayDeque<>();

    public MyQueue() {

    }

    public void push(int x) {
        stack.push(x);
    }

    public int pop() {
        // 临时栈空,则从stack中取元素“翻过来”
        if (temp.isEmpty()) {
            while (!stack.isEmpty()) {
                temp.push(stack.pop());
            }
        }
        // 直接从temp中取
        return temp.pop();
    }

    // 队列操作,因为同pop需要临时栈
    public int peek() {
        if (temp.isEmpty()) {
            while (!stack.isEmpty()) {
                temp.push(stack.pop());
            }
        }
        return temp.peek();
    }

    public boolean empty() {
        return stack.isEmpty() && temp.isEmpty();
    }
}

844. 比较含退格的字符串

我傻傻地用栈比对。

public boolean backspaceCompare(String s, String t) {
    Deque<Character> stack = new ArrayDeque<>();
    StringBuilder ssb = new StringBuilder();
    StringBuilder tsb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (!stack.isEmpty() && c == '#') {
            stack.pop();
        } else if (c != '#')  {
            stack.push(c);
        }
    }
    while (!stack.isEmpty()) {
        ssb.append(stack.pop());
    }
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        if (!stack.isEmpty() && c == '#') {
            stack.pop();
        } else if (c != '#') {
            stack.push(c);
        }
    }
    while (!stack.isEmpty()) {
        tsb.append(stack.pop());
    } 
    return ssb.toString().equals(tsb.toString());
}

其实可以直接用StringBuilder,可以append()和deleteCharAt(index)来实现栈的操作,确实更省一些。

public boolean backspaceCompare(String s, String t) {
    return build(s).equals(build(t));
}

private String build(String s) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // 他的判断好优雅
        if (c != '#') {
            sb.append(c);
        } else if (sb.length() > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    return sb.toString();
}

224. 基本计算器

这个。。。还得研究一下逆波兰表达式那些,这里是使用栈进行模拟。

而且我没想到,可以直接用一个sign判断正负号,并且可以push两个值入栈来处理括号逻辑。

public int calculate(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    int sign = 1, res = 0;
    int n = s.length();
    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)){
            int cur = c - '0';
            while (i + 1 < n && Character.isDigit(s.charAt(i + 1))){
                cur = cur * 10 + s.charAt(++i) - '0';
            }
            res += sign * cur;
        }else if(c == '+'){
            sign = 1;
        }else if(c == '-'){
            sign = -1;
        }else if(c == '('){
            stack.push(res);
            res = 0;
            stack.push(sign);
            sign = 1;
        }else if(c == ')'){
            res = stack.pop() * res + stack.pop();
        }
    }
    return res;
}

682. 棒球比赛 - 力扣(LeetCode) (leetcode-cn.com)

傻傻地用栈做,其实用数组就行了,只不过它的过程确实是像栈。

这里也可以发现,栈这个数据结构确实是操作受限的,比如当元素为+时,它要拿两个数来加,但是你不能直接拿第二个,需要把栈顶的提出,然后才能拿到。这也让我感受到这种操作受限的缺点?当然,本题是栈的思路,但是可以不用栈做,这是纯纯自找麻烦了。

    public int calPoints(String[] ops) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String op : ops) {
            if (op.equals("D")) {
                int val = stack.peek(); 
                stack.push(val << 1);
            } else if (op.equals("C")) {
                stack.pop();
            } else if (op.equals("+")) {
                int first = stack.pop();
                int second = stack.peek();
                stack.push(first);
                stack.push(first + second);
            } else {
                stack.push(Integer.parseInt(op));
            }
        }
        int sum = 0;
        while (!stack.isEmpty()) {
            sum += stack.pop();
        }
        return sum;
    }

496. 下一个更大元素 I

单调栈的应用。

凡是找右边第一个更大/更小的,都是用单调栈解决。

我一开始不太懂,想到什么“最小栈”??其实这个叫做单调栈,顾名思义,这个栈中的元素是单调的,在这里找右边更大的元素,里面存的元素则是从栈顶到栈底依次变小。如果有一个比栈中某些元素更大的,就把比它小的去掉。

大概是这样?可以多刷几道题。。

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    Deque<Integer> stack = new ArrayDeque<>();
    Map<Integer, Integer> map = new HashMap<>();
    int[] res = new int[m];
    for(int i = n - 1;i >= 0;i--){
        while(!stack.isEmpty() && stack.peek() <= nums2[i]){
            stack.pop();
        }
        map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
        stack.push(nums2[i]);
    }
    for(int i = 0;i < m;i++){
        res[i] = map.get(nums1[i]);
    }
    return res;
}

42. 接雨水

同样是单调栈的应用,似乎不太会表达。。

public int trap(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int sum = 0;
    for(int i = 0;i < height.length;i++){
        while(!stack.isEmpty() && height[stack.peek()] <= height[i]){
            int mid = stack.pop();
            if(stack.isEmpty()){
                break;
            }
            int left = stack.peek();
            int curWidth = i - left - 1;
            int curHeight = Math.min(height[left], height[i]) - height[mid];
            sum += curWidth * curHeight;
        }
        stack.push(i);
    }
    return sum;
}