一、关于栈(Stack)
1.1 栈的概念
一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO( Last In First Out)原则
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈。出数据在栈顶。
栈在现实生活中的例子：
上面的两个例子都遵循后进先出的原则。
1.2 栈的使用
栈可以在库函数中直接调用，比如下面的代码：
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()); } }
1.3 栈的模拟实现
从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。
所以，我们就可以利用顺序表来实现栈。
1.3.1 栈的类定义
默认栈的大小为10，也可以通过构造函数自己定义栈的大小。
public class MyStack { private final int DEFALUT_CAPACITY=10; private int[] elem; private int usedSize; public MyStack(){ elem=new int[DEFALUT_CAPACITY]; } public MyStack(int size){ int[] elem=new int[size]; } }
1.3.2 判断栈空或栈满
栈空：在栈的类定义中，我们定义了一个usedSize来表示当前栈中的元素个数,因此，判断栈是否为空，只需要判断usedSize是否为0即可。
public boolean isEmpty(){ return usedSize==0; }
栈满：如果当前栈中的元素个数和数组的长度相等，那么就判栈满。
public boolean isFull(){ return elem.length==usedSize; }
1.3.3 出栈
数组的最后一个元素便是栈顶的元素，返回这个元素即可。
public int pop(){ if(isEmpty()){ System.out.println("栈空!"); return -1; //或者抛自定义的异常 } int old=elem[usedSize-1]; usedSize--; //若是引用类型:>elem[usedSize]=null; return old; }
1.3.4 入栈
public void push(int data){ if(isFull()){ elem= Arrays.copyOf(elem,elem.length*2); } elem[usedSize]=data; usedSize++; }
1.3.5 获取栈顶元素
public int peak(){ if(isEmpty()){ System.out.println("栈空!"); return -1; } return elem[usedSize-1];//获取栈顶元素 }
1.3.6 获取栈中当前元素个数
public int size(){ return usedSize; }
二、栈的应用
2.1 后缀表达式求值
后缀表达式求值的基本思路是:>当遇到的字符串是数字时，把它压入栈中，而当遇到的字符串是操作符时，从栈中弹出两个元素做对应的运算,再把运算结果压入栈中。字符串遍历完成后，栈顶元素就是计算的结果。这里需要注意，当遇到操作符要执行出栈操作是，第一次出栈的元素是计算时的右操作数，第二次出栈的元素是计算时的左操作数。
比如下面的题目：
给你一个字符串数组 tokens ，表示一个根据后缀表达式表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
根据上面的思路，我们写这个代码其实就非常简单了:>
public int evalRPN(String[] tokens) { Stack<Integer> stack=new Stack<>(); for (String x:tokens) { if(!isOperation(x)){ //如果不是操作符，就把x转为数字并压栈 stack.push(Integer.parseInt(x)); }else{ //弹出两个操作数，并做相应的运算 int num2=stack.pop(); int num1=stack.pop(); switch (x){ case "+": stack.push(num1+num2); break; case "-": stack.push(num1-num2); break; case "*": stack.push(num1*num2); break; case "/": stack.push(num1/num2); break; } } } int ret = stack.pop(); return ret; } private boolean isOperation(String s){ if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){ return true; } return false; }
2.2 括号匹配
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路:
- 遍历字符串，当遇到这三种左括号时，全部压入栈中。
- 当遇到右括号时，如果当前栈空，直接返回false，因为这种情况是不可能匹配成功的
- 如果当前栈不空，先获取(不能直接出栈)栈顶元素，与当前的右括号进行匹配。
- 若匹配成功，当前与之匹配的栈顶元素出栈，继续向后遍历。
- 否则匹配不成功，返回false。
- 当遍历完成后，只需判断当前栈是否为空，若为空，那肯定是匹配成功。
- 若遍历完成后，当前栈非空，说明匹配失败，返回false。（说明左括号多）
下面是代码实现:>
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()){ //如果栈不空 char ch2=stack.peek();//ch是右括号,ch2是左括号 if((ch2=='(' && ch==')') || (ch2=='{' && ch=='}') || (ch2=='[' && ch==']')){ //左括号出栈 stack.pop(); }else { return false; } }else { return false; } } } if(!stack.empty()){ //i已经遍历完成，栈还不为空，返回false return false; } return true; }
2.3 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void push(int val)将元素val推入堆栈。int top()获取堆栈顶部的元素。(这里指普通栈)int getMin()获取堆栈中的最小元素。
思路:>
利用两个栈来同时进行相关的操作，需要定义一个普通栈(Stack)，还需要定义一个存放最小元素的栈(MinStack)。
关于入栈:>
- 普通栈无论如何是要进行入栈操作的，那么只需要考虑最小栈是否要进行入栈操作。
- 最小栈存放的是最小元素，所以每次普通栈进行入栈的时候，需要把当前要进入普通栈的元素(val)和在最小栈里的栈顶元素进行比较，如果val小于等于最小栈中的栈顶元素，此时最小栈也是需要执行入栈操作的。
- 需要注意的是，在普通栈进行第一次入栈操作的时候，最小栈也是需要入栈的，也就是说，当最小栈当前为空，直接入栈即可。若最小栈非空，才需要比较大小，让小的压入最小栈。
关于出栈:>
- 执行出栈操作时，为了确保在获取最小元素的时候不出错，同样需要把当前从普通栈弹出的元素和最小栈中的栈顶元素比较(因为要确保最小栈存放的是当前栈的最小值)。
- 如果普通栈中弹出的元素比最小栈中的栈顶元素大，那么普通栈弹出元素并不会影响获取当前栈中的最小元素，直接出栈即可。
- 当普通栈中弹出元素等于(不可能小于)最小栈的栈顶元素时，这两个栈要同时执行出栈操作。(因为如果此时最小栈不弹出，并不能更新普通栈弹出元素后，此时普通栈的最小值)
下面的具体的代码实现:>
class MinStack { private Stack<Integer> stack; private 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 peekVal=MinStack.peek(); if(val<=peekVal){ MinStack.push(val); } } } public void pop() { /** * pop的时候和stack的栈顶元素比较，如果相等，全部出栈 * 不一样，只出普通栈 */ int val=stack.pop(); if(!MinStack.empty()){ if(val==MinStack.peek()){ MinStack.pop(); } } } public int top() { return stack.peek(); } public int getMin() { if(!MinStack.empty()){ return MinStack.peek(); } return -1; } }
2.4 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- 0<=pushV.length == popV.length <=1000
- -1000<=pushV[i]<=1000
- pushV 的所有数字均不相同
思路:>
- 遍历入栈数组，同时遍历给定的弹出序列。
- 每次将入栈数组中的元素入栈后，就和给定的弹出序列比较
- 若相等，那么直接将入栈的元素弹出
- 遍历结束后，若栈空，说明给定的序列可以成为该栈的弹出序列。否则，返回false。
下面是具体的实现代码:>
public boolean IsPopOrder (int[] pushV, int[] popV) { // write code here Stack<Integer> stack = new Stack<>(); int j = 0; for (int i = 0; i < pushV.length; i++) { stack.push(pushV[i]); while (!stack.empty() && j < popV.length && stack.peek() == popV[j]) { stack.pop(); j++; } } if (stack.empty()) { return true; } return false; }
