Java数据结构与算法——栈篇

书读的越多而不加思考,你就会觉得你知道得很多;而当你读书而思考得越多的时候,你就会越清楚地看到,你知道得很少。

导读:本篇文章讲解 Java数据结构与算法——栈篇,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

Java数据结构与算法: https://blog.csdn.net/weixin_46822367/article/details/115478461?spm=1001.2014.3001.5502.

在这里插入图片描述
在这里插入图片描述

系统中的堆、栈和数据结构堆、栈不是一个概念。可以说系统中的堆、栈是真实的内存物理区,数据结构中的堆、栈是抽象的数据存储结构。

栈:实际上就是满足后进先出的性质,是一种数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除。

在这里插入图片描述

栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。

栈的优势是,存取速度比堆要快,仅次于直接位于CPU中的寄存器。但缺点是,存在栈中的数据大小与生存期必须是确定的,缺乏灵活性。

在这里插入图片描述

1、栈

思路分析:
在这里插入图片描述

代码实现:

package com.lyp.stack;

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) {
					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]);
		}
	}

	
}

2、栈实现综合计算器

思路分析:
在这里插入图片描述

代码实现:

package com.lyp.stack;

public class Calculator {

	public static void main(String[] args) {
		String expression = "7*2*2-5+1-5+3-4";
		//创建两个栈,数栈,一个符号栈
		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);
					
				}
			} else {//如果是数
				//numStack.push(ch - 48);//'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))) {
						//如果后一位是运算符,则入栈
						numStack.push(Integer.parseInt(keepNum));
						//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);//入栈
		}
		//将数栈的最后数,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 和 char可以混用
		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;
	}
}

3、前缀、中缀、后缀表达式,逆波兰计算器

原理分析:
在这里插入图片描述
在这里插入图片描述

代码实现:

package com.lyp.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import javax.management.RuntimeErrorException;

public class PolandNotation {

	public static void main(String[] args) {
		
		//完成将一个中缀表达式转成后缀表达式的功能 
		//说明
		//1. 1+((2+3)*4)-5 => 转成 1 2 3 + 4 * + 5 -
		//2. 因为直接对str 进行操作,不方便,因此 先将"1+((2+3)*4)-5" => 中缀表达式对应的List
		//  即 “1+((2+3)*4)-5” => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
		//3. 将得到的中缀表达式对应的List => 后缀表达式对应的List
		//即 ArrayList ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] => ArrayList [1,2,3,+,4,*,+,5,-]
		
		String expression = "1+((2+3)*4)-5";
		List<String> infixExpressionList = toInfixExpressionList(expression);
		System.out.println("后缀表达式对应的List="+infixExpressionList);//ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
		List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
		System.out.println("后缀表达式对应的List="+suffixExpressionList);//ArrayList [1,2,3,+,4,*,+,5,-]
		
		System.out.printf("expression=%d",calculate(suffixExpressionList));
		/*
		//先定义一个逆波兰表达式
		//(30+4)*5-6 => 30 4 + 5 * 6 - => 164
		//4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + 
		//为了方便,逆波兰表达式的数字和符号使用空格隔开
		//String suffixExpression = "30 4 + 5 * 6 -";
		String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";//76
		//思路
		//1.先将"3 4 + 5 * -" => 放到ArrayList中
		//2.将ArrayList 传给一个方法,遍历 ArrayList 配合栈完成计算
		
		List<String> list = getListString(suffixExpression);
		System.out.println("rpnList"+list);
		int res = calculate(list);
		System.out.println("计算的结果="+res);
		*/
	}
	
