栈的介绍
栈是限制插入和删除只能在一个位置上进行的线性表。其中允许插入和删除的一端位于表的末端，叫做栈顶(top);不允许插入和删除的另一端为栈底(bottom)。对栈的基本操作有push(压栈)和pop(出栈、弹栈),前者相当于表的插入操作(向栈顶插入一个元素),后者则是删除操作(删除一个栈顶元素)。栈式一种后进先出，先进后出(LIFO)的数据结构，最先被删除的是最近压栈的元素。
遵循**先进后出，后进先出**原则
- 取出数据: 出栈(弹栈)
- 插入数据: 压栈
栈实现
由于栈是一个表，因此任何实现表的方法都可以用来实现栈。主要有俩种方式，链表实现和数组实现。
链表实现栈
可以使用单链表来实现栈。通过在表顶端插入一个来实现push,通过删除表顶端元素来实现pop。使用链表实现的的栈又叫动态栈。动态栈有链表的部分特性，即元素与元素之间在物理存储上可以不连续，但是功能有些受限，动态栈只能在栈顶处进行插入和删除操作，不能在栈尾或者栈中间进行插入和删除操作
数组实现栈
栈也可以用数组来实现。使用数组方式实现的栈叫做静态栈
栈的应用场景
- 子程序的调用: 在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
- 处理递归调用: 和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
- 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)
- 二叉树的遍历
- 图形的深度优先(depth->first) 搜索法
模拟栈实现(数组)
package com.chentianyu.stack;public class ArrayStack {//栈的大小private int maxStack;//数组来模拟栈private int[] stack;//表示栈顶所在的位置，默认情况下，没有数据时,使用-1private int top = -1;//给栈设置初始化大小public ArrayStack(int maxStack){this.maxStack = maxStack;//初始化栈stack = new int[maxStack];}/*** 1.压栈* 2.弹栈* 3.判断是否是空栈* 4.当前栈中是否是满栈的状态*///判断是否已经满栈public boolean isFull(){return this.top == maxStack - 1;}//判断当前栈是否是一个空栈(栈里有没有元素)public boolean isEmpty(){return this.top == -1;}//压栈public void push(int val){//是否已经栈满if(isFull()){throw new RuntimeException("栈已满");}top++;stack[top] = val;}//弹栈public int pop(){//如果栈是空的if(isEmpty()){throw new RuntimeException("栈是空的，没有数据");}int value = stack[top];top--;return value;}//该方法查看栈中所有的元素public void list(){if(isEmpty()){throw new RuntimeException("栈是空的，没有数据");}for (int i=0;i<stack.length;i++){System.out.printf("stack[%d]=%d",i,stack[i]);}}/*** 栈中元素存在的个数* @return*/public int length(){return this.top + 1;}}
栈(回文数据)
- 回文: 指一个单词(或数据)从前往后，从后往前都是一样的
package com.chentianyu.stack;public class ArrayStackTest {public static void main(String[] args) {/*** 回文数据* 回文: 指一个单词(或数据)从前往后，从后往前都是一样的* 需求: 通过上面以数据模拟栈来判断一个字符是否是一个回文数据*/System.out.println(detecation("hello"));}public static boolean detecation(String val){/*** 初始化栈对象*/ArrayStack arrayStack = new ArrayStack(10);/*** 获取字符串的长度*/int length = val.length();//把字符串数据逐次获取字符压栈至数组中for (int i=0;i<length;i++){arrayStack.push(val.charAt(i));}/*** 获取*/String newVal = "";for (int i=0;i<arrayStack.length();i++){//是否是一个空栈if(!arrayStack.isEmpty()){//强制类型转换char pop = (char) arrayStack.pop();newVal = newVal + pop;}}if(val.equals(newVal)){return true;}return false;java}}
每次arrayStack.length()循环的数字不是一个固定的值，在递减可以考虑把长度拿出循环，在外面付给一个变量
package com.chentianyu.stack;
public class ArrayStackTest {
public static void main(String[] args) {
/**
* 回文数据
* 回文: 指一个单词(或数据)从前往后，从后往前都是一样的
* 需求: 通过上面以数据模拟栈来判断一个字符是否是一个回文数据
*/
System.out.println(detecation("hello"));
}
//判断是否是回文数据
public static boolean detecation(String val){
/**
* 初始化栈对象
*/
ArrayStack arrayStack = new ArrayStack(10);
/**
* 获取字符串的长度
*/
int length = val.length();
//把字符串数据逐次获取字符压栈至数组中
for (int i=0;i<length;i++){
arrayStack.push(val.charAt(i));
}
/**
* 获取
*/
String newVal = "";
// for (int i=0;i<arrayStack.length();i++){//每次arrayStack.length()循环的数字不是一个固定的值，在递减可以考虑把长度拿出循环，在外面付给一个变量
int len = arrayStack.length();
for (int i=0;i<len;i++){
//是否是一个空栈
if(!arrayStack.isEmpty()){
//强制类型转换
char pop = (char) arrayStack.pop();
newVal = newVal + pop;
}
}
if(val.equals(newVal)){
return true;
}
return false;
}
}
aba是回文数据，返回true
hello不是回文数据,返回false
栈(计算机需求分析)
使用栈完成一个表达式计算结果:**4+3+2+1*5**或者是一个**"4+3+2+1*5"**的数据
思路: 定义俩个栈: 数字栈和符号栈。当获取到的是符号是数字，就会压栈到数字栈中,把符号压入符号栈
- 1.循环遍历出来每一个元素
- 2.如果是数字则压入数字栈，如果是一个符号则压入符号栈。
- 3.如果符号(存在优先级问题)
- 如果符号栈是空，则直接入栈
- 如果符号栈中不为空，则对比栈中符号的优先级；如果优先级小于等于栈中的符号,则先计算数字栈中的数据，将得到的结果再次入栈,再把符号入符号栈(比如栈顶是
*压栈了一个-,-小于*的优先级，所以需要它原本的数据先进行运算得到的结果再次入栈);如果优先级大于符号栈的符号，直接将符号入栈即可
//ArrayStack.java
/**
* 判断是否是一个运算符 + - * /
*/
public boolean isOper(char v){
return v == '+'||v == '-'||v == '*'|| v == '/';
}
/**
* 判断运算符优先级,使用数字表示优先级大小;数字越大优先级越大
*/
public int priority(int oper){
if(oper == '*' || oper == '/'){
return 1;
}else if(oper == '+' || oper == '-'){
return 0;
}else {
return -1;
}
}
/**
* 查看栈顶数据
*/
public int peek(){
return this.stack[top];
}
/**
* 获取栈的容量
*/
public int stackLength(){
return this.stack.length;
}
/**
* 计算俩个数进行运算后的结果
*/
public int calculate(int num1,int num2,int oper){
//计算结果
int result = 0;
switch (oper){
case '+': result = num1 + num2;break;
case '-': result = num2 - num1;break;
case '*': result = num1 * num2;break;
case '/': result = num2 /num1;break;
default:break;
}
return result;
}
验证结果
//判断字符串的
public static void yunSuan(String str){
/**
* 1.需要遍历当前字符串，获取每一个字符
* 2.判断当前字符是一个运算符还是一个数字
* 3.把数字存放在数字栈中，把运算符放在运算符栈中
* 4.运算符栈如果是一个空战，则运算符直接入栈;如果运算符栈中存在其他的运算符，那我们就需要对比运算符的优先级: 新进来的运算优先级如果小于等于原栈中的运算符，那么就需要把原原运算符弹栈,数字栈中的数据进行弹栈运算,运算后的结果重新放入数字栈中
* 如果新的运算符优先级大于原符号栈中运算符，那么新的符号直接入栈
*/
ArrayStack numStack = new ArrayStack(10);//数字栈
ArrayStack symbolStack = new ArrayStack(10);//符号栈
/**
* 获取字符串长度
*/
//拿取数字栈中第一个数字
int temp1 = 0;
//拿取数字栈中第二个数字
int temp2 = 0;
//拿字符
int symbolChar = 0;
//结果
int result = 0;
int length = str.length();
for (int i=0;i<length;i++){
char c = str.charAt(i);
//是否是一个运算符
if(symbolStack.isOper(c)){
String values = "";
//如果不是一个空栈
if(!symbolStack.isEmpty()){
//比较运算符优先级
if(symbolStack.priority(c)<=symbolStack.priority(symbolStack.peek())){
/**
* 1.去符号栈中获取栈顶符号
* 2.去数字栈中获取俩个数字
*/
temp1 = numStack.pop();
temp2 = numStack.pop();
symbolChar = symbolStack.pop();
//result俩个数字之间的运算结果
result = numStack.calculate(temp1,temp2,symbolChar);
//把运算结果再次放入数字栈中
numStack.push(result);
//把当前符号压入符号栈中
symbolStack.push(c);
}else {
//符号直接压进符号栈;如果是空符号栈，将运算符直接压栈
symbolStack.push(c);
}
}else {
//比如 33+44
values += c;
if(i == length-1){
numStack.push(Integer.parseInt(values));
}else {
//如果后面还不是一个符号
char data = str.substring(i+1,i+2).charAt(0);
if (symbolStack.isOper(data)){
numStack.push(Integer.parseInt(values));
//放入栈后清空values
values = "";
}
}
}
}
while (true){
if (symbolStack.isEmpty()){
break;
}
temp1 = numStack.pop();
temp2 = numStack.pop();
symbolChar = symbolStack.pop();
result = numStack.calculate(temp1,temp2,symbolChar);
numStack.push(result);
}
int res = numStack.pop();
System.out.println("结果是:" + res);
}
}
若有收获，就点个赞吧
0 人点赞
