java模拟栈的操作
2024-10-08 23:29:01
栈是一种有序列表，可以使用数组的结构来储存栈的数据内容
思路
1. 创建一个栈类StackArray
2. 定义一个top来模拟栈顶，初始化为-1
3. 入栈： 当有数据加入到栈的时候 top++ stack[top] = data
4. 出栈 int value = stack[top]; top--, return value
代码实现
//定义一个类来表示栈
class ArrayStack{
private int maxSize; //栈的大小
private int[] stack; //数组模拟栈 数据放在数组中
private int top = -1; //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;
} //入栈 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]);
}
} }
通过main方法调用自定义的栈类来模拟栈的操作
public class StackArrayDemo {
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 result = stack.pop();
System.out.printf("取出的数据为：%d\n", result);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
根据上边的内容 来模拟一下用栈实现的计算表达式的功能
思路
通过一个index（索引） 来遍历我们的表达式
如果我们发现是一个数字 就直接入数栈
如果扫描到的是一个符号 就分如下情况
1.如果当前符号栈为空， 就直接入栈
2.如果符号栈有操作符 就进行比较 如果当前操作符的优先级 小于或等于栈中的操作符
就需要从数栈中pop出两个数，再从符号栈中pop出一个符号，进行运算，将得到的结果入数栈
再把当前的符号入符号栈，
3.如果当前符号的优先级大于栈中的操作符，直接入栈
扫描完毕后 就顺序地冲数栈和符号栈中pop出响应的数和符号 并运行
最后在数栈中只有一个数字就是表达式的结果 参考上边的ArrayStack类 拓展一个ArrayStack2 类 并对功能进行增强
//定义一个类来表示栈 对ArrayStack进行扩展
class ArrayStack2{
private int maxSize; //栈的大小
private int[] stack; //数组模拟栈 数据放在数组中
private int top = -1; //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;
} //入栈 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 oper, int num1, int num2){
int result = 0; // 用于存放计算的结果
switch (oper){
case '+':
result = num1 + num2;
break;
case '-':
result = num2 - num1;
break;
case '*':
result = num2 * num1;
break;
case '/':
result = num2 / num1;
break;
default:
break;
} return result;
} //返回栈顶的值 不Pop
public int peek(){
return stack[top];
} }
调用主方法 进行案例的具体实现
public class StackCalculate {
public static void main(String[] args) {
//完成表达式的运算
String expression = "500+7*2-8";
//创建两个栈 一个数栈一个符号栈
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 (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(oper,num1, num2);
//将运算结果压入数栈
numStack.push(res);
//将当前运算符压入符号栈
operStack.push(ch);
}else {
operStack.push(ch);
}
}else {
//为空 直接入栈、
operStack.push(ch);
}
}else {
//如果ch是数字 直接入数栈
// numStack.push(ch - 48); // ASCII码转换成int
//当处理多位数时 有可能是多位数 因此 需要定义一个字符串变量 用于拼接
keepNum += ch;
//如果ch已经到expression的最后一位了直接入栈
if (index == expression.length() - 1){
numStack.push(Integer.parseInt(keepNum));
} else if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))){
// 如果后一位是运算符则入栈
numStack.push(Integer.parseInt(keepNum));
//!!重要的 清空keepNum
keepNum = "";
}
}
//index ++ 判断是否扫描到表达式最后的位置
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(oper,num1, num2);
numStack.push(res);
}
//将最后的计算结果pop出
int finalRes = numStack.pop();
System.out.printf("表达式%s = %d", expression, finalRes);
}
}
最新文章
- Jenkins 2.0 要来了
- cocos2d-x 3.0 事件分发机制
- 每天一个 Linux 命令（17）：whereis 命令
- Tabio – 轻松，高效的管理 Chrome 标签页
- wf（四）
- [issue] dyld`dyld_fatal_error: -> 0x120015088 <+0>: brk #0x3
- LZW压缩算法
- yeild
- Java OCR 图像智能字符识别技术，可识别中文
- cnblogs体验
- C#中打日志导出日志到txt文本
- 重要的几个热键[Tab], [ctrl]-c, [ctrl]-d
- python基础教程（九）
- html->html5->css->javascript(js)->jQuery->AJAX->JSON
- 使用JConsole以及VisualVM进行jvm程序的监控，排错，调优
- 我的mfc基础知识点
- Maven 构建浏览器解析userAgent类
- requests+正则爬取猫眼电影前100
- golang pprof 内存分析
- SQL Server 优化---为什么索引视图（物化视图）需要with(noexpand)强制查询提示
热门文章
- 30分钟学会Objective-C
- 简单说 JavaScript中的tostring( ) 与 valueOf( )方法
- uWSGI, send_file and Python 3.5
- 续python学习（一）
- 浅谈Java中静态代码块和非静态代码块
- kafka集群搭建及结合springboot使用
- js 实现弹性运动的简单应用----导航栏中弹性
- Spring Cloud - Nacos注册中心入门单机模式及集群模式
- 网络安全从入门到精通 (第二章-2) 后端基础SQL—MySQL数据库简介及SQL语法
- 编译Zookeeper3.4.6源代码并通过Intellij IDEA运行（2020年）