1.概念
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据操作的一端称为栈顶，另一端称为栈底。栈中元素遵守后进先出的原则。
压栈：栈的插入操作脚进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
2.栈的使用
| 方法 | 功能 |
| Stack() | 构造一个空的栈 |
| E push(E e) | 将e入栈，并返回e |
| E pop() | 将栈顶元素出栈并返回 |
E peek() |
获取栈顶元素 |
| int size() | 获取栈中有效元素个数 |
| boolean empty() | 检测栈是否为空 |
public class Test { public static void main(String[] args) { Stack<Integer> stack=new Stack<>(); stack.push(12); stack.push(23); stack.push(34); stack.push(45); int val=stack.peek();//获取栈顶元素，但是不删除 System.out.println(val);//45 int val2=stack.pop();//删除并返回栈顶元素 System.out.println(val2); val=stack.peek();//获取栈顶元素，但是不删除 System.out.println(val);//34 stack.pop(); stack.pop(); stack.pop(); System.out.println(stack.empty()); System.out.println(stack.size()); } } 45 45 34 true 0 Process finished with exit code 0
3.栈的模拟实现
从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。（Stack可以调用Vector的成员属性和成员方法）
模拟实现代码：
public class MyStack { public int[] elem; public int usedSize; public static final int DEFAULT_CAPACITY=10; public MyStack() { elem=new int[DEFAULT_CAPACITY]; } /** * 入栈 * @param val */ public void push(int val) { //先判断栈是否满了 if(isFull()) { elem= Arrays.copyOf(elem,2*elem.length); } elem[usedSize++]=val; } /** * 判断当前栈是否满了 * @return */ public boolean isFull() { if(usedSize==elem.length) { return true; } return false; } /** * 删除栈顶元素 */ public int pop() { if(isEmpty()) { throw new RuntimeException("栈空了"); } int val= elem[usedSize-1]; usedSize--; return val; } /** * 是否为空 * @return */ public boolean isEmpty() { return usedSize==0; } /** * 获取栈顶元素但不删除 * @return */ public int peek() { if(isEmpty()) { throw new RuntimeException("栈为空了！"); } return elem[usedSize-1]; } }
4.栈的应用场景及OJ练习
1.将递归转化为循环
比如：逆序打印单链表
//递归方式 public void printList1(Node head) { if(null!=head) { printList1(head.next); System.out.println(head.val+" "); } } //循环方式 public void printList2(Node head) { if(head==null) return; Stack<Node> stack=new Stack<>(); //将链表中的结点保存在栈中 Node cur=head; while (cur!=null) { stack.push(cur); cur=cur.next; } //将栈中元素出栈 while (!stack.empty()) { System.out.println(stack.pop().val+" "); } }
2.括号匹配
【力扣题目 20. 有效的括号】
题意：
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
示例 3:
输入: “(]”
输出: false
示例 4:
输入: “([)]”
输出: false
示例 5:
输入: “{[]}”
输出: true
思路：
共有三种无效方式：
- 1.左右括号不匹配 "{(}}"
- 2.左括号多"(()"
- 3.右括号多"())"
将给定的字符串从头开始遍历，遇见左括号就对应入栈右括号（比如：遇见"{",就对应入栈"}"），在遇到不是左括号的情况下去出栈并比对括号是否一致，如果刚好遍历完字符串栈也为空，则说明为有效括号。
代码：
class Solution { public boolean isValid(String s) { Stack<Character> stack=new Stack<>(); char ch; for(int i=0;i<s.length();i++) { ch=s.charAt(i); if(ch=='(') stack.push(')'); else if(ch=='{') stack.push('}'); else if(ch=='[') stack.push(']'); else if(stack.isEmpty()||ch!=stack.pop()) return false; } return stack.isEmpty(); } }
3.逆波兰表达式求值
【力扣题目 150.逆波兰表达式求值】
题意：
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = [“2”,“1”,“+”,“3”,“*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = [“4”,“13”,“5”,“/”,“+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
思路：
给定中缀表达式转前缀后缀表达式的方法：
1.给每一步运算都加上括号
2.把符号都移到对应括号的外边（移到对应括号后边就是后缀表达式，移到对应括号前边就是前缀表达式）
3.去掉所有括号，得到前缀或者后缀表达式
上边扩充的是一些题外知识，该题的思路就是利用栈来完成运算，运算规则是：
如果是数字就入栈，如果是符号则不入栈，弹出栈顶两个元素，先弹出的为右操作数，后弹出的为左操作数，完成运算后入栈运算结果，最后返回最后的运算结果（栈中也就只有一个元素了）。
代码：
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack=new Stack<>(); for(String s:tokens) { 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.peek(); } //判断是否为操作符 private boolean isOperation(String s) { if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")) return true; return false; } }
4.出栈入栈次序匹配
【牛客题目链接 JZ31 栈的压入、弹出序列】
题意：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- 1.0<=pushV.length == popV.length <=1000
- 2.-1000<=pushV[i]<=1000
- 3.0pushV 的所有数字均不相同
- 示例1
- 输入：
- [1,2,3,4,5],[4,5,3,2,1]
- 返回值：
- true
- 说明：
- 可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
- 这样的顺序得到[4,5,3,2,1]这个序列，返回true
示例2
输入：
[1,2,3,4,5],[4,3,5,1,2]
返回值：
false
说明：
由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false
思路：
栈在入栈的同时也可以出栈，所以将入栈数组遍历依次进行入栈，每次入栈完成后判断栈顶元素是否与出栈数组从前往后的对应元素相同，如果相同则出栈，直到栈为空或者元素不相同，则继续入栈，到最后栈中为空则说明出栈入栈次序匹配。
代码：
public class Solution { 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()&&stack.peek()==popA[j]) { stack.pop(); j++; } } return stack.empty(); } }
