栈的介绍

栈的英文为(stack)栈是一个先入后出(FILO-First In Last Out)的有序列表。栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的 一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元 素最先删除，最先放入的元素最后删除图解方式说明出栈(pop)和入栈(push)的概念

栈的应用场景

子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。 3)表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。二叉树的遍历。图形的深度优先(depth 一first)搜索法。

栈的快速入门

数组模拟栈

用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来储存栈的数据内容，下面我们就用数组模拟栈的出栈，入栈等操作。实现思路分析,并画出示意图 使用数组来模拟栈定义一个 top 来表示栈顶，初始化 为 -1入栈的操作，当有数据加入到栈时， top++; stack[top] = data;出栈的操作， int value = stack[top]; top–, return value

代码实现

import java.util.Scanner; public class ArrayStackDemo { public static void main(String[] args) { //测试一下ArrayStack 是否正确 //先创建一个ArrayStack对象->表示栈 ArrayStack stack = new ArrayStack(4); String key = ""; boolean loop = true; //控制是否退出菜单 Scanner scanner = new Scanner(System.in); while(loop) { System.out.println("show: 表示显示栈"); System.out.println("exit: 退出程序"); System.out.println("push: 表示添加数据到栈(入栈)"); System.out.println("pop: 表示从栈取出数据(出栈)"); System.out.println("请输入你的选择"); key = scanner.next(); switch (key) { case "show": stack.list(); break; case "push": System.out.println("请输入一个数"); int value = scanner.nextInt(); stack.push(value); break; case "pop": try { int res = stack.pop(); System.out.printf("出栈的数据是 %d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case "exit": scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~~"); } } //定义一个 ArrayStack 表示栈 class ArrayStack { private int maxSize; // 栈的大小 private int[] stack; // 数组，数组模拟栈，数据就放在该数组 private int top = -1;// top表示栈顶，初始化为-1 //构造器 public ArrayStack(int maxSize) { this.maxSize = maxSize; stack = new int[this.maxSize]; } //栈满 public boolean isFull() { return top == maxSize - 1; } //栈空 public boolean isEmpty() { return top == -1; } //入栈-push public void push(int value) { //先判断栈是否满 if(isFull()) { System.out.println("栈满"); return; } top++; stack[top] = value; } //出栈-pop, 将栈顶的数据返回 public int pop() { //先判断栈是否空 if(isEmpty()) { //抛出异常 throw new RuntimeException("栈空，没有数据~"); } int value = stack[top]; top--; return value; } //显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据 public void list() { if(isEmpty()) { System.out.println("栈空，没有数据~~"); return; } //需要从栈顶开始显示数据 for(int i = top; i >= 0 ; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); } } }

单链表模拟栈

思路： 1.添加（push）：把数据永远插入到head的下一个位置 NewheroNode.next = temp.next; head.next = NewheroNode; 2.遍历（list）：单链表普通遍历 3取出（pop）：head.next就是了再head.next = head.next.next;连接到下一个节点

代码实现

public class LinkStackDemo { public static void main(String[] args) { // TODO 自动生成的方法存根 HeroNode hero1 = new HeroNode(1, "宋江", "及时雨"); HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吴用", "智多星"); HeroNode hero4 = new HeroNode(4, "林冲", "豹子头"); // 创建要给链表 LinkStack singleLinkedList = new LinkStack(); // 加入 singleLinkedList.push(hero1); singleLinkedList.push(hero2); singleLinkedList.push(hero3); singleLinkedList.push(hero4); singleLinkedList.pop(); System.out.println("原来链表的情况~~"); singleLinkedList.list(); } } class LinkStack { private HeroNode head = new HeroNode(0, "", ""); // 返回头节点 public HeroNode getHead() { return head; } public boolean isEmpty() { return head.next == null; } public void push(HeroNode heroNode) { // 因为head节点不能动，因此我们需要一个辅助遍历 temp HeroNode temp = head; // 遍历链表，找到最后 if (isEmpty()){ head.next = heroNode; } else { heroNode.next = temp.next; head.next = heroNode; } } public void list() { // 判断链表是否为空 if (head.next == null) { System.out.println("链表为空"); return; } // 因为头节点，不能动，因此我们需要一个辅助变量来遍历 HeroNode temp = head.next; while (true) { // 判断是否到链表最后 if (temp == null) { break; } // 输出节点的信息 System.out.println(temp); // 将temp后移， 一定小心 temp = temp.next; } } public void pop() { System.out.printf(" 取出%d 节点\n", head.next.no); head.next = head.next.next; } } // 定义HeroNode ， 每个HeroNode 对象就是一个节点 class HeroNode { public int no; public String name; public String nickname; public HeroNode next; // 指向下一个节点 // 构造器 public HeroNode(int no, String name, String nickname) { this.no = no; this.name = name; this.nickname = nickname; } // 为了显示方法，我们重新toString @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; } }

栈实现综合计算器(中缀表达式)

栈的一个实际需求

请输入一个表达式 计算式:[722-5+1-5+3-3] 点击计算【如下图】 请问: 计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算,因为我们看这个算式 7 * 2 * 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。-> 栈

思路分析(图解)

使用栈完成表达式的计算 思路

通过一个 index 值（索引），来遍历我们的表达式如果我们发现是一个数字, 就直接入数栈如果发现扫描到是一个符号, 就分如下情况 3.1 如果发现当前的符号栈为 空，就直接入栈 3.2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.最后在数栈只有一个数字，就是表达式的结果

验证： 3+2*6-2 = 13

先实现一位数的运算扩展到多位数的运算

步骤解析： ①扫描到3放入数栈 ②扫描到+且符号栈为 空，就直接入符号栈 ③扫描到2直接入数栈 ④扫描到 * 因为 * > + 直接入符号栈 ⑤扫描到 - 因为-<*所以pop出2和6和 * 进行运算然后把12放入数栈，再将-放入符号栈 ⑥扫描到2直接入数栈 ⑦扫描完毕后pop2和12和-号运算（后面弹出的数减去前面弹出的数）再把10放入数栈 ⑧pop10和3和+一起运算得到13。

代码实现

public class Calculator { public static void main(String[] args) { // 根据前面老师思路，完成表达式的运算 String expression = "7*2*2-5+1-5+3-4"; // 15//如何处理多位数的问题？ // 创建两个栈，数栈，一个符号栈 ArrayStack2 numStack = new ArrayStack2(10); ArrayStack2 operStack = new ArrayStack2(10); // 定义需要的相关变量 int index = 0;// 用于扫描 int num1 = 0; int num2 = 0; int oper = 0; int res = 0; char ch = ' '; // 将每次扫描得到char保存到ch String keepNum = ""; // 用于拼接 多位数 // 开始while循环的扫描expression while (true) { // 依次得到expression 的每一个字符 ch = expression.substring(index, index + 1).charAt(0); // 判断ch是什么，然后做相应的处理 if (operStack.isOper(ch)) {// 如果是运算符 // 判断当前的符号栈是否为空 if (!operStack.isEmpty()) { // 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数, // 在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈 if (operStack.priority(ch) <= operStack.priority(operStack.peek())) { num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = numStack.cal(num1, num2, oper); // 把运算的结果如数栈 numStack.push(res); // 然后将当前的操作符入符号栈 operStack.push(ch); } else { // 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈. operStack.push(ch); } } else { // 如果为空直接入符号栈.. operStack.push(ch); // 1 + 3 } } else { // 如果是数，则直接入数栈 // numStack.push(ch - 48); //? "1+3" '1' => 1 // 分析思路 // 1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数 // 2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈 // 3. 因此我们需要定义一个变量 字符串，用于拼接 // 处理多位数 keepNum += ch; // 如果ch已经是expression的最后一位，就直接入栈 if (index == expression.length() - 1) { numStack.push(Integer.parseInt(keepNum)); } else { // 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈 // 注意是看后一位，不是index++ if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) { // 如果后一位是运算符，则入栈 keepNum = "1" 或者 "123" numStack.push(Integer.parseInt(keepNum)); // 重要的!!!!!!, keepNum清空 keepNum = ""; } } } // 让index + 1, 并判断是否扫描到expression最后. index++; if (index >= expression.length()) { break; } } // 当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行. while (true) { // 如果符号栈为空，则计算到最后的结果, 数栈中只有一个数字【结果】 if (operStack.isEmpty()) { break; } num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = numStack.cal(num1, num2, oper); numStack.push(res);// 入栈 } // 将数栈的最后数，pop出，就是结果 int res2 = numStack.pop(); System.out.printf("表达式 %s = %d", expression, res2); } } //先创建一个栈,直接使用前面创建好 //定义一个 ArrayStack2 表示栈, 需要扩展功能 class ArrayStack2 { private int maxSize; // 栈的大小 private int[] stack; // 数组，数组模拟栈，数据就放在该数组 private int top = -1;// top表示栈顶，初始化为-1 // 构造器 public ArrayStack2(int maxSize) { this.maxSize = maxSize; stack = new int[this.maxSize]; } // 增加一个方法，可以返回当前栈顶的值, 但是不是真正的pop public int peek() { return stack[top]; } // 栈满 public boolean isFull() { return top == maxSize - 1; } // 栈空 public boolean isEmpty() { return top == -1; } // 入栈-push public void push(int value) { // 先判断栈是否满 if (isFull()) { System.out.println("栈满"); return; } top++; stack[top] = value; } // 出栈-pop, 将栈顶的数据返回 public int pop() { // 先判断栈是否空 if (isEmpty()) { // 抛出异常 throw new RuntimeException("栈空，没有数据~"); } int value = stack[top]; top--; return value; } // 显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据 public void list() { if (isEmpty()) { System.out.println("栈空，没有数据~~"); return; } // 需要从栈顶开始显示数据 for (int i = top; i >= 0; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); } } // 返回运算符的优先级，优先级是程序员来确定, 优先级使用数字表示 // 数字越大，则优先级就越高. public int priority(int oper) { if (oper == '*' || oper == '/') { return 1; } else if (oper == '+' || oper == '-') { return 0; } else { return -1; // 假定目前的表达式只有 +, - , * , / } } // 判断是不是一个运算符 public boolean isOper(char val) { return val == '+' || val == '-' || val == '*' || val == '/'; } // 计算方法 public int cal(int num1, int num2, int oper) { int res = 0; // res 用于存放计算的结果 switch (oper) { case '+': res = num1 + num2; break; case '-': res = num2 - num1;// 注意顺序 break; case '*': res = num1 * num2; break; case '/': res = num2 / num1; break; default: break; } return res; } }

判断多位数

keepNum += ch; // 如果ch已经是expression的最后一位，就直接入栈 if (index == expression.length() - 1) { numStack.push(Integer.parseInt(keepNum)); } else { // 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈 // 注意是看后一位，不是index++ if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) { // 如果后一位是运算符，则入栈 keepNum = "1" 或者 "123" numStack.push(Integer.parseInt(keepNum)); // 重要的!!!!!!, keepNum清空 keepNum = ""; } }