1. 栈的概念
栈是一种特殊的线性表，它只能在固定的一端进行插入和删除操作，进行数据插入和删除的一端为栈顶，另一端为栈底。栈中的元素遵循后进先出(LIFO)(Last In First Out)的原则。
压栈：栈的插入数据操作叫做进栈，压栈，入栈。入数据在栈顶
出栈：栈的删除操作叫做出栈。出数据在栈顶
2. 栈的使用
| 方法 | 功能说明 | |
| Stack() | 构造一个空栈 | |
| E push(E e) | 将e入栈并返回e | |
| E pop() | 将栈顶元素出栈并返回 | |
| E peek() | 获取栈顶元素 | |
| int size() | 获取栈中有效元素的个数 | |
| boolean empty() | 检测栈是否为空 |
将上述方法进行代码展示：
public class TestStack { 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()); s.pop(); System.out.println(s.peek()); if(s.empty()){ System.out.println("栈空"); }else{ System.out.println("栈不空，元素个数为："+s.size()); } } //结果： 4 3 栈不空，元素个数为：3
使用栈将递归转化为循环：
// 递归方式 void printList(Node node){ if(null != node){ printList(node.next); System.out.print(node.val + " "); } } // 循环方式 void printList(Node node){ if(null == node){ return; } Stack<Node> s = new Stack<>(); // 将链表中的结点保存在栈中 Node cur = node; while(null != cur){ s.push(cur); cur = cur.next; } // 将栈中的元素出栈 while(!s.empty()){ System.out.print(s.pop().val + " "); } }
3. 栈的OJ题
1. 括号匹配（LeetCode20）有效的括号
可以进入上面链接查看题目
方法：
1. 依次拿到字符串的元素，如果该元素是左括号，则入栈
2. 如果不是左括号，先判断栈是否为空，如果为空则返回false，如果不为空则进行后续操作
3. 拿到栈顶的元素与前面所拿到字符串的元素作比较，如果括号匹配，则栈顶元素出栈，结束当前循环，继续进行后续比较，如果括号不匹配，则返回false
4. 当字符串的元素比较完后，判断栈是否有剩余，如果有剩余，则返回false，无剩余则返回true
参考代码：
class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for(int i=0;i<s.length();i++){ char c = s.charAt(i); if(c=='('||c=='{'||c=='['){ stack.push(c); }else{ if(stack.empty()){ return false; } char top = stack.pop(); if(top=='{'&&c=='}'||top=='['&&c==']'||top=='('&&c==')'){ continue; }else{ return false; } } } if(!stack.empty()){ return false; } return true; } }
2.逆波兰表达式求值（LeetCode150）逆波兰表达式求值
可以进入上面链接查看题目
方法：
1. 依次将字符串入栈，如果字符串不是算数符号，则入栈
2. 当字符串是算数符号的时候，取栈顶的两个元素进行算数运算
3. 将运算的结果继续入栈
4. 依次进行上述循环
5. 最后返回栈顶元素的值，即所求逆波兰表达式的值
参考代码：
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> s = new Stack<>(); for(String e : tokens){ if(!(e.equals("+")||e.equals("-")||e.equals("*")||e.equals("/"))){ s.push(Integer.parseInt(e));//将字符e转为整型 }else{ int right = s.pop(); int left = s.pop(); switch(e) { case "+": s.push(left+right); break; case "-": s.push(left-right); break; case "*": s.push(left*right); break; case "/": s.push(left/right); break; } } } return s.peek(); } }
3. 出栈入栈次序匹配（JZ31）栈的压入、弹出序列
方法：
1. 当入栈序列的元素小于出栈序列的第一个元素，将入栈序列的元素依次入栈
2. 每入栈一个元素，入栈序列的下标加1
3. 当入栈序列的元素与出栈序列的元素相等时，进行出栈，并且出栈序列下标加1
4. 当出栈序列的元素遍历完后，返回true
参考代码：
class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { Stack<Integer> s = new Stack<>(); int inIndex = 0; int outIndex = 0; while(outIndex<popped.length){ while(s.empty()||s.peek()!=popped[outIndex]){ if(inIndex<pushed.length){ s.push(pushed[inIndex]); inIndex++; } else{ return false; } } s.pop(); outIndex++; } return true; } }
4. 栈的模拟实现
public class MyStack<E> { E[] array; int size; public MyStack(){ array = (E[])new Object[3]; } public E push(E e){ ensureCapacity(); array[size++] = e; return e; } public E pop(){ E e = peek(); size--; return e; } public E peek(){ if(empty()){ throw new RuntimeException("栈为空，无法获取栈顶元素"); } return array[size-1]; } public int size(){ return size; } public boolean empty(){ return 0 == size; } private void ensureCapacity(){ if(size == array.length){ array = Arrays.copyOf(array, size*2); } } }
5. 栈，虚拟机栈，栈帧的区别
栈：一种后进先出的数据结构，继承自Vector
虚拟机栈：具有特殊作用的一块内存空间。栈区：是线程私有的，存放的是函数调用相关信息，主要是栈帧，它是按照数据结构中栈的特性来实现的
栈帧：一种结构，与函数调用相关。内部：局部变量表，操作数栈。每个方法运行时JVM会创建一个栈帧，然后将栈帧压到虚拟机栈中，调用结束时，该方法对应的栈帧会从虚拟机栈中出栈。
