栈(stack)的定义
? ? ? ? ①栈是一个先入后出的有序链表
? ? ? ? ②栈是限制线性表中元素的插入和删除只能在线性表的同一段进行的一种特殊线性表?
? ?允许插入和删除的一段 为变化的一端 称为 栈顶 另一端为固定的一端 称为栈底
? ? ? ? ③根据栈的定义可知 最先放入栈中元素在栈底 最后放入的元素在栈顶 而删除元素刚好相反
? ?最后放入的元素最先删除 最先放入的元素最后删除
?栈的应用场景? ? ? ??
?数组模拟栈
? ? ? ? ·定义一个top来表示栈顶 初始化为-1
? ? ? ? ·入栈的操作 当有数据加入到栈时 top++? ? ?stack[top]=data
? ? ? ? ·出栈的操作 int value = stack[top] top--??? return value
代码:
package zhan;
public class shuzumonizhan {
public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack(5);
arrayStack.push(1);
arrayStack.push(2);
arrayStack.push(3);
arrayStack.push(4);
arrayStack.list();
System.out.println();
System.out.println(arrayStack.pop());
}
}
class ArrayStack{
private int maxSize;//栈的大小
private int[] stack;//数组 数组模拟战 数据放在这里
private int 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;
}
//入栈
public void push(int value){
if(isFull()){
System.out.print("满啦！");
return;
}
top++;
stack[top] = value;
}
//出栈
public int pop(){
if(isEmpty()){
throw new RuntimeException("空的！");
}
int value = stack[top];
top--;
return value;
}
//遍历栈 遍历时 需要从栈顶开始显示
public void list(){
if(isEmpty()){
return;
}
for (int i = top; i >-1 ; i--) {
System.out.println("stack["+i+"]:"+stack[i]);
}
}
}
?
栈实现综合计算器
? ? ? ? 思路:? ? ? ?
????????
?代码(暂时不考虑括号):
package zhan;
public class jisuanqi {
public static void main(String[] args) {
String expression = "70+2*6-4";
//创建两个栈 一个数字 一个符号
ArrayStackJsq numStackJsq = new ArrayStackJsq(10);
ArrayStackJsq opeStackJsq = new ArrayStackJsq(10);
int index = 0;//用于扫描
int num1 = 0;
int num2 = 0;
int ope = 0;
int res = 0;
String temp = "";
char ch = ' ';//将每次扫描得到的char保存到ch
while(true){
//一次得到exp中的每个字符
ch = expression.substring(index,index+1).charAt(0);
//判断ch
if(opeStackJsq.isOper(ch)){
if(!opeStackJsq.isEmpty()){
//判断优先级
if(opeStackJsq.youxianji(ch)<=opeStackJsq.youxianji(opeStackJsq.zhanding())){
num1 = numStackJsq.pop();
num2 = numStackJsq.pop();
ope = opeStackJsq.pop();
res = numStackJsq.cal(num1,num2,ope);
numStackJsq.push(res);
opeStackJsq.push(ch);
}else {
opeStackJsq.push(ch);
}
}else {
opeStackJsq.push(ch);
}
}else {
//numStackJsq.push(ch-48);
//当处理多位数字时 处理数时 要向expression的index后再看一位 若是数 就再扫描 是符号再入栈
temp+=ch;
if(index==expression.length()-1){
numStackJsq.push(Integer.parseInt(temp));
}else{
//判断下一个字符是不是数字
if(opeStackJsq.isOper(expression.substring(index+1,index+2).charAt(0))){
numStackJsq.push(Integer.parseInt(temp));
temp="";
}
}
}
index++;
if(index==expression.length()){
break;
}
}
while (true){
//若符号栈为空则 计算结束
if(opeStackJsq.isEmpty()){
break;
}
num1 = numStackJsq.pop();
num2 = numStackJsq.pop();
ope = opeStackJsq.pop();
res = numStackJsq.cal(num1,num2,ope);
numStackJsq.push(res);
}
System.out.println(numStackJsq.pop());
}
}
class ArrayStackJsq{
private int maxSize;//栈的大小
private int[] stack;//数组 数组模拟战 数据放在这里
private int top = -1;
//读取栈顶的元素
public int zhanding(){
return stack[top];
}
//构造器
public ArrayStackJsq(int maxSize){
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
//判断栈满
public boolean isFull(){
return top == maxSize-1;
}
//
public boolean isEmpty(){
return top==-1;
}
//入栈
public void push(int value){
if(isFull()){
System.out.print("满啦！");
return;
}
top++;
stack[top] = value;
}
//出栈
public int pop(){
if(isEmpty()){
throw new RuntimeException("空的！");
}
int value = stack[top];
top--;
return value;
}
//遍历栈 遍历时 需要从栈顶开始显示
public void list(){
if(isEmpty()){
return;
}
for (int i = top; i >-1 ; i--) {
System.out.println("stack["+i+"]:"+stack[i]);
}
}
//返回运算符的优先级 优先级使用数组表示
//数字越大 优先值越高
public int youxianji(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 o){
int res = 0 ;
switch (o){
case '+':
res = num1+num2;
break;
case '-':
res = num2-num1;
break;
case '*':
res = num1*num2;
break;
case '/':
res = num2/num1;
}
return res;
}
}
前缀表达式(波兰表达式)
? ? ? ? 前缀表达式的运算符位于操作数之前
? ? ? ? eg: (3+4)*5-6的前缀表达式为-*3456
前缀表达式的计算机求值
? ? ? ? 从右到左扫描表达式 遇到数字时 将数字压入堆栈 遇到运算符时 弹出栈顶的两个数 用运算符对它们做相应的计算(栈顶元素 和 次栈顶元素) 并将结果入栈 重复上述过程直到表达式最左端 最后运算得出的值就是表达式的结果
????????
中缀表达式
?后缀表达式(逆波兰表达式)
? ? ? ? 后缀表达式与前缀表达式相似 只是运算符位于操作数之后
后缀表达式的计算机求值
? ? ? ? 从左至右 扫描表达式 遇到数字时 将数字压入堆栈 遇到运算符时 弹出栈顶的两个数 用运算符对它们做相应的计算(次顶元素和栈顶元素) 并将结果入栈 重复上述过程直到表达式最右端 最后运算得出的值即为表达式的结果? ? ? ??
?逆波兰计算器
?代码:
package zhan;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class nibolanbiaodashi {
public static void main(String[] args) {
//先定义一个逆波兰表达式
//(3+4)*5-6 =>30 4 + 5 * 6 -
String expre = "30 4 + 5 * 6 -";
//先将expre放入ArrayList中
//将ArrayList传递给一个方法 该方法配合栈 完成计算
List<String> list = getListString(expre);
System.out.println(list);
System.out.println(cal(list));
}
//将一个逆波兰表达式 一次将数据和运算符放入到将ArrayList传递给一个方法
public static List<String> getListString(String sss){
//将sss分割
String[] split = sss.split(" ");
List<String> list = new ArrayList<>();
for(String s : split){
list.add(s);
}
return list;
}
//完成对逆波兰表达式的运算
public static int cal(List<String> list){
//创建一个栈即可
Stack<String> strings = new Stack<>();
for (String item:list) {
//使用正则表达式取出数
if(item.matches("\\d+")){
strings.push(item);
}else {
int num2 = Integer.parseInt(strings.pop());
int num1 = Integer.parseInt(strings.pop());
int res = 0;
if(item.equals("+")){
res=num1+num2;
}else if(item.equals("-")){
res=num1-num2;
}else if(item.equals("*")){
res = num1*num2;
}else if(item.equals("/")){
res = num1/num2;
}else {
throw new RuntimeException("ERROR!");
}
strings.push(res+"");
}
}
return Integer.parseInt(strings.pop());
}
}
?中缀表达式转换为后缀表达式
? ? ? ? 具体步骤:
? ? ? ? ①初始化两个栈:运算符栈s1和存储中间结果的栈s2
? ? ? ? ②从左至右扫描中缀表达式
? ? ? ? ③遇到操作数时 将其压入s2
? ? ? ? ④遇到运算符时 比较其与s1栈顶运算符的优先级
? ? ? ? ? ? ? ? *·若s1为空 ，或者栈顶运算符位左括号"(",则将此运算符入栈
? ? ? ? ? ? ? ? ·否则 若优先级比栈顶运算符的高 也将运算符压入s1
? ? ? ? ? ? ? ? ·否则 (比如运算及相同的+和-)将s1栈顶的运算符弹出并压入到s2中 再次转到(*)与s1中新的栈顶运算符比较
????????⑤遇到括号时:
????????? ? ? ? ·若是左括号"(" 则直接压入s1
????????????????·若是右括号")" 则依次弹出s1栈顶的运算符 并压入s2 直到遇到左括号为止 然后将这一
????????对括号丢弃
????????⑥重复步骤2-5 直到表达式的最右边
? ? ? ? ⑦将s1中剩余的运算符依次弹出并压入s2
????????⑧依次弹出s2中的元素并输出 结果的逆序即为中缀表达式对应的后缀表达式
?代码1:将表达式转为List
//将中缀表达式转为相应的List
public static List<String> toList(String str){
List<String> ans = new ArrayList<>();
int i = 0;
String s;//多位数的拼接
char c;//每遍历到一个字符 就放入到c
do{
//如果c是一个非数字 需要加入ans
if((c=str.charAt(i))<48 || (c=str.charAt(i))>57) {
ans.add(""+c);
i++;
}else {//若是一个数 需要考虑多位数
s="";
while(i<str.length()&&(c=str.charAt(i))>=48&&(c=str.charAt(i))<=57){
s+=c;
i++;
}
ans.add(s);
}
}while (i<str.length());
return ans;
}代码2(中缀转逆波兰list):
?
//将中缀表达式的list转为后缀表达式相应的list
public static List<String> toNibolan(List<String>ans){
//定义两个栈
Stack<String>s1 = new Stack<>();//符号栈
// Stack<String>s2 = new Stack<>();//中间栈 没有必要有这个 因为在
// //整个转换过程中没有pop操作 且最后需要逆序输出 所以 使用一个list代替
List<String> s2 = new ArrayList<String>(){};
//遍历
for(String item : ans){
if(item.matches("\\d+")){
s2.add(item);
}else if(item.equals("(")){
s1.push(item);
}else if(item.equals(")")){
while(!s1.peek().equals("(")){
s2.add(s1.pop());
}
s1.pop();//将这一对括号消除
}else {
//当item优先级小于等于栈顶运算符优先级 将s1栈顶的运算符加入s2
while (s1.size()!=0&&Operation.getValue(s1.peek())>=Operation.getValue(item)){
s2.add(s1.pop());
}
s1.push(item);
}
}
while (s1.size()!=0){
s2.add(s1.pop());
}
return s2;
}综合代码:
package zhan;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class zhongxuzhuannibolan {
public static void main(String[] args) {
//先把表达式转为中序的ArrayList 然后进行转换
String expre = "1+((2+3)*4)-5";
List<String> list = toList(expre);
System.out.println(list);
System.out.println();
System.out.println(toNibolan(list));
}
//将中缀表达式的list转为后缀表达式相应的list
public static List<String> toNibolan(List<String>ans){
//定义两个栈
Stack<String>s1 = new Stack<>();//符号栈
// Stack<String>s2 = new Stack<>();//中间栈 没有必要有这个 因为在
// //整个转换过程中没有pop操作 且最后需要逆序输出 所以 使用一个list代替
List<String> s2 = new ArrayList<String>(){};
//遍历
for(String item : ans){
if(item.matches("\\d+")){
s2.add(item);
}else if(item.equals("(")){
s1.push(item);
}else if(item.equals(")")){
while(!s1.peek().equals("(")){
s2.add(s1.pop());
}
s1.pop();//将这一对括号消除
}else {
//当item优先级小于等于栈顶运算符优先级 将s1栈顶的运算符加入s2
while (s1.size()!=0&&Operation.getValue(s1.peek())>=Operation.getValue(item)){
s2.add(s1.pop());
}
s1.push(item);
}
}
while (s1.size()!=0){
s2.add(s1.pop());
}
return s2;
}
//将中缀表达式转为相应的List
public static List<String> toList(String str){
List<String> ans = new ArrayList<>();
int i = 0;
String s;//多位数的拼接
char c;//每遍历到一个字符 就放入到c
do{
//如果c是一个非数字 需要加入ans
if((c=str.charAt(i))<48 || (c=str.charAt(i))>57) {
ans.add(""+c);
i++;
}else {//若是一个数 需要考虑多位数
s="";
while(i<str.length()&&(c=str.charAt(i))>=48&&(c=str.charAt(i))<=57){
s+=c;
i++;
}
ans.add(s);
}
}while (i<str.length());
return ans;
}
//将一个逆波兰表达式 一次将数据和运算符放入到将ArrayList传递给一个方法
public static List<String> getListString(String sss){
//将sss分割
String[] split = sss.split(" ");
List<String> list = new ArrayList<>();
for(String s : split){
list.add(s);
}
return list;
}
//完成对逆波兰表达式的运算
public static int cal(List<String> list){
//创建一个栈即可
Stack<String> strings = new Stack<>();
for (String item:list) {
//使用正则表达式取出数
if(item.matches("\\d+")){
strings.push(item);
}else {
int num2 = Integer.parseInt(strings.pop());
int num1 = Integer.parseInt(strings.pop());
int res = 0;
if(item.equals("+")){
res=num1+num2;
}else if(item.equals("-")){
res=num1-num2;
}else if(item.equals("*")){
res = num1*num2;
}else if(item.equals("/")){
res = num1/num2;
}else {
throw new RuntimeException("ERROR!");
}
strings.push(res+"");
}
}
return Integer.parseInt(strings.pop());
}
}
//此类用来判断优先级
class Operation{
public static final int ADD =1;
public static final int SUB =1;
public static final int MUL =2;
public static final int DIV =2;
public static int getValue(String ope){
int res = 0;
switch (ope){
case "+":
res = ADD;
break;
case "-":
res = SUB;
break;
case "*":
res = MUL;
break;
case "/":
res = DIV;
break;
}
return res;
}
}
递归
? ? ? ? ①执行一个方法时 就创建一个新的受保护的独立空间(栈空间)
? ? ? ? ②方法的局部变量是独立的不会相互影响 比如n变量
? ? ? ? ③如果方法中使用的是引用类型的变量(比如数组) 就会共享该引用类型的数据
? ? ? ? ④递归必须向退出递归的条件必进 否则就是无限递归?
? ? ? ? ⑤当一个方法执行完毕 或者遇到return 就会返回 遵守谁调用 就将结果返回给谁
? ? 同时方法执行完毕或者返回时 该方法也就执行完毕
实际案例:
? ? ? ? 递归-迷宫问题 目前没学过算法 所以只能强行通过比较得出最短 索性放到后面再说了
public class migong {
public static void main(String[] args) {
//先创建一个二维数组 模拟迷宫
int[][] map = new int[8][7];
//用1表示墙壁
//把上下置为1
for (int i = 0; i < 7; i++) {
map[0][i]=1;
map[7][i]=1;
}
//把左右置为1
for (int j = 0; j < 8; j++) {
map[j][0]=1;
map[j][6]=1;
}
map[3][1]=1;
map[3][2]=1;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
System.out.println();
System.out.println();
setWay(map,1,1);
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
//使用递归来给小球找路
}
/**
*如果能到map[6][5] 则能找到
* 当map[i][j]=0时 表示小球还没走过这个点 1表示墙 2表示走过 且是通路 3表示走过 但是死路
* 在走迷宫时 需要确定一个方法 比如 按照下->右->上->左的顺序 若走不通 则回溯
* @param map 地图
* @param i (i,j)从哪个位置开始找
* @param j
* @return 若找到 返回true
*/
public static boolean setWay(int [][]map,int i,int j){
if(map[6][5]==2){
return true;
}else{
if(map[i][j]==0){
//按照下->右->上->左的顺序
map[i][j]=2;//先假设能走通
if(setWay(map,i+1,j)){
return true;
}else if(setWay(map,i,j+1)){
return true;
}else if(setWay(map,i-1,j)){
return true;
}else if(setWay(map,i,j-1)){
return true;
}else {
map[i][j]=3;
return false;
}
}else {//可能是123
return false;
}
}
}
}
? 递归八皇后问题
?
?
?思路分析:
public class bahuanghou {
static int max = 8;//表示有几个皇后
int []array = new int[max];//存最后的结果
static int count=0;
static int count2=0;
public static void main(String[] args) {
bahuanghou bahuanghou = new bahuanghou();
bahuanghou.check(0);
System.out.println(count);
System.out.println(count2);
}
//可以将皇后摆放的位置输出
private void print(){
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
//查看我们放置第n个皇后后 去检测该皇后是否和前面已经摆放的皇后冲突
private boolean judge(int n){
count2++;
for (int i = 0; i < n; i++) {
//表示第n个皇后 是否和前面的n-1个皇后 是否在同一列 是否在同一直线
if (array[i] == array[n]||Math.abs(n-i)==Math.abs(array[n]-array[i])) {
return false;
}
}
return true;
}
//编写一个方法 放置第n个皇后
private void check(int n){
if(n==max){
print();
return;
}
//依次放入 并判断是否冲突
for (int i=0 ; i < max ;i++){
//先把当前这个皇后n 放到该行的第一列
array[n]=i;
if(judge(n)){//不冲突
//接着放第n+1个皇后
check(n+1);
}
}
}
}
?
?