	//即 ArrayList ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] => ArrayList [1,2,3,+,4,*,+,5,-]
	//方法 :将得到的中缀表达式对应的List => 后缀表达式对应的List
	public static List<String> parseSuffixExpressionList(List<String> ls){
		//定义两个栈
		Stack<String> s1 = new Stack<String>();//符号栈
		//说明,因为 s2 这个栈,在整个转化过程中,没有 pop操作,而且后面我们还需要逆序输出
		//因此比较麻烦,这里我们就不用Stack<String> 直接用 List<String> s2
		//Stack<String> s2 = new Stack<String>();//存储中间结果的 栈 s2
		List<String> s2 = new ArrayList<String>();//存储中间结果的 List s2
		
		//遍历 ls
		for(String item :ls) {
			//如果是一个数,加入s2
			if(item.matches("\\d+")) {
				s2.add(item);
			} else if (item.equals("(")) {
				s1.push(item);
			} else if (item.equals(")")) {
				//如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,知道遇到左括号为止,此时将这一对括号丢弃
				while (!s1.peek().equals("(")) {
					s2.add(s1.pop());
				}
				s1.pop();//!!! 将 ( 弹出 s1栈,消除小括号
			} else {
				//当item 的优先级小于等于s1栈顶运算符,将s1栈顶的运算符弹出并加入s2中,再次与s1中新的栈顶运算符比较
				while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
					s2.add(s1.pop());
				}
				//还需要将item 压入栈
				s1.push(item);
			}
		}
		
		//将s1剩余的运算符依次弹出 加入s2
		while(s1.size() != 0) {
			s2.add(s1.pop());
		}
		
		return s2;//因为是存放到List,因此按顺序输出就是对应的List
	}

	//方法: 将 中缀表达式转成对应的List
	//s ="1+((2+3)*4)-5";
	public static List<String> toInfixExpressionList(String s){
		//定义一个List,存放中缀表达式 对应的内容
		List<String> ls = new ArrayList<String>();
		int i = 0;//这是一个指针,用于遍历 中缀表达式字符串
		String str;//对多位数的拼接
		char c;//每遍历到一个字符,就放入到c
		do {
			//如果c是一个非数字,需要加入到ls
			if((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
				ls.add(""+ c);
				i++;//i需要后移
			} else { //如果是一个数,需要考虑多位数
				str = "";//先将str 置成空串  '0' [48] -> '9' [57]
				while(i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57){
					str += c;//拼接
					i++;
				}
				ls.add(str);
			}
		} while(i < s.length());
		return ls;//返回
	}
	
	//将一个逆波兰表达式,依次将数据和运算符 放入 ArrayList中
	public static List<String> getListString(String suffixExpression){
		//将 suffixExpression 分割
		String[] split = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>();
		for(String ele: split) {
			list.add(ele);
		}
		return list;
	}
	
	//完成对逆波兰表达式的运算
	public static int calculate(List<String> ls) {
		//创建栈,只需要一个栈即可
		Stack<String> stack = new Stack<String>();
		//遍历 ls
		for(String item: ls) {
			//这里使用正则表达式取出数
			if(item.matches("\\d+")) {//匹配的是多位数
				//入栈
				stack.push(item);
			} else {
				//pop出两个数,并运算,再入栈
				int num2 = Integer.parseInt(stack.pop());
				int num1 = Integer.parseInt(stack.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("运算符有误");
				}
				//把 res 入栈
				stack.push(""+res);
			}
		}
		//最后留在stack中的数据是运算结果
		return Integer.parseInt(stack.pop());
	}
}
 
//编写一个类 Operation 可以返回一个运算符 对应的优先级
class Operation {
	private static int ADD = 1;
	private static int SUB = 1;
	private static int MUL = 2;
	private static int DIV = 2;
	
	//写一个方法,返回对应的优先级数字
	public static int getValue(String operation) {
		int result = 0;
		switch(operation) {
		case "+" :
			result = ADD;
			break;
		case "-" :
			result = SUB;
			break;
		case "*" :
			result = MUL;
			break;
		case "/" :
			result = DIV;
			break;
		default :
			System.out.println("不存在该运算符");
			break;
		}
		return result;
	}
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/123090.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!