从0到1带你了解栈

Dear 丶 2023-09-27 11:08 75阅读 0赞

![在这里插入图片描述][7d81a96e93b04d179e5476f115cee9b0.gif_pic_center]

#### 文章目录 ####

*  一、栈是什么？
 *  二、自定义实现栈
 *  三、逆波兰式求值
 *  四、栈的压入、弹出序列
 *  五、有效的括号
 *  六、最小栈

## 一、栈是什么？ ##

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。  
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。  
出栈：栈的删除操作叫做出栈。出数据在栈顶。  
![在这里插入图片描述][118776996efc425887f10cc713099b19.png]

## 二、自定义实现栈 ##

import java.util.Arrays;
    import java.util.Stack;
    public class MyStack {
        
        public int[] elem;
        public int usedSize;
        public static final int DEFAULT_SIZE = 10;
    
        public MyStack() {
        
            elem = new int[DEFAULT_SIZE];
        }
        //压栈
        public int push(int data) {
        
            if(isFull()) {
        
                elem = Arrays.copyOf(elem,2 * elem.length);
            }
            this.elem[usedSize] = data;
            usedSize++;
            return data;
        }
    
        private boolean isFull() {
        
            return usedSize >= elem.length;
        }
        //出栈
        public int pop() {
        
            if(isEmpty()) {
        
                throw new MyEmptyStackException("栈为空，不能弹出");
            }
            return elem[--usedSize];
        }
        private boolean isEmpty() {
        
            return usedSize == 0;
        }
        //查看栈顶元素
        public int peek() {
        
            if(isEmpty()) {
        
                throw new MyEmptyStackException("栈为空");
            }
            return elem[usedSize - 1];
        }
    }

## 三、逆波兰式求值 ##

有效的算符包括 +、-、\*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。  
注意 两个整数之间的除法只保留整数部分。  
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。  
![在这里插入图片描述][afd3aa76f1764f50b7ba63b07321d32d.png]

public static int evalRPN(String[] tokens) {
        
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < tokens.length; i++) {
        
                String s = tokens[i];
                if(!isOperation(s)) {
        
                    stack.push(Integer.parseInt(s));
                }else {
        
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                        switch (s) {
        
                            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();
        }
        public static boolean isOperation(String s) {
        
            if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
        
                return true;
            }
            return false;
        }

## 四、栈的压入、弹出序列 ##

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。  
![在这里插入图片描述][14c36ad5914f47c2b77ef96e8fdd2936.png]  
![在这里插入图片描述][9f9934f8bb63498f93ef4fb5a9c1eaf5.png]

public boolean IsPopOrder(int [] pushA, int [] popA) {
        
            Stack<Integer> stack = new Stack<>();
            int j = 0;
            for (int i = 0; i < pushA.length; i++) {
        
                stack.push(pushA[i]);
                while (!stack.empty() && j < popA.length && stack.peek().equals(popA[j])) {
        
                    stack.pop();
                    j++;
                }
            }
            if (!stack.empty()) {
        
                return false;
            }
            return true;
        }

## 五、有效的括号 ##

给定一个只包括 ‘(’，‘)’，‘\{’，‘\}’，‘\[’，‘\]’ 的字符串 s ，判断字符串是否有效。  
有效字符串需满足：  
左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
每个右括号都有一个对应的相同类型的左括号。

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

## 六、最小栈 ##

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。  
实现 MinStack 类:  
MinStack() 初始化堆栈对象。  
void push(int val) 将元素val推入堆栈。  
void pop() 删除堆栈顶部的元素。  
int top() 获取堆栈顶部的元素。  
int getMin() 获取堆栈中的最小元素。  
![在这里插入图片描述][ec9e4c295c734ffdb39e5d4121afa977.png]

import java.util.Stack;
    public 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 x = minStack.peek();
                if(val <= x) {
        
                    minStack.push(val);
                }
            }
        }
    
        public void pop() {
        
            if(!stack.empty()) {
        
                int x = stack.peek();
                int y = minStack.peek();
                if(x == y) {
        
                    minStack.pop();
                }
                stack.pop();
            }
        }
    
        public int top() {
        
            if(!stack.empty()) {
        
                return stack.peek();
            }
            return -1;
        }
    
        public int getMin() {
        
            if(!minStack.empty()) {
        
                return minStack.peek();
            }
            return -1;
        }
    }

[7d81a96e93b04d179e5476f115cee9b0.gif_pic_center]: https://img-blog.csdnimg.cn/7d81a96e93b04d179e5476f115cee9b0.gif#pic_center
[118776996efc425887f10cc713099b19.png]: https://img-blog.csdnimg.cn/118776996efc425887f10cc713099b19.png
[afd3aa76f1764f50b7ba63b07321d32d.png]: https://img-blog.csdnimg.cn/afd3aa76f1764f50b7ba63b07321d32d.png
[14c36ad5914f47c2b77ef96e8fdd2936.png]: https://img-blog.csdnimg.cn/14c36ad5914f47c2b77ef96e8fdd2936.png
[9f9934f8bb63498f93ef4fb5a9c1eaf5.png]: https://img-blog.csdnimg.cn/9f9934f8bb63498f93ef4fb5a9c1eaf5.png
[ec9e4c295c734ffdb39e5d4121afa977.png]: https://img-blog.csdnimg.cn/ec9e4c295c734ffdb39e5d4121afa977.png