热身：

1 . 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

   A: 1,4,3,2   B: 2,3,4,1   C: 3,1,4,2   D: 3,4,2,1

分析：这里有个隐含条件，压栈序列1，2，3，4，当时压栈，当时就可以出栈，简单来讲，让1进栈时，当时就可以将1弹出栈，再往后进栈；

如此分析，只有B选项符合条件：1进栈，2进栈，与B选项第一个出栈序列匹配，弹出2，再看进栈序列中：1与弹出序列的3不匹配，继续对进栈序列的下一个元素比较，如此往复，可得出答案。

JZ31栈的压入、弹出序列

思路：

创建一个栈stack

对进栈序列先压栈再与出栈序列比较

若相等则弹出

import java.util.*;
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int count = 0;//计数：与压栈数据匹配则加一
        for(int i = 0; i < pushA.length; i++){
            if(pushA[i] == popA[count]){
                //先压栈，再判断
                stack.push(pushA[i]);
                while(stack.peek() == popA[count]){
                    stack.pop();
                    count++;
                    //popA遍历完说明正确
                    if(count == pushA.length){
                        return true;
                    }
                    /**
                    *弹出栈后，可能一个元素也不剩，这时再到while里判断，
                    *有可能能造成对空指针的解引用操作
                    */
                    if(stack.empty()){
                        break;
                    }
                }
            }
            else{
                stack.push(pushA[i]);
            }
        }
        return false;
    }
}

逆波兰表达式求值

博主已整理出博客，快去看看吧~

http://t.csdn.cn/adU0q

有效的括号

也是对栈的理解中，频率较高的考题

思路：

1.创建一个栈

2.大的方向上遍历给定数组

3.小的方向上比较是否匹配

注意：不匹配分为以下几种情况

a.左右括号不匹配

b.右括号多：当前下标是右括号，但栈为空

c.左括号多：字符串数组遍历完成，但栈仍不为空

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == '(' || ch == '{' || ch == '['){
                stack.push(ch);
            }
            else{
                //说明ch是右括号
                if(stack.empty()){
                    //右括号多
                    return false;
                }
                char tmp = stack.peek();
                if(tmp == '(' && ch == ')' || 
                   tmp == '{' && ch == '}' || 
                   tmp == '[' && ch == ']'){
                       //当前括号匹配
                       stack.pop();
                }
                else{
                    //左右括号不匹配
                    return false;
                }
            }
        }
        //判断是否为空
       if(stack.empty()){
            return true;
        }
        else{
            //左括号多
            return false;
        }
    }
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/124361.html