1.栈
1.1 栈的特点
栈是一种组织数据的方式，栈内的元素有先进后出的特点，因此也叫做先进后出表，由此我们能够得到栈的概念：栈是一种只能在一端进行插入或删除操作的线性表。栈常常由顺序表或双链表实现，Java 的 Stack 类底层就是由顺序表实现的，当然 LinledList 底层是一个双链表，由此 LinkedList 也可以当做栈来使用。
如果你现在对于栈还不能理解，你可以想象栈就是一个“死胡同”，只能一端进或者出。
栈的几个术语：允许进行插入、删除操作的一端称为栈顶；栈的另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈（压栈）。栈的删除操作通常称为退栈或出栈。
1.2 栈的常见应用
1.2.1 验证栈的压入、弹出序列
给你入栈序列，判断不可能的出栈序列，见例题：
选项 A： a，b，c 依次入栈，c 出栈，d 入栈，d 出栈，b，a 依次出栈，出栈序列为 c，d，b，a，所以选项 A 的出栈序列是可能的。选项 B： a，b，c，d 依次入栈，d，c，b，a 依次出栈，出栈序列为 d，c，b，a，所以选项 B 的出栈序列是可能的。选项 C： a 入栈，a 出栈，b，c 依次入栈，c 出栈，d 入栈，d 出栈，b 出栈，出栈序列为 a，c，d，b 所以选项 C 的出栈序列是可能的。选项 D： a，b，c，d 依次入栈，d 出栈，后一个出栈元素不可能是 a，所以选项 D 的出栈序列是不可能的。
举一反三，看下面一道题：
p3的取值除了不能取到 3 其他的值均有可能，因此p3取值个数为n−1。
1.2.2 前，中，后缀表达式
我们常用的数学加减乘除运算表达式都是中缀表达式，比如1+1+6∗8，将中缀表达式按运算顺序打上不同的的括号对，分别将运算符移到对应括号最右边，再将所有括号擦除，就能得到后缀表达式，同理将运算符移到到对应括号最左边就是前缀表达式。
2.Stack
2.1Stack 类的使用
2.1.1Stack 类与 Vector 类
Stack 类的继承实现关系图如下，不妨把它称作 Stack 的家谱吧：
我们发现 Stack 支持序列化，克隆，随机访问，for-each 循环遍历，Collection，List 接口，Vector 都可以引用 Stack 对象.
Vector 与 ArrayList 基本是一致的，不同的是 Vector 是线程安全的，会在可能出现线程安全的方法前面加上synchronized关键字。对于 Vector 类，是线程安全的动态数组，但是性能较差，可以说 Vector 已经过时了，不常用了，取而代之的是性能更强的 CopyOnWriteArrayList。所以本文着重介绍 Stack 类，Vector 类不多阐述。因为 Vector 是线程安全的，那它的子类 Stack 自然也是线程安全的。
Vector & ArrayList & CopyOnWriteArrayList 三者的区别：
这三个集合类都继承 List 接口，都是动态的顺序表，其不同点如下：
2.1.2 常用方法
这些方法的使用结合后文的题目进行演示。
2.2Stack 简单模拟实现
栈的基本结构：数组（泛型）+ 栈顶指针
public class MyStack<E> { private E[] elem;//栈空间 private int top;//栈顶索引}
复制代码
入栈 push+出栈 pop+判断栈是否为空 empty+获取栈顶元素 peek+toString 方法:
public class MyStack<E> { private E[] elem; private int top; public MyStack() { this.elem = (E[])new Object[10]; this.top = 0; } public void push(E e) { if (top == this.elem.length) { this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length); } this.elem[this.top] = e; top++; } public E peek() { if (this.top <= 0) { throw new StackOverflowError("栈为空！"); } return this.elem[this.top - 1]; } public E pop() { if (this.top <= 0) { throw new StackOverflowError("栈为空！"); } this.top--; return this.elem[this.top]; } public boolean empty() { return this.top <= 0; }
@Override public String toString() { if (this.top <= 0) { return "[]"; } StringBuilder stringBuilder = new StringBuilder("["); for (int i = 0; i < this.top - 1; i++) { stringBuilder.append(this.elem[i]); stringBuilder.append(","); } stringBuilder.append(this.elem[this.top - 1]); stringBuilder.append("]"); return stringBuilder.toString(); }}
复制代码
测试代码：
public class Test { public static void main(String[] args) { MyStack<Integer> stack1 = new MyStack<>(); MyStack<String> stack2 = new MyStack<>(); //push test stack1.push(1); stack1.push(2); stack1.push(3); System.out.println(stack1.toString());
stack2.push("虎年"); stack2.push("大吉"); System.out.println(stack2.toString());
//peek test System.out.println(stack1.peek()); System.out.println(stack2.peek());
//pop test empty test System.out.println(stack1.pop()); System.out.println(stack1.pop()); System.out.println(stack1.pop()); System.out.println(stack1.empty());
System.out.println(stack2.pop()); System.out.println(stack2.pop()); System.out.println(stack2.empty()); }}
复制代码
运行结果：
2.3 使用 Stack 解决问题
2.3.1 验证栈的出入序列
在前面 1.2.1 已经介绍了给定一个入栈序列，判断一个序列是否可能是出栈序列的问题，在这里我们来尝试使用编程来解决它！
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2}，就不可能是该压栈序列的弹出序列。
示例：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出：true解释：我们可以按以下顺序执行：push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
复制代码
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]输出：false解释：1 不能在 2 之前弹出
复制代码
提示：
0<=pushed.length==popped.length<=10000<=pushed[i],popped[i]<1000pushed 是 popped 的入栈排列。
💡解题思路：我们可以对入栈序列数组进行遍历，每次都将里面的元素入栈，然后依次按顺序将出栈序列数组中的元素与栈顶元素比较，如果相等就出栈，并比较下一个出栈数组元素与下一次栈顶元素是否相等，相等就出栈，以此类推直到不相等为止，最终栈为空栈，则出栈序列是可能的。例如：pushed=[1,2,3,4,5],popped=[4,5,3,2,1]
最终栈为空，所以返回true。
🔑源代码：
class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { Stack<Integer> stack = new Stack<>(); int j = 0; for (int i = 0; i < pushed.length; i++) { stack.push(pushed[i]); while (!stack.empty() && stack.peek() == popped[j]) { stack.pop(); j++; } } return stack.empty(); }}
复制代码
在线练习链接：1.946. 验证栈序列2.剑指 Offer 31. 栈的压入、弹出序列
2.3.2 逆波兰表达式
还能记得文章前面介绍的前中后缀表达式吗？逆波兰表达式就是后缀表达式，我们来尝试一下使用编程进行后缀表达式求值。
根据 逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]输出：9解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
复制代码
示例 2：
输入：tokens = ["4","13","5","/","+"]输出：6解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
复制代码
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]输出：22解释：该算式转化为常见的中缀算术表达式为： ((10 * (6 / ((9 + 3) * -11))) + 17) + 5= ((10 * (6 / (12 * -11))) + 17) + 5= ((10 * (6 / -132)) + 17) + 5= ((10 * 0) + 17) + 5= (0 + 17) + 5= 17 + 5= 22
复制代码
提示：
1<=tokens.length<=104tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围[-200, 200]内的整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如(1+2)∗(3+4) 。该算式的逆波兰表达式写法为 ((12+)(34+)∗) 。逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 12+34+∗ 也可以依据次序计算出正确结果。
💡解题思路：适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。
首先遍历字符串数组，然后判断元素是否是运算符，如果是则从栈中取出两个元素进行运算，并将结果入栈，如果不是运算符则将字符串转数字入栈。注意，先出栈的数要放在运算符右边，后出栈的数放在运算符左边。最终栈顶元素的值即为运算结果。比如：11+68∗+，转换成中缀表达式为1+1+6∗8，结果为50。
🔑源代码：
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (int i = 0; i < tokens.length; i++) { String s = tokens[i]; if (isOperation(s)) { //遇到运算符，出栈元素，进行计算，结果入栈 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; } } else { //遇到数字，入栈，等待计算 stack.push(Integer.parseInt(s)); } } //最终栈中的元素为最终结果 return stack.pop(); } public boolean isOperation(String s) { if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) { return true; }else { return false; } }}
复制代码
在线练习链接：150. 逆波兰表达式求值剑指 Offer II 036. 后缀表达式
2.3.3 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。pop() —— 删除栈顶的元素。top() —— 获取栈顶元素。getMin() —— 检索栈中的最小元素。
示例:
输入：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]
输出：[null,null,null,null,-3,null,0,-2]
解释：MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.getMin(); --> 返回 -2.
复制代码
提示：pop、top 和 getMin 操作总是在 非空栈 上调用。
💡解题思路：该题的意思是设计一个栈，能够获取栈中实时最小值，我们可以使用一个辅助栈，用来存放实时最小值，主栈每一个元素均。出栈时，如果辅助栈出栈元素与主栈出栈元素相同，则同时出栈，否则仅出主栈上的元素。
怎么在辅助栈中存放实时最小值？很简单，入栈时，如果待入栈元素的值小于或等于栈顶元素，则入栈，辅助栈为空栈时，直接入栈。主栈不论什么情况，均入栈。代码演示主栈为stack，辅助栈为min。
🔑源代码：
class MinStack { Stack<Integer> stack; Stack<Integer> min;
public MinStack() { this.min = new Stack<>(); this.stack = new Stack<>(); } public void push(int val) { if (this.min.isEmpty()) { this.min.push(val); } else if (this.min.peek() >= val) { this.min.push(val); } this.stack.push(val); } public void pop() { if (this.stack.peek().equals(this.min.peek())) { this.min.pop(); } this.stack.pop(); } public int top() { return this.stack.peek(); } public int getMin() { return this.min.peek(); }}
复制代码
在线练习链接：155. 最小栈面试题 03.02. 栈的最小值
好了，本文就分享到这里了，下次再见！
评论