今天记录栈的相关学习
栈
栈的英文为(stack)
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。 允许插入和删除的一端， 为变化的一端， 称为栈顶(Top)， 另一端为固定的一端， 称为栈底(Bottom)。
栈的用处
- 子程序的调用： 在跳往子程序前， 会先将下个指令的地址存到堆栈中， 直到子程序执行完后再将地址取出， 以回到原来的程序中。
- 处理递归调用： 和子程序的调用类似， 只是除了储存下一个指令的地址外， 也将参数、 区域变量等数据存入堆栈中。
- 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
- 二叉树的遍历。
- 图形的深度优先(depth 一 first)搜索法。
数组进行模拟栈
package com.tunan.stack;
import java.util.Scanner;
public class ArrayStackDemo {
public static void main(String[] args) {
//测试
ArrayStack arrayStack = 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":
arrayStack.showStack();
break;
case "push":
System.out.println("请输入入栈参数");
int value = scanner.nextInt();
arrayStack.push(value);
break;
case "pop":
try {
int res = arrayStack.pop();
System.out.printf("出栈数据是%d \n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
System.out.println("退出成功");
break;
default:
break;
}
}
}
}
//创建一个 ArrayStack 类，数组模拟栈
class ArrayStack {
private int maxSize; //栈的最大容量
private int[] stack;//栈的数据存放于该数组
private int top = -1;//表示栈顶，初始化为-1
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
//判断栈满
public boolean isFull() {
return top == maxSize - 1;
}
//判断栈空
public boolean isEmpty() {
return top == -1;
}
//入栈操作
public void push(int val) {
if(isFull()) {
System.out.println("栈满，无法进行入栈操作");
return;
}
top++;
stack[top]=val;
}
//出栈操作
public int pop() {
if(isEmpty()) {
//抛出异常
throw new RuntimeException("栈空，无法进行出栈操作");
}
int res = stack[top];
top--;
return res;
}
//遍历栈
public void showStack(){
if(isEmpty()) {
System.out.println("栈空");
return;
}
for (int j=top; j>-1;j--){
System.out.printf("stack[%d] = %d \n", j, stack[j]);
}
}
}
数组模拟栈的操作相对简单，因此这里给出一个数组模拟栈的更进一步的应用：
实现计算器操作
这里首先实现一个简单的中缀表达式计算操作，所谓的中缀，就是我们平时所见最多的表达式形式，比如
722-5+1-5+3-4/2
实现这样操作的思路是：
代码实现如下：
package com.tunan.stack;
public class Calculator {
public static void main(String[] args) {
//给出一个表达式
String expression = "7*2*2-5+1-5+3-4/2";//如何处理多位数的问题
//创建两个栈，数栈和符号栈
calStack numStack = new calStack(10);
calStack operStack = new calStack(10);
//定义相关变量
int index = 0;//扫描用
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' ';//将每次扫描得到char保存到ch中
String keepNum = "";//用于拼接多位数
//开始进行while扫描
while(true) {
//依次得到expression中的每一位,使用字符串的方法
ch = expression.substring(index, index+1).charAt(0);
//判断这一位是数还是符号
if(operStack.isOper(ch)) {//如果是运算符
if(!operStack.isEmpty()){
//不为空需要判断优先级
//优先级小于等于栈顶优先级，则需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 ***对照acsll码，字符和数字差了48
//考虑多位数的情况，需要对index后面继续扫描，如果是数，则需要拼接
keepNum += ch;
if(index == expression.length() - 1){
numStack.push(Integer.parseInt(keepNum));
} else{
if(operStack.isOper(expression.substring(index+1, index+2).charAt(0))) {
//字符串转int，“123”->123
numStack.push(Integer.parseInt(keepNum));
//必须把keepNum清空！！！
keepNum = "";
}
}
}
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(num1, num2, oper);
numStack.push(res);
}
System.out.printf("表达式 %s = %d\n", expression, numStack.pop());
}
}
//创建一个栈，增加计算器所需功能
class calStack {
private int maxSize; //栈的最大容量
private int[] stack;//栈的数据存放于该数组
private int top = -1;//表示栈顶，初始化为-1
public calStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
//查看栈顶值但不执行出栈操作
public int peek() {
if(isEmpty()) {
//抛出异常
throw new RuntimeException("栈空，无法进行出栈操作");
}
int res = stack[top];
return res;
}
//判断栈满
public boolean isFull() {
return top == maxSize - 1;
}
//判断栈空
public boolean isEmpty() {
return top == -1;
}
//入栈操作
public void push(int val) {
if(isFull()) {
System.out.println("栈满，无法进行入栈操作");
return;
}
top++;
stack[top]=val;
}
//出栈操作
public int pop() {
if(isEmpty()) {
//抛出异常
throw new RuntimeException("栈空，无法进行出栈操作");
}
int res = stack[top];
top--;
return res;
}
//遍历栈
public void showStack(){
if(isEmpty()) {
System.out.println("栈空");
return;
}
for (int j=top; j>-1;j--){
System.out.printf("stack[%d] = %d \n", j, stack[j]);
}
}
//返回操作符的优先级，用数字表示
//数字越大，优先级越高
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 res = 0;//用于存放结果
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;
}
}
这里可以看出计算过程有一些繁琐，这也是中缀表达式的短板，虽然有利于人们去读，但对计算机却并不友好，并且上面的程序没有考虑到括号的情况。
下一节我将继续介绍前缀、中缀和后缀的表达，以及实现逆波兰的表达。