1、定义
- 栈是一个 先入后出的有序列表
- 栈(stack)是限制线性表中元素的插入和删除只能在线性表的 同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底
- 最先放入的元素在栈底，且最后出栈。最后放入的元素在栈顶，且最先出栈
2、应用场景
- 子程序递归调用。如JVM中的虚拟机栈
- 表达式转换（中缀转后缀）与求值
- 二叉树的遍历
- 图的深度优先遍历
3、实现
- 定义top表示栈顶，初始值为-1
- 入栈的操作，先让top++，再放入数组
- 出栈操作，先取出元素，在让top–
- top == -1时，栈空
- top == maxSize-1时，栈满
java;collapse:true;;gutter:true;
import java.util.Scanner;</p>
<p>public class ArrayStackDemo {
public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack(4);
String key = "";
boolean flag = true;
Scanner scanner = new Scanner(System.in);</p>
<pre><code> while (flag){
System.out.println("输入show展示数据");
System.out.println("输入push加入数据");
System.out.println("输入pop 取出数据");
System.out.println("输入exit退出程序");
key = scanner.next();
switch (key){
case "show":
arrayStack.showStack();
break;
case "push":
System.out.println("请输入您的数据:");
int value = scanner.nextInt();
arrayStack.pushStack(value);
break;
case "pop":
try {
int num = arrayStack.popStack();
System.out.println("取出的数据是:"+num);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
flag = false;
break;
default:
break;
}
}
System.out.println("程序已退出");
}
</code></pre>
<p>}</p>
<p>class ArrayStack{
private int maxSize;
private int[] stack;
private int top = -1;</p>
<pre><code>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 pushStack(int value){
if (isFull()){
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}
public int popStack(){
if (isEmpty()){
throw new RuntimeException("栈空,无法取出");
}
int value = stack[top];
top--;
return value;
}
public void showStack(){
if (isEmpty()){
System.out.println("栈空");
return;
}
for (int i = top; i >= 0; i--){
System.out.printf("stack[%d]=%d \n",i,stack[i]);
}
}
</code></pre>
<p>}</p>
<pre><code>
## 4、应用
* 准备一个索引index来帮助我们遍历表达式
* 如果index位置上的元素是一个数字，就直接入栈
* 如果index位置上的元素是一个符号
- 如果符号栈为空，直接入栈
- 如果符号栈不为空
+ index位置上的符号的优先级小于或等于栈顶符号的优先级，则弹出两个数栈中的元素和符号栈中的一个符号，并且进行计算。将运算结果放入数栈中，并将index位置上的符号压入符号栈
+ index位置上的符号的优先级大于符号栈栈顶符号的优先级，则将该符号压入符号栈
* 当表达式遍历完毕后，就弹出数栈中的2个数字和符号栈中的1个符号进行运算，并将运行结果入栈
* 最终数栈中只有一个值，这个值便是运算结果
* 注意：
- 读取的是字符，所以存入数字前需要减去0的ASCII码
- 如果数字是多位数，需要一直读，读到下一位不是数字为止，然后将读到的字符进行拼接，然后一起压入数栈
;collapse:true;;gutter:true;
public class Calculator {
public static void main(String[] args) {
String expression = "321+2*6-2";
//要获取两个栈,一个是数栈,一个是符号栈
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);
if (operStack.isOper(ch)){//判断这个扫描到的字符是不是运算符
if (!operStack.isEmpty()){//判断这个符号栈是否为空
/*
如果符号栈不为空
index位置上的符号的优先级小于或等于栈顶符号的优先级，则弹出两个数栈中的元素和符号栈中的一个符号，并且进行计算。
将运算结果放入数栈中，并将index位置上的符号压入符号栈
index位置上的符号的优先级大于符号栈栈顶符号的优先级，则将该符号压入符号栈
*/
if (operStack.priority(ch) = 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 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;
}
}
Original: https://www.cnblogs.com/wyh518/p/16746526.html
Author: 腹白
Title: 栈的定义和应用(数组模拟)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605349/
转载文章受原作者版权保护。转载请注明原作者出处！