浅谈网站的主色调设计,网站建设客户常见问题集锦,侧边导航 wordpress,wordpress添加微信公众号数据结构和算法-栈
1. 栈的介绍
栈的介绍#xff1a;
栈的英文为(stack)栈是一个先入后出的有序列表栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端#xff0c;为变化的一端#xff0c;称为栈顶#xff0c;另一端为固…数据结构和算法-栈
1. 栈的介绍
栈的介绍
栈的英文为(stack)栈是一个先入后出的有序列表栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端为变化的一端称为栈顶另一端为固定的一端称为栈底。根据栈的定义可知最先放入栈中元素的栈底最后放入的元素在栈顶而删除元素刚好相反最后放入的元素最先删除最先放入的元素最后删除。出栈(POP)和入栈(PUSH)的概念
注意栈和上次介绍的队列是不同的
栈的栈底是固定的先入后出。一个指针而队列的首尾都是不固定的先入先出。两个指针 图1 出栈和入栈示意图 2. 栈的应用场景
子程序的调用在跳往子程序前会先将下个指令的地址存到堆栈中直到子程序执行完后再将地址取出以回到原来的程序中。处理递归调用和子程序的调用类似只是除了存储下一个指令的地址外也将参数、区域变量等数据存入堆栈中。表达式的转换[中缀表达式转后缀表达式]与求值实际解决。二叉树的遍历图形的深度优先depth-first搜索法。
3. 栈的快速入门
3.1 用数组模拟栈
用数组模拟栈的使用由于栈是一种有序列表可以使用数组的结构来存储栈的数据内容。下面用数组模拟栈的出栈、入栈等操作 实现栈的思路分析
使用栈的思路分析定义一个top来表示栈顶初始化为-1入栈的操作当有数据加入到栈时top;stack[top]data;出栈的操作int value stack[top];top–;return value;
韩老师代码如下
//定义一个ArrayStack 表示栈
class ArrayStack {private int maxSize; //栈的大小private int[] stack; //数组 数组模拟栈 数据就放在该数组private int top -1; //top表示栈顶 初始化为-1 arr[top] 是栈的最后一个有效数据public ArrayStack(int maxSize) {this.maxSize maxSize;stack new int[maxSize];}//栈满public boolean isFull() {return top maxSize - 1;}//栈空public boolean isEmpty() {return top -1;}//入栈-pushpublic void push(int value) {//先判断是否满if (isFull()) {System.out.println(栈满);return;}stack[top] value;}//出栈-pop 将栈顶的数据返回public int pop() {//先判断栈是否空if (isEmpty()) {//抛出异常处理throw new RuntimeException(栈为空);}return stack[top--];}//显示栈的情况 遍历时 需要从栈顶开始显示public void list() {//先判断栈是否空if (isEmpty()) {//抛出异常处理throw new RuntimeException(栈为空);}for (int i top; i 0; i--) {System.out.println(stack[i]);}}
}3.2 课堂作业-用链表模拟栈
自己写的代码如下
//无头结点的单链表模拟栈
class ListStack {private final int maxSize; //栈的最大容量private Node list new Node(0); //栈的第一个存储空间private int top -1; //指向栈顶public ListStack(int maxSize) {//maxSize 最大容量this.maxSize maxSize;Node temp list;for (int i 1; i maxSize; i) {temp.setNext(new Node(i)); //将上一个节点连接新节点temp temp.getNext(); //将temp指向新节点(链表的最后一个节点)}}//判断栈是否满了public boolean isFull() {return top maxSize - 1;}//判断栈是否为空public boolean isEmpty() {return top -1;}//入栈public void push(int value) {if (isFull()) { //如果满了System.out.println(满了兄弟);return;//退出函数}Node temp list;top;while (temp.getNo() ! top) {//当找到时退出循环temp temp.getNext();}//当退出循环时 temp就是目标temp.setValue(value);}//出栈-pop 将栈顶的数据返回public int pop(){if (isEmpty()){ //说明为空throw new RuntimeException(空了);}Node temp list;while (temp.getNo() ! top) {//当找到时退出循环temp temp.getNext();}top--;return temp.getValue();}//显示栈的情况 遍历时 需要从栈顶开始显示public void show(){if (isEmpty()){ //说明为空System.out.println(空的);}for (int i 0; i top 1; i) {Node temp list;for (int j 0; j top - i; j) {temp temp.getNext();}System.out.println(temp.getValue());}}
}//单链表的节点
class Node {private int no; //编号private int value; //保存的值private Node next; //next域public Node(int no) {this.no no;}public int getNo() {return no;}public void setNo(int no) {this.no no;}public int getValue() {return value;}public void setValue(int value) {this.value value;}public Node getNext() {return next;}public void setNext(Node next) {this.next next;}Overridepublic String toString() {return Node{ no no , value value , next ((next null) ? null : next.hashCode()) };}
}看到弹幕说有直接头插法试了一下发现确实更好
//有头结点的单链表模拟栈
class ListStack2 {private final int maxSize; //栈的最大容量private Node2 head new Node2(); //头节点private int top -1; //指向栈顶public ListStack2(int maxSize) {this.maxSize maxSize;}//判断栈是否满了public boolean isFull() {return top maxSize - 1;}//判断栈是否为空public boolean isEmpty() {return top -1;}//入栈public void push(int value) {if (isFull()) { //如果满了System.out.println(满了兄弟);return;//退出函数}Node2 temp new Node2(value);//创建新节点//将此节点插入到头节点和旧的第一个节点中 成为新的第一个节点(栈顶)temp.setNext(head.getNext());head.setNext(temp);top;//计数加一}//出栈-pop 将栈顶的数据返回public int pop() {if (isEmpty()) { //说明为空throw new RuntimeException(空了);}top--; //计数减一int value head.getNext().getValue(); //得到返回值//将第一个节点从链表中删除head.setNext(head.getNext().getNext()); //将头节点的next指向第二个节点 作为新的第一个节点return value;}//显示栈的情况 遍历时 需要从栈顶开始显示public void show() {if (isEmpty()) { //说明为空System.out.println(空的);return;}Node2 temp head.getNext();while (temp ! null) {//遍历完所有节点System.out.println(temp.getValue());temp temp.getNext();//节点后移}}
}//单链表的节点
class Node2 {private int value; //保存的值private Node2 next; //next域public Node2(int value) {this.value value;}public Node2() {}public int getValue() {return value;}public void setValue(int value) {this.value value;}public Node2 getNext() {return next;}public void setNext(Node2 next) {this.next next;}
}4. 栈实现综合计算器 图2 思路图 使用栈完成表达式的计算思路
通过一个index值索引来遍历我们的表达式如果我们发现是一个数字,就直接入数栈如果发现扫描到是一个符号,就分如下情况 如果发现当前的符号栈为空就直接入栈如果符号栈有操作符就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符就需要从数栈中pop出两个数,在从符号栈中pop出一个符号进行运算将得到结果入数栈然后将当前的操作符入符号栈如果当前的操作符的优先级大于栈中的操作符就直接入符号栈. 当表达式扫描完毕就顺序的从数栈和符号栈中pop出相的数和符号并运行.最后在数栈只有一个数字就是表达式的结果
自己写的多位数代码如下
package com.atguigu.stack;/*** author 小小低头哥* version 1.0*/public class Calculator {public static void main(String[] args) {//根据前面思路 完成表达式的运算
// String expression 22*3-2*1-12-3-2-3;
// String expression 231-4-3-22*20*450/5064-3-4-2*2;String expression 30*2-6*91;//创建两个栈 数栈、符号栈ArrayStack2 numStack new ArrayStack2(30);ArrayStack2 operStack new ArrayStack2(50);//定义需要的相关变量int index 0; //用于扫描int num1 0;int num2 0;int oper 0;int res 0;char ch ; //将每次扫描得到char保存到chint count 0; //计数器 记录是几位数 放在符号栈的符号中//开始while循环的扫描expressionwhile (true) {//依次得到expression的每一个字符ch expression.substring(index, index 1).charAt(0);//判断ch是什么 然后做出相应的处理if (operStack.isOper(ch)) { //如果是运算符//判断当前的符号栈是否为空if (!operStack.isEmpty()) { //不为空则一个个判断operStack.push(count); //先放进去//if (operStack.priority(ch) operStack.priority(operStack.peek()))while (operStack.priority(ch) operStack.priority(operStack.peek())) {//下面num1、oper、num2弹出的顺序不能变num1 numStack.popN(operStack.pop()); //得到符号位前面的整数 并弹出符号栈中对应的数字标志oper operStack.pop(); //出栈num2 numStack.popN(operStack.pop());res numStack.cal(num1, num2, oper);//把运算的结果放入数栈numStack.push(res);count 1;if (!operStack.isEmpty()) { //说明前面没有运算符了 自然也不需要更新了operStack.pop(); //把前一个运算符后面的数字位数去掉 因为此时已经变成res了 由于res是一个整体 所以相当于count1operStack.push(count); //更新前一个运算符后面的数字位数}else {break;}}}//为空或者判断完毕后 把当前符号入符号栈operStack.push(count); //把符号前面的数是几位数记录下来 并放在ch的前面operStack.push(ch);count 0; //重新置零} else {//如果是数 则直接入数栈count; //数字数加一numStack.push(ch - 48); //转换为数字}//让index 1 并判断是否扫描到expression最后index;if (index expression.length()) { //扫描结束operStack.push(count); //扫描结束最后一个肯定是数字 需要把此数字的位数压入到符号栈break;}}while (true) {//下面num1、oper、num2弹出的顺序不能变num1 numStack.popN(operStack.pop()); //得到符号位前面的整数 并弹出符号栈中对应的数字标志oper operStack.pop(); //出栈num2 numStack.popN(operStack.pop());if (!operStack.isEmpty() oper - operStack.peek() -) { //如果此时的操作符和上一个操作符都是负号//那么说明此时不是相减 而是相加res numStack.cal(num1, num2, );} else if (!operStack.isEmpty() oper operStack.peek() -) { //则应是num2-num1res numStack.cal(num1, num2, -);} else {res numStack.cal(num1, num2, oper);}numStack.push(res); //入栈//如果符号栈为空 则计算到最后的结果数栈中只有一个数字if (operStack.isEmpty()) {break;}operStack.pop(); //把前一个运算符后面的数字位数去掉 因为此时已经变成res了operStack.push(1); //更新前一个运算符后面的数字位数}System.out.println(expression 表达式的结果是: numStack.pop());}
}//先定义一个栈 直接使用前面创建好
//定义一个ArrayStack表示栈class ArrayStack2 {private int maxSize; //栈的大小private int[] stack; //数组 数组模拟栈 数据就放在该数组private int top -1; //top表示栈顶 初始化为-1 arr[top] 是栈的最后一个有效数据public ArrayStack2(int maxSize) {this.maxSize maxSize;stack new int[maxSize];}//栈满public boolean isFull() {return top maxSize - 1;}//栈空public boolean isEmpty() {return top -1;}//入栈-pushpublic void push(int value) {//先判断是否满if (isFull()) {System.out.println(栈满);return;}stack[top] value;}//出栈 连续出栈几个并组成数字 为数栈准备public int popN(int n) {int res 0;for (int i 0; i n; i) {if (i 0) {res res pop();} else {res res pop() * (int) Math.pow(10, i); //从个位、十位等依次入手}}return res;}//出栈-pop 将栈顶的数据返回public int pop() {//先判断栈是否空if (isEmpty()) {//抛出异常处理throw new RuntimeException(栈为空);}return stack[top--];}//显示栈的情况 遍历时 需要从栈顶开始显示public void list() {//先判断栈是否空if (isEmpty()) {//抛出异常处理throw new RuntimeException(栈为空);}for (int i top; i 0; i--) {System.out.println(stack[i]);}}//返回运算符的优先级 优先级是程序员确定的 优先级使用数组表示//数字越大 则优先级越高public int priority(int oper) {if (oper * || oper /) {return 1;} else if (oper || oper -) {return 0;} else {return -1; //假定目前表达式只有加减乘除}}//增加一个方法 可以返回当前栈顶的值 但是不是真正的poppublic int peek() {return stack[top - 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;}}韩老师写的多位数代码如下
package com.atguigu.stack;/*** author 小小低头哥* version 1.0*/
public class Calculator2 {public static void main(String[] args) {//根据前面思路 完成表达式的运算String expression 30*2-6*91;//创建两个栈 数栈、符号栈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保存到chString keepNum ; //用于拼接多位数//开始while循环的扫描expressionwhile (true) {//依次得到expression的每一个字符ch expression.substring(index, index 1).charAt(0);//判断ch是什么 然后做出相应的处理if (operStack.isOper(ch)) { //如果是运算符//判断当前的符号栈是否为空if (!operStack.isEmpty()) { //不为空则一个个判断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);}} else {//如果是数 则直接入数栈//分析思路//1. 当处理多位数时 不能发现一个数就立即入栈 因为可能是多位数//2. 在处理数需要翔expression的表达式的index后再看一位 如果是数就进行扫描 如果是符号才入栈//3. 因此需要定义一个变量 用于拼接//处理多位数keepNum ch;//如果ch已经是expression的最后一位 就直接入栈if (index expression.length() - 1) {numStack.push(Integer.parseInt(keepNum));} else {//判断下一个字符是不是数字 如果是数字 就继续扫描 如果是运算符 则入栈//注意看后一位 不是indexif (operStack.isOper(expression.substring(index 1, index 2).charAt(0))) {//如果后一位是运算符 则入栈numStack.push(Integer.parseInt(keepNum));keepNum ; //清空}}}//让index 1 并判断是否扫描到expression最后index;if (index expression.length()) { //扫描结束break;}}while (true) {//如果符号栈为空 则计算到最后的结果数栈中只有一个数字if (operStack.isEmpty()) {break;}num1 numStack.pop();num2 numStack.pop();oper operStack.pop(); //出栈res numStack.cal(num1, num2, oper);numStack.push(res); //入栈}System.out.println(expression 表达式的结果是: numStack.pop());}
}//先定义一个栈 直接使用前面创建好
//定义一个ArrayStack表示栈class ArrayStack2 {private int maxSize; //栈的大小private int[] stack; //数组 数组模拟栈 数据就放在该数组private int top -1; //top表示栈顶 初始化为-1 arr[top] 是栈的最后一个有效数据public ArrayStack2(int maxSize) {this.maxSize maxSize;stack new int[maxSize];}//栈满public boolean isFull() {return top maxSize - 1;}//栈空public boolean isEmpty() {return top -1;}//入栈-pushpublic void push(int value) {//先判断是否满if (isFull()) {System.out.println(栈满);return;}stack[top] value;}//出栈-pop 将栈顶的数据返回public int pop() {//先判断栈是否空if (isEmpty()) {//抛出异常处理throw new RuntimeException(栈为空);}return stack[top--];}//显示栈的情况 遍历时 需要从栈顶开始显示public void list() {//先判断栈是否空if (isEmpty()) {//抛出异常处理throw new RuntimeException(栈为空);}for (int i top; i 0; i--) {System.out.println(stack[i]);}}//返回运算符的优先级 优先级是程序员确定的 优先级使用数组表示//数字越大 则优先级越高public int priority(int oper) {if (oper * || oper /) {return 1;} else if (oper || oper -) {return 0;} else {return -1; //假定目前表达式只有加减乘除}}//增加一个方法 可以返回当前栈顶的值 但是不是真正的poppublic int peek() {return stack[top];}//判断是不是一个运算符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;}}4.1 课堂作业-加入小括号
在前面的基础上加上了判断小括号的功能觉得还行 不过没加入判断负数的功能
package com.atguigu.stack;/*** author 小小低头哥* version 1.0*/public class Calculator {public static void main(String[] args) {//根据前面思路 完成表达式的运算
// String expression 22*3-2*1-12-3-2-3;
// String expression 231-4-3-22*20*450/5064-3-4-2*2;String expression 30*2-(6*9)-(15*4)(4*6);//创建两个栈 数栈、符号栈ArrayStack2 numStack new ArrayStack2(30);ArrayStack2 operStack new ArrayStack2(50);//定义需要的相关变量int index 0; //用于扫描int num1 0;int num2 0;int oper 0;int res 0;char ch ; //将每次扫描得到char保存到chint count 0; //计数器 记录是几位数 放在符号栈的符号中boolean flag false; //flag为真时 说明接收到了左、右括号 且还没有接收到符号位//开始while循环的扫描expressionwhile (true) {//依次得到expression的每一个字符ch expression.substring(index, index 1).charAt(0);//判断ch是什么 然后做出相应的处理if (operStack.isOper(ch)) { //如果是运算符//判断当前的符号栈是否为空if (!operStack.isEmpty()) { //不为空则一个个判断if (!flag) {//如果上一个是 ( 则不用放进去operStack.push(count); //先放进去}flag false;//if (operStack.priority(ch) operStack.priority(operStack.peek()))while (operStack.priority(ch) operStack.priority(operStack.peek(1))) {//0的优先权最小 不会进入循环 正要如此//下面num1、oper、num2弹出的顺序不能变num1 numStack.popN(operStack.pop()); //得到符号位前面的整数 并弹出符号栈中对应的数字标志oper operStack.pop(); //出栈num2 numStack.popN(operStack.pop());res numStack.cal(num1, num2, oper);//把运算的结果放入数栈numStack.push(res);count 1;//前面还有运算符了 需要更新 或者计算完括号中的数if (!operStack.isEmpty() operStack.peek(0) ! 0) {operStack.pop(); //把前一个运算符后面的数字位数去掉 因为此时已经变成res了 由于res是一个整体 所以相当于count1operStack.push(count); //更新前一个运算符后面的数字位数} else {break;}}}//为空或者判断完毕后 把当前符号入符号栈operStack.push(count); //把符号前面的数是几位数记录下来 并放在ch的前面operStack.push(ch);count 0; //重新置零} else if (ch () { //按数学规矩 (的前面一个肯定是运算符flag true;operStack.push(0); //把零送进去当作是起点} else if (ch )) {flag true;operStack.push(count); //)前必然是数字 所以这里先送进去一个计数器while (true) {//说明还没计算完括号内的运算//下面num1、oper、num2弹出的顺序不能变num1 numStack.popN(operStack.pop()); //得到符号位前面的整数 并弹出符号栈中对应的数字标志oper operStack.pop(); //出栈num2 numStack.popN(operStack.pop());if (operStack.peek(0)! 0 oper - operStack.peek(1) -) { //如果此时的操作符和上一个操作符都是负号//那么说明此时不是相减 而是相加res numStack.cal(num1, num2, );} else if (operStack.peek(0)! 0 oper operStack.peek(1) -) { //则应是num2-num1res numStack.cal(num1, num2, -);} else {res numStack.cal(num1, num2, oper);}numStack.push(res); //入栈//如果括号中的数计算完毕if (operStack.peek(0) 0) {operStack.pop(); //把标志位给弹出来operStack.push(1); //因为()的结果是一个整数 所以把1送进去作为()整体的数的个数break;}operStack.pop(); //把前一个运算符后面的数字位数去掉 因为此时已经变成res了operStack.push(1); //更新前一个运算符后面的数字位数}} else {//如果是数 则直接入数栈count; //数字数加一numStack.push(ch - 48); //转换为数字}//让index 1 并判断是否扫描到expression最后index;if (index expression.length() ) { //扫描结束//扫描结束最后一个肯定是数字 需要把此数字的位数压入到符号栈if( ch ! )){ //但是如果最后是以)结束 则由于括号计算中已经把1插进去了 不需要了operStack.push(count);}break;}}while (true) {//下面num1、oper、num2弹出的顺序不能变num1 numStack.popN(operStack.pop()); //得到符号位前面的整数 并弹出符号栈中对应的数字标志oper operStack.pop(); //出栈num2 numStack.popN(operStack.pop());if (!operStack.isEmpty() oper - operStack.peek(1) -) { //如果此时的操作符和上一个操作符都是负号//那么说明此时不是相减 而是相加res numStack.cal(num1, num2, );} else if (!operStack.isEmpty() oper operStack.peek(1) -) { //则应是num2-num1res numStack.cal(num1, num2, -);} else {res numStack.cal(num1, num2, oper);}numStack.push(res); //入栈//如果符号栈为空 则计算到最后的结果数栈中只有一个数字if (operStack.isEmpty()) {break;}operStack.pop(); //把前一个运算符后面的数字位数去掉 因为此时已经变成res了operStack.push(1); //更新前一个运算符后面的数字位数}System.out.println(expression 表达式的结果是: numStack.pop());}
}//先定义一个栈 直接使用前面创建好
//定义一个ArrayStack表示栈class ArrayStack2 {private int maxSize; //栈的大小private int[] stack; //数组 数组模拟栈 数据就放在该数组private int top -1; //top表示栈顶 初始化为-1 arr[top] 是栈的最后一个有效数据public ArrayStack2(int maxSize) {this.maxSize maxSize;stack new int[maxSize];}//栈满public boolean isFull() {return top maxSize - 1;}//栈空public boolean isEmpty() {return top -1;}//入栈-pushpublic void push(int value) {//先判断是否满if (isFull()) {System.out.println(栈满);return;}stack[top] value;}//出栈 连续出栈几个并组成数字 为数栈准备public int popN(int n) {int res 0;for (int i 0; i n; i) {if (i 0) {res res pop();} else {res res pop() * (int) Math.pow(10, i); //从个位、十位等依次入手}}return res;}//出栈-pop 将栈顶的数据返回public int pop() {//先判断栈是否空if (isEmpty()) {//抛出异常处理throw new RuntimeException(栈为空);}return stack[top--];}//显示栈的情况 遍历时 需要从栈顶开始显示public void list() {//先判断栈是否空if (isEmpty()) {//抛出异常处理throw new RuntimeException(栈为空);}for (int i top; i 0; i--) {System.out.println(stack[i]);}}//返回运算符的优先级 优先级是程序员确定的 优先级使用数组表示//数字越大 则优先级越高public int priority(int oper) {if (oper * || oper /) {return 1;} else if (oper || oper -) {return 0;} else {return -1; //假定目前表达式只有加减乘除}}//增加一个方法 可以返回当前栈顶的第n个值 但是不是真正的poppublic int peek(int n) {return stack[top - n];}//判断是不是一个运算符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;}}
