目录

一. 概念

二. 栈的使用

三. 栈的模拟实现

四. 栈的应用

1. 改变元素的序列

2. 将递归转化为循环

3. 括号匹配  链接

4. 逆波兰表达式求值 链接

5. 出栈入栈次序匹配 链接

6. 最小栈 链接

---

一. 概念

二. 栈的使用

public static void main ( String [] args ) {

        Stack < Integer > s = new Stack ();

        s . push ( 1 );

        s . push ( 2 );

        s . push ( 3 );

        s . push ( 4 );

        System . out . println ( s . size ()); // 获取栈中有效元素个数 ---> 4

        System . out . println ( s . peek ()); // 获取栈顶元素 ---> 4

        s . pop (); // 4 出栈，栈中剩余 1 2 3 ，栈顶元素为 3

        System . out . println ( s . pop ()); // 3 出栈，栈中剩余 1 2 栈顶元素为 3

        if ( s . empty ()){

                System . out . println ( " 栈空 " );

        } else {

                System . out . println ( s . size ());

        }

}

三. 栈的模拟实现

可以用链表实现, 也可以用顺序表实现, 这里我们用顺序表:

public class MyStack {
    int[] array;
    int size;
    public MyStack(){
    array = new int[3];
    }
    public int push(int e){
        ensureCapacity();
        array[size++] = e;
        return e;
    }
    public int pop(){
        int e = peek();
        size--;
        return e;
    }
    public int peek(){
        if(empty()){
            throw new RuntimeException("栈为空，无法获取栈顶元素");
        }
        return array[size-1];
    }
    public int size(){
        return size;
    }
    public boolean empty(){
        return 0 == size;
    }
    private void ensureCapacity(){
        if(size == array.length){
            array = Arrays.copyOf(array, size*2);
        }
    }
}

四. 栈的应用

1. 改变元素的序列

3. 括号匹配  链接

思路:

1. 先遍历字符串, 如果遇到左括号( { [ , 就压入栈中, 如果遇到右括号) } ], 就需要判断:

        1) 如果此时栈为空, 说明没有和右括号匹配的左括号, 所以括号匹配失败

        2)如果栈不为空, 那么判断栈顶元素是否和此时的字符相匹配, 如果匹配则出栈

2. 如果字符串遍历完成, 但此时栈中还有元素, 意味着左括号剩余, 则匹配失败

3. 字符串遍历完成, 栈中没有元素剩余, 则匹配成功

代码:

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{
               if(stack.isEmpty()){
                   return false;
               }else{
                    char ch2 = stack.peek();
                    if(ch2 == '(' && ch ==')' ||ch2 == '{' && ch =='}' ||ch2 == '[' && ch ==']'){
                        stack.pop();
                    }else{
                        return false;
                    }

               }
            }
        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;

    }
}

4. 逆波兰表达式求值 链接

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 
• 该算式的逆波兰表达式写法为  1 2 + 3 4 + *

 中缀表达式如果转成后缀表达式:

1. 将每一次计算都加上括号 例:(( 1 + 2 ) * ( 3 + 4 )) 

2. 将括号中的符号移到括号后 例: (( 1 2 )+( 3 4 )+) *

3. 把括号删去 例: 1 2 + 3 4 + *

逆波兰表达式如何求值:

1. 手动: 从前往后遍历字符串, 遇到运算符就取此运算符的前两个数字计算, 计算的值替换掉原来的位置一步一步运算即可

例:  1 2 + 3 4 + *

第一步:1+2 = 3  替换: 3 3 4 + *

第二步: 3+4 = 7 替换: 3 7 *

第三步: 3*7= 21

2. 代码:使用栈这种数据结构, 从前往后遍历字符串, 遇到数字就入栈, 遇到运算符就弹出两个数字并进行计算, 将结果再压入栈中

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<tokens.length;i++){
            String str = tokens[i];
          if(!isOperations(str)){
              int val = Integer.valueOf(str);
              stack.push(val);

          }else{
              int num2 = stack.pop();
              int num1 = stack.pop();
              switch(str) {
                case "+":
                  stack.push(num1+num2);
                  break;
                case "-":
                  stack.push(num1-num2);
                  break; 
                case "*":
                  stack.push(num1*num2);
                  break; 
                case "/":
                  stack.push(num1/num2);
                  break;
              }

          }
        }
     return stack.pop();
    }
//判断是否是运算符
    private boolean isOperations(String str){
        if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/") ){
            return true;
        }
        return false;

    }
}

5. 出栈入栈次序匹配 链接

思路:

给出两个数组, 数组pushV是入栈顺序, 数组popV是出栈顺序, 我们需要同时遍历两个数组, 将pushV中的数据压入栈中, 每放一次, 都要循环判断popV中的数字与栈顶元素是否相同, 如果相同则出栈, 数组popV向后遍历,不同则继续入栈, 最后当两个数组全部遍历完成, 则说明顺序是匹配的, 否则是不匹配的

代码:

public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int j = 0;
        for (i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while (!stack.isEmpty() && stack.peek() == popV[j] && j < popV.length) {
                stack.pop();
                j++;
            }
        }
        if (i == pushV.length && j == popV.length) {
            return true;
        }
        return false;
    }

6. 最小栈 链接

思路:

1. 要想在常数时间检索到最小的数字, 需要借助两个栈, 一个普通栈存放所有的元素, 另一个最小栈存放压栈时的最小数字

2. 当入栈时, 要先和最小栈中的栈顶元素进行比较, 如果最小栈为空, 则直接存放在最小栈, 如果大于栈顶元素, 不放, 如果小于等于栈顶元素, 放

3. 当出栈时, 需从普通栈出栈, 如果最小栈的栈顶元素和要出栈的数字相同, 则最小栈也需要出栈

代码:

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            int peekNum = minStack.peek();
            if(val <= peekNum){
                minStack.push(val);
            }
        }

    }
    
    public void pop() {
        int popNum = stack.pop();
        if(popNum == minStack.peek()){
            minStack.pop();
        }

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

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

    }
}