当前位置 博文首页 > 邱天的henry的博客:第四章 数据结构与算法(栈)
4.1栈的一个实际需求
计算一个表达式
计算表达式:【722-5+1-5+3-3】点击计算【如下图】
此例并不是简单的把算式列出计算,而是考虑计算机是如何对这个式子进行解析并运算的,这就引出问题的关键--------栈。
5.2栈的介绍
(1)栈的英文为(stack)
(2)栈是一个先入后出(FILO-First In Last Out)的有序列表
(3)栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底(Bottom)。
(4)根据栈的定义可知,最先放入栈中的元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除
(5)图解方式说明出栈(pop)和入栈(push)的概念
4.3栈的应用场景
(1)子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中,直到子程序执行完后再将地址取出,以回到原来的程序中。
(2)处理递归调用:和子程序的调用类似,只是除了存储下一个指令的地址外,也将参数、区域变量等数据存入堆栈中。
(3)表达式的转换【中缀表达式转后缀表达式】与求职(实际解决)。
(4)二叉树的遍历。
(5)图形的深度优先(depth —first)搜索法。
4.4栈的快速入门
(1)用数组模拟栈的使用,由于栈是一种有序列表,当然可以使用数组的结构来存存储栈的数据内容,以下是数组模拟栈的出栈,入栈操作。
(2)实现思路如下:
代码实现:
import java.util.Scanner;
public class ArrayStackDemo {
public static void main(String[] args) {
//测试ArrayStack是否正确(定义菜单测试栈)
ArrayStatck arrayStatck = new ArrayStatck(4);
String key=""; //接收控制台输入的命令
boolean flag=true; //标识是否退出程序
Scanner scanner = new Scanner(System.in); //接收控制台输入
//创建菜单
while (flag){
System.out.println("show:展示栈中数据");
System.out.println("add:向栈中添加数据");
System.out.println("pop:弹出栈中数据");
System.out.println("exit:退出程序");
String str = scanner.next();
switch (str){
case "show":
arrayStatck.show();
break;
case "add":
System.out.println("请输入数据");
int value = scanner.nextInt();
arrayStatck.push(value);
break;
case "pop":
try {
int pop = arrayStatck.pop();
System.out.printf("出栈的数据为:%d \n",pop);
break;
}catch (Exception e){
System.out.println(e.getMessage());
}
case "exit":
scanner.close();
flag=false;
break;
}
}
System.out.println("退出菜单!");
}
}
//用数组来模拟栈
class ArrayStatck{
private int maxSize; //定义栈的最大空间
private int[] stack; //用数组来存放栈中数据
private int pop=-1; //将栈顶指针初始化为-1
//创建构造器,初始化栈
public ArrayStatck(int maxSize){
this.maxSize=maxSize;
stack=new int[maxSize];
}
//判断栈是否为空
public boolean isEmpty(){
return pop==-1;
}
//判断栈是否满
public boolean isFull(){
return pop==maxSize-1;
}
//入栈
public void push(int data){
if (isFull()){
System.out.println("栈满");
return;
}
pop++; //将指针上移
stack[pop]=data; //将数据存入
}
//出栈
public int pop(){
if (isEmpty()){
throw new RuntimeException("栈为空");
}
int value=stack[pop]; //将出栈的值存入临时变量方便后入弹出
pop--; //将指针下移
return value;
}
//遍历栈中元素(注意:从栈顶开始遍历)
public void show(){
if (isEmpty()){
System.out.println("栈为空");
return;
}
//遍历出栈
for (int i=pop;i>=0;i--){
System.out.printf("stack[%d]=%d \n",i,stack[i]);
}
}
}
4.5栈实现综合计算器(中缀表达式)
@使用栈来实现综合计算器
@思路分析(图解)
@代码实现【1.先实现一位数的运算,2.扩展到多位数的运算】
public class Calculator {
public static void main(String[] args) {
String expression = "7*2-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.count(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