答案在博客最下方，前面是题型和解析。
1. 改变元素的序列
1. 一个栈的入栈序列为ABCDE，则不可能的出栈序列为（ ）
A .ABCDE
B .EDCBA
C .DCEBA
D .ECDBA
2.借助于栈输入A、B、C、D四个元素（进栈和出栈可以穿插进行），则不可能出现的输出是 （ ）
A .DCBA
B .ABCD
C .CBAD
D .CABD
解析：
此题型虽说不是编程题，但是在非编程题中还是挺常见的！可以直接看着分析，也可以直接画图，画图是最稳妥的做法。
切记压栈出栈只能是栈顶。
2. 括号匹配
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例：
输入：s = "()" 输出：true
输入：s = "{)" 输出：false
输入：s = "{()}" 输出：true
解析：
这题比较简单，但很经典，是对栈特性很好的应用，具体操作如下：
循环遍历String中的字符，逐个取到每个括号，如果该括号是：
1. 左括号，直接入栈
2. 右括号，与栈顶的左括号进行匹配，如果不匹配直接返回false，否则继续循环
循环结束后，如果栈空则匹配，否则左括号比右括号多肯定不匹配。
3. 逆波兰表达式求值
题目描述：
给你一个字符串数组
tokens，表示一个根据逆波兰表达式表示的算术表达式。请你计算该表达式。
返回一个表示表达式值的整数。
示例：
输入：tokens = ["2","1","+","3","*"] 输出：9
输入：tokens = ["4","13","5","/","+"] 输出：6
解析：
逆波兰表达式（又称后缀表达式）是一种不包含括号的表达式表示方法，运算符位于操作数之后，因此不需要考虑运算符优先级和括号的问题。
对tokens数组进行遍历，依次获取到每个元素，如果：
1. 该元素是数字(注意：不是运算符肯定是数字)，将该数字入栈
2. 该元素是运算符，从栈顶获取该运算符对应的右左操作数，进行相应的操作，最后将结果入栈
循环结束后，栈顶的元素就是最终表达式的结果
4. 最小栈
题目描述：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
解析：
最小栈是指在一个栈中支持常数时间内获取栈中的最小元素。实现思路如下：
除了普通的栈，我们需要再创建一个辅助栈，用来存储当前栈的最小值。
在每次向栈中插入元素时，同时也需要向辅助栈中插入当前栈的最小值。
在每次从栈中弹出元素时，同时也需要从辅助栈中弹出当前栈的最小值。
获得栈中最小元素时，直接返回辅助栈的栈顶元素即可
5. 答案
1. D D
2.
public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); //遍历整个字符串 for (char c : s.toCharArray()) { //判断左右括号，左括号放入栈中，右括号便从栈中弹出来一个元素匹配 if (c == '(' || c == '[' || c == '{') { stack.push(c); } else { //如果栈中没有元素，直接false if (stack.isEmpty()) { return false; } //与弹出元素比较，不匹配返回false，匹配继续循环 char left = stack.pop(); if ((c == ')' && left != '(') || (c == ']' && left != '[') || (c == '}' && left != '{')) { return false; } } } //栈空返回true，反之false return stack.isEmpty(); }
3.
public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); //遍历每一个元素，如果是数字，放入栈中，不是弹出两个元素进行运算，结果放入栈中 for (String token : tokens) { if (token.equals("+")) { int b = stack.pop(); int a = stack.pop(); stack.push(a + b); } else if (token.equals("-")) { int b = stack.pop(); int a = stack.pop(); stack.push(a - b); } else if (token.equals("*")) { int b = stack.pop(); int a = stack.pop(); stack.push(a * b); } else if (token.equals("/")) { int b = stack.pop(); int a = stack.pop(); stack.push(a / b); } else { stack.push(Integer.parseInt(token)); } } return stack.pop(); }
4.
class MinStack { Stack<Integer> stack; Stack<Integer> minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } //如果最小栈为空，或者最小栈栈顶元素不小于放入元素，放入此元素 public void push(int x) { stack.push(x); if (minStack.empty() || x <= minStack.peek()) { minStack.push(x); } } //出栈时，如果与最小栈元素相同，最小栈也出元素 public void pop() { if (stack.pop().equals(minStack.peek())) { minStack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }
