引言：Re：从零开始的DS生活 轻松和面试官扯一个小时栈，详细介绍了栈的概念和性质，简要的介绍了栈ADT并附两种实现方式（链式、顺序），列举LeetCode第20题与严蔚敏老师栈和递归的讲解加深对栈的应用，供读者理解与学习，适合点赞+收藏。有什么错误希望大家直接指出~
友情链接：Re：从零开始的DS生活 轻松从0基础写出链表LRU算法、Re：从零开始的DS生活 轻松从0基础实现多种队列、Re：从零开始的DS生活 轻松从0基础写出Huffman树与红黑树
导读（有基础的同学可以通过以下直接跳转到感兴趣的地方）
栈的基本概念和性质,栈ADT及其顺序,链接实现;
栈（Stack）又名后进先出表LIFO(Last In First Out),，它是一种运算受限的线性表。 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底（这句话是性质）。和弹夹的进出顺序是一样的。
编辑
进栈：入栈或压栈，将新元素放到栈顶元素的上面，使之成为新的栈顶元素。
出栈：退栈，将栈顶元素删除掉，使得与其相邻的元素成为新的栈顶元素。
编辑
栈ADT
ADT Stack{ 数据对象: D={aijlai属于ElemSet, i=1,2...n, n>=0} 数据关系: R1={<ai-1,ai>/ai-1, ai属于D, i=2,... n} 约定an端为栈顶, al端为栈底。 基本操作: InitStack(&S) // 操作结果:构造一个空栈 S. DestroyStack(&S) // 初始条件:栈S已存在 操作结果:栈S被销毁 ClearStack(&S) // 初始条件:栈S已存在 操作结果:将S清为空栈 StackEmpty(S) // 初始条件 :栈S已存在 操作结果:若栈S为空栈,则返回TRUE,否则 FALSE Stacklength(S) // 初始条件:栈S已存在 操作结果:返回S的元素个数,即栈的长度 GetTop(S, &e) // 初始条件:栈S已存在且非空 操作结果:用e返回S的栈顶元素 Push(&S, e) // 初始条件:栈S已存在 操作结果:插入元素e为新的栈顶元素 Pop(&S, &e) // 初始条件:栈S已存在且非空操作结果:删除S的栈顶元素,并用e返回其值 StackTraverse(S, visit() //初始条件: 栈S已存在并非空 操作结果:从栈底到栈顶依次对S的每个数据元素调用函数visit(),一旦visit()失败,则返回操作失败。 }ADT Stack 出自《数据结构(C语言版)》严蔚敏、吴伟民著)
栈的顺序,链接实现
栈的数组(顺序)实现
编辑
/** * 栈的数组实现--java * 数组的长度是固定的，当栈空间不足时，将原数组数据复制到一个更长的数组中 * 故入栈的时间复杂度为O(N)，出栈的时间复杂度依然为O(1) * * @author macfmc * @date 2020/6/12-20:08 */ public class MyArrayStack { /** * 容器 */ private Object[] stack; /** * 栈的默认大小 */ private static final int INIT_SIZE = 10; /** * 栈顶索引 */ private int index; /** * 初始化栈_默认构造方法 */ public MyArrayStack() { this.stack = new Object[INIT_SIZE]; this.index = -1; } /** * 初始化栈，自定义长度 */ public MyArrayStack(int init_size) { if (init_size < 0) { throw new RuntimeException(); } this.stack = new Object[init_size]; this.index = -1; } /** * 判断栈是否为空 * * @return */ public boolean isEmpty() { return index == -1; } /** * 判断是都栈满 * * @return */ public boolean isFull() { return index >= stack.length - 1; } /** * 入栈 * * @param obj */ public synchronized void push(Object obj) { // 动态扩容 if (isFull()) { Object[] temp = stack; // 创建一个二倍大小的数组 stack = new Object[stack.length * 2]; // System.arraycopy(temp, 0, stack, 0, temp.length); } stack[++index] = obj; } /** * 查看栈顶元素 * * @return */ public Object peek() { if (!isEmpty()) { return stack[index]; } return null; } /** * 出栈 * * @return */ public synchronized Object pop() { if (!isEmpty()) { Object obj = peek(); stack[index--] = null; return obj; } return null; } public static void main(String[] args) { MyArrayStack stack = new MyArrayStack(); for (int i = 0; i < 100; i++) { stack.push("stack" + i); } for (int i = 0; i < 100; i++) { System.out.println(stack.pop()); } } }
栈的链表(链接)实现
编辑
/** * 栈的链表实现--java * * @author macfmc * @date 2020/6/12-20:08 */ public class MyLinkedStack<T> { /** * 单链表 * * @param <T> */ private class Node<T> { //指向下一个节点 Node next; //本节点存储的元素 T date; } /** * 栈中存储的元素的数量 */ private int count; /** * 栈顶元素 */ private Node top; public MyLinkedStack() { count = 0; top = null; } /** * 判断是都为空 * * @return true为空 */ public boolean isEmpty() { return count == 0; } /** * 入栈 * * @param element */ public void push(T element) { Node<T> node = new Node<T>();//链表节点 node.date = element;//链表节点数据 node.next = top;//链表下一步节点 top = node;//现在的栈顶 count++;//栈数量 } /** * 出栈 * * @return */ public T pop() { if (isEmpty()) { throw new RuntimeException(); } T result = (T) top.date; top = top.next; count--; return result; } /** * 获取栈顶 * * @return */ public T peek() { if (isEmpty()) { throw new RuntimeException(); } return (T) top.date; } public static void main(String[] args) { MyLinkedStack<String> lind = new MyLinkedStack<String>(); for (int i = 0; i < 10; i++) { lind.push("LindedStack" + i); } for (int i = 0; i < 10; i++) { System.out.println(lind.pop()); } } }
栈的应用
括号匹配的检验-有效括号问题
// https://leetcode-cn.com/problems/valid-parentheses/） class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); char[] chars = s.toCharArray(); // 遍历括号 for (char aChar : chars) { if (stack.size() == 0) { // 初始化栈，没有的话会报空栈异常EmptyStackException stack.push(aChar); } else if (isSym(stack.peek(), aChar)) { // 判断栈顶和入栈元素是不是一对括号 stack.pop(); } else { stack.push(aChar); } } return stack.size() == 0; } private boolean isSym(char c1, char c2) { return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}'); } public boolean isValid2(String s) { Stack stack = new Stack(); char[] chars = s.toCharArray(); for (char c : chars) if (stack.size() == 0) stack.push(c); else if (isSym((char) stack.peek(), c)) stack.pop(); else stack.push(c); return stack.size() == 0; } private boolean isSym(char c1, char c2) { return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}'); } }
栈的经典应用-逆波兰表达式法
中缀表达式转为后缀表达式：
设置一个堆栈，初始时将堆栈顶设置为#
顺序读入中缀表达式，到读到的单词为数字时将其输出，接着读下一个单词；
令x1 为栈顶运算符变量，x2 为扫描到的运算符变量，当顺序从表达试中读到的运算符时赋值给x2，然后比较x1 和 x2 的优先级，若x1 的优先级高于x2的优先级，将x1退栈并输出，接着比较新的栈顶运算符x1，x2的优先级；若 x1的优先级低于x2的优先级，将x2 入栈;如果x1 = “（”且 x2 = “）”，将x1 退栈；若x1的优先级等于x2的优先级且x1 = “#”而x2=“#”时，算法结束
import java.util.ArrayList; import java.util.Stack; /** * @author macfmc * @date 2020/6/13-22:30 */ public class ReversePolishNotation { /** * 测试的main方法 */ public static void main(String arg[]) { String s = "9+(3-1)*3+10/2"; ArrayList postfix = transform(s); for (int i = 0, len = postfix.size(); i < len; i++) { System.out.println(postfix.get(i)); } calculate(postfix); } /** * 将中缀表达式转换成后缀表达式 */ public static ArrayList transform(String prefix) { System.out.println("transform"); int i, len = prefix.length();// 用字符串保存前缀表达式 prefix = prefix + '#';// 让前缀表达式以'#'结尾 Stack<Character> stack = new Stack<Character>();// 保存操作符的栈 stack.push('#');// 首先让'#'入栈 ArrayList postfix = new ArrayList();//后缀数组集合 // 保存后缀表达式的列表,可能是数字，也可能是操作符 for (i = 0; i < len + 1; i++) { System.out.println(i + " " + prefix.charAt(i)); if (Character.isDigit(prefix.charAt(i))) {// 当前字符是一个数字 if (Character.isDigit(prefix.charAt(i + 1))) {// 当前字符的下一个字符也是数字(两位数) postfix.add(10 * (prefix.charAt(i) - '0') + (prefix.charAt(i + 1) - '0')); i++;// 序号加1 } else {// 当前字符的下一个字符不是数字(一位数) postfix.add((prefix.charAt(i) - '0')); } } else {// 当前字符是一个操作符 switch (prefix.charAt(i)) { case '(':// 如果是开括号 stack.push(prefix.charAt(i));// 开括号只放入到栈中，不放入到后缀表达式中 break; case ')':// 如果是闭括号 while (stack.peek() != '(') { postfix.add(stack.pop());// 闭括号不入栈，将前一个不是“）”的操作符入栈 } stack.pop();// '('出栈 break; default:// 默认情况下:+ - * / while (stack.peek() != '#' && compare(stack.peek(), prefix.charAt(i))) {// 比较运算符之间的优先级 postfix.add(stack.pop());// 不断弹栈，直到当前的操作符的优先级高于栈顶操作符 } if (prefix.charAt(i) != '#') {// 如果当前的操作符不是'#'(结束符)，那么入操作符栈 stack.push(prefix.charAt(i));// 最后的标识符'#'是不入栈的 } break; } } } return postfix; } /** * 比较运算符之间的优先级 * 如果是peek优先级高于cur，返回true，默认都是peek优先级要低 */ public static boolean compare(char peek, char cur) { if (peek == '*' && (cur == '+' || cur == '-' || cur == '/' || cur == '*')) {// 如果cur是'('，那么cur的优先级高,如果是')'，是在上面处理 return true; } else if (peek == '/' && (cur == '+' || cur == '-' || cur == '*' || cur == '/')) { return true; } else if (peek == '+' && (cur == '+' || cur == '-')) { return true; } else if (peek == '-' && (cur == '+' || cur == '-')) { return true; } else if (cur == '#') {// 这个很特别，这里说明到了中缀表达式的结尾，那么就要弹出操作符栈中的所有操作符到后缀表达式中 return true;// 当cur为'#'时，cur的优先级算是最低的 } return false;// 开括号是不用考虑的，它的优先级一定是最小的,cur一定是入栈 } /** * 计算后缀表达式 */ public static double calculate(ArrayList postfix) {// 后缀表达式的运算顺序就是操作符出现的先后顺序 System.out.println("calculate"); int i, res = 0, size = postfix.size(); Stack<Integer> stackNum = new Stack<Integer>(); for (i = 0; i < size; i++) { if (postfix.get(i).getClass() == Integer.class) {// 判断如果是操作数 stackNum.push((Integer) postfix.get(i));//入栈 System.out.println("push" + " " + (Integer) postfix.get(i)); } else {// 如果是操作符 System.out.println((Character) postfix.get(i)); int a = stackNum.pop();// 出栈后一个操作数 int b = stackNum.pop();// 出栈前一个操作数 switch ((Character) postfix.get(i)) { case '+': res = b + a; System.out.println("+ " + a + " " + b); break; case '-': res = b - a; System.out.println("- " + a + " " + b); break; case '*': res = b * a; System.out.println("* " + a + " " + b); break; case '/': res = b / a; System.out.println("/ " + a + " " + b); break; } stackNum.push(res);//操作后的结果入栈 System.out.println("push" + " " + res); } } res = stackNum.pop();//结果 System.out.println("结果： " + " " + res); return res; } }
栈与递归
栈：限定仅在表尾进行插入和删除操作的线性表。
递归：直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。
函数的递归调用和普通函数调用是一样的。当程序执行到某个函数时，将这个函数进行入栈操作，在入栈之前，通常需要完成三件事。
1、将所有的实参、返回地址等信息传递给被调函数保存。
2、为被调函数的局部变量分配存储区。
3、将控制转移到北调函数入口。
当一个函数完成之后会进行出栈操作，出栈之前同样要完成三件事。
1、保存被调函数的计算结果。
2、释放被调函数的数据区。
3、依照被调函数保存的返回地址将控制转移到调用函数。
上述操作必须通过栈来实现，即将整个程序的运行空间安排在一个栈中。每当运行一个函数时，就在栈顶分配空间，函数退出后，释放这块空间。所以当前运行的函数一定在栈顶。
（注：摘自严蔚敏等人的数据结构c语言版）
JVM内存栈
JVM：在java编译器和os平台之间的虚拟处理器，JVM会递归调用为例，一个栈帧包括局部变量表、操作数栈、栈数据区
编辑
编辑
