• 数据结构与算法：栈（java）

    1.栈的介绍

    栈是限制插入和删除只能在一个位置上进行的线性表。其中，允许插入和删除的一端位于表的末端，叫做栈顶（top），不允许插入和删除的另一端叫做栈底（bottom）。对栈的基本操作有 PUSH（压栈）和 POP （出栈），前者相当于表的插入操作（向栈顶插入一个元素），后者则是删除操作（删除一个栈顶元素）。栈是一种后进先出（LIFO）的数据结构，最先被删除的是最近压栈的元素。 

    弹栈：

    栈实现

    由于栈是一个表，因此任何实现表的方法都可以用来实现栈。主要有两种方式，链表实现和数组实现。

    链表实现栈

    可以使用单链表来实现栈。通过在表顶端插入一个元素来实现 PUSH，通过删除表顶端元素来实现 POP。使用链表方式实现的栈又叫动态栈。动态栈有链表的部分特性，即元素与元素之间在物理存储上可以不连续，但是功能有些受限制，动态栈只能在栈顶处进行插入和删除操作，不能在栈尾或栈中间进行插入和删除操作。

    数组实现栈

    栈也可以用数组来实现。使用数组方式实现的栈叫静态栈。

    2.栈的应用场景

    3.栈的快速入门

    习题1:使用数组来模拟栈的使用

    ArrayStack类

    1. package stack;
    2.  
    3. public class ArrayStack {
    4.  
    5.     //栈的大小
    6.     private int maxStack;
    7.  
    8.     //数组用来模拟栈
    9.     private int[] stack;
    10.  
    11.     //表示栈顶的所在的位置，默认情况下没有数据使用-1
    12.     private int top=-1;
    13.  
    14.     //有参构造
    15.     public ArrayStack(int maxStack){
    16.  
    17.         this.maxStack=maxStack;
    18.         stack=new int[maxStack];
    19.     }
    20.  
    21.     //判断栈是否是空栈
    22.     public boolean isFull(){
    23.         return this.top==maxStack-1;
    24.     }
    25.  
    26.     //判断栈是否是空栈
    27.     public boolean isEmpty(){
    28.         return this.top==-1;
    29.     }
    30.  
    31.     //压栈
    32.     public void push(int val){
    33.         //是否已经栈满
    34.         if(isFull()){
    35.             throw new RuntimeException("此栈已满");
    36.         }
    37.         top++;
    38.         stack[top]=val;
    39.     }
    40.  
    41.     //弹栈
    42.     public int pop(){
    43.         if (isEmpty()){
    44.             throw new RuntimeException("空栈，未找到数据！");
    45.         }
    46.         int value=stack[top];
    47.         top--;
    48.         return value;
    49.     }
    50.  
    51.     //查看栈中所有的元素
    52.     public void list(){
    53.         //是否是空栈
    54.         if (isEmpty()){
    55.             throw new RuntimeException("空栈，未找到数据！");
    56.         }
    57.         for (int i=0;i
    58.             System.out.printf("stack[%d]=%d\n", i ,stack[i]);
    59.         }
    60.     }
    61.  
    62.     //栈中元素存在的个数
    63.     public int length(){
    64.         return this.top+1;
    65.     }
    66. }

    习题2：回文数

    回文： 一个单词、短语或数字，从前往后写和从后往前写都是一样的。比如，单词“dad”、“racecar”就是回文；如果忽略空格和             标点符号，下面这个句子也是回文，“A man, a plan, a canal: Panama”, 数字1001 也是回文。

    思路：使用栈，可以轻松判断一个字符串是否是回文。我们将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串，最后的字符在栈顶，第一个字符在栈底。

    Test类

    1. package stack;
    2.  
    3. import java.util.Arrays;
    4.  
    5. public class Test {
    6.     public static void main(String[] args) {
    7.  
    8.         /**
    9.          * 回文数据
    10.          * 回文：aba racecar 回文就是压栈字符串顺序和出栈字符串顺序相等。
    11.          * 需求：通过上面数组模拟栈，判断字符串是否是一个回文数据
    12.          */
    13.         System.out.println(detecation("aba"));
    14.  
    15.     }
    16.  
    17.     public static boolean detecation(String val){
    18.         //初始化栈对象
    19.         ArrayStack arrayStack=new ArrayStack(10);
    20.  
    21.         //获取字符串长度
    22.         int length = val.length();
    23.         //把字符串数据逐次获取字符压栈到数组中
    24.         for (int i=0;i
    25.             arrayStack.push(val.charAt(i));
    26.         }
    27.  
    28.         //把字符串的数据逐次弹出
    29.         String newVal="";
    30.         int length1=arrayStack.length();
    31.         for (int i=0;i
    32.             //是否是一个空栈
    33.             if (!arrayStack.isEmpty()){
    34.                 char pop= (char) arrayStack.pop();
    35.                 newVal+=pop;
    36.             }
    37.         }
    38.         if (val.equals(newVal)){
    39.             return true;
    40.         }
    41.         return false;
    42.     }
    43.  
    44.  
    45.  
    46.  
    47. }

    测试结果

     

     

     4.栈实现计算器

    首先在ArrayStack类中编写测试类所需要的方法

    ArrayStack类

    1. package stack;
    2.  
    3. public class ArrayStack {
    4.  
    5.     //栈的大小
    6.     private int maxStack;
    7.  
    8.     //数组用来模拟栈
    9.     private int[] stack;
    10.  
    11.     //表示栈顶的所在的位置，默认情况下没有数据使用-1
    12.     private int top=-1;
    13.  
    14.     //有参构造
    15.     public ArrayStack(int maxStack){
    16.  
    17.         this.maxStack=maxStack;
    18.         stack=new int[maxStack];
    19.     }
    20.  
    21.     //判断栈是否是空栈
    22.     public boolean isFull(){
    23.         return this.top==maxStack-1;
    24.     }
    25.  
    26.     //判断栈是否是空栈
    27.     public boolean isEmpty(){
    28.         return this.top==-1;
    29.     }
    30.  
    31.     //压栈
    32.     public void push(int val){
    33.         //是否已经栈满
    34.         if(isFull()){
    35.             throw new RuntimeException("此栈已满");
    36.         }
    37.         top++;
    38.         stack[top]=val;
    39.     }
    40.  
    41.     //弹栈
    42.     public int pop(){
    43.         if (isEmpty()){
    44.             throw new RuntimeException("空栈，未找到数据！");
    45.         }
    46.         int value=stack[top];
    47.         top--;
    48.         return value;
    49.     }
    50.  
    51.     //查看栈中所有的元素
    52.     public void list(){
    53.         //是否是空栈
    54.         if (isEmpty()){
    55.             throw new RuntimeException("空栈，未找到数据！");
    56.         }
    57.         for (int i=0;i
    58.             System.out.printf("stack[%d]=%d\n", i ,stack[i]);
    59.         }
    60.     }
    61.  
    62.     //栈中元素存在的个数
    63.     public int length(){
    64.         return this.top+1;
    65.     }
    66.  
    67.  
    68.     //判断是否是一个运算符+  -  *  |
    69.     public boolean isOper(char v){
    70.         return v=='+' || v=='-' || v=='*' || v=='/';
    71.     }
    72.  
    73.     //判断优先符的优先级，用数字表示优先级的大小，数字越大优先级越大
    74.     public int priority(int oper){
    75.         if (oper=='*' || oper=='/'){
    76.             return 1;
    77.         }else if (oper=='+' || oper=='-'){
    78.             return 0;
    79.         }else {
    80.             return -1;
    81.         }
    82.     }
    83.  
    84.  
    85.     //获取栈的栈顶数据
    86.     public int peek(){
    87.         return this.stack[top];
    88.     }
    89.  
    90.     //获取栈的容量
    91.     public int stackLength(){
    92.         return  this.stack.length;
    93.     }
    94.  
    95.     //计算两个数进行运算后的结果(出栈时是先进后出)
    96.     public int calculate(int num1,int num2,int oper){
    97.         //计算结果
    98.         int result=0;
    99.         switch (oper){
    100.             case '+':
    101.                 result = num1+num2;
    102.                 break;
    103.             case '-':
    104.                 result= num2-num1;
    105.                 break;
    106.             case '*':
    107.                 result=num1*num2;
    108.                 break;
    109.             case '/':
    110.                 result=num2/num1;
    111.                 break;
    112.             default:
    113.                 break;
    114.         }
    115.         return result;
    116.     }
    117.  
    118.  
    119. }

    Test2测试类

    1. package stack;
    2.  
    3. public class Test2 {
    4.     public static void main(String[] args) {
    5.         String str="4+3*2-1";
    6.  
    7.         ArrayStack numStack=new ArrayStack(10);
    8.         ArrayStack symbolStack=new ArrayStack(10);
    9.  
    10.         int temp1=0;
    11.         int temp2=0;
    12.         int symbolChar=0;
    13.         int result=0;
    14.         //获取字符串的长度
    15.         int length = str.length();
    16.  
    17.         String values="";
    18.         for (int i=0;i
    19.             char c = str.charAt(i);
    20.             //判断是否是一个运算符
    21.             if (symbolStack.isOper(c)){
    22.                 //如果不是一个空的符号栈
    23.                 if (!symbolStack.isEmpty()){
    24.                     //比较运算符的优先级
    25.                     if (symbolStack.priority(c)
    26.                         /**
    27.                          * 1.去符号栈中获取栈顶的符号
    28.                          * 2.去数字栈中获取两个数字
    29.                          */
    30.                         temp1 = numStack.pop();
    31.                         temp2=numStack.pop();
    32.                         symbolChar = symbolStack.pop();
    33.                         result=numStack.calculate(temp1,temp2,symbolChar);
    34.  
    35.                         //把运算结果再次放入数字栈中
    36.                         numStack.push(result);
    37.  
    38.                         //把当前符号压入符号栈中
    39.                         symbolStack.push(c);
    40.                     }else {
    41.                         symbolStack.push(c);
    42.                     }
    43.                 }else {
    44.                     //如果是空字符栈，将运算符直接压栈
    45.                     symbolStack.push(c);
    46.                 }
    47.             }else {
    48.                 values+=c;
    49.  
    50.                 if (i==length-1){
    51.                     numStack.push(Integer.parseInt(values));
    52.                 }else {
    53.                     char c1 = str.substring(i + 1, i + 2).charAt(0);
    54.                     if (symbolStack.isOper(c1)){
    55.                         numStack.push(Integer.parseInt(values));
    56.                         values="";
    57.                     }
    58.                 }
    59.             }
    60.         }
    61.  
    62.         while (true){
    63.             if (symbolStack.isEmpty()){
    64.                 break;
    65.             }
    66.             temp1=numStack.pop();
    67.             temp2=numStack.pop();
    68.  
    69.             symbolChar=symbolStack.pop();
    70.  
    71.             result=numStack.calculate(temp1,temp2,symbolChar);
    72.  
    73.             numStack.push(result);
    74.  
    75.         }
    76.  
    77.         int res=numStack.pop();
    78.  
    79.         System.out.println("结果是："+res);
    80.  
    81.     }
    82.  
    83.  
    84. }

    测试结果

     

     

     

  • 相关阅读:
    SpringBoot介绍及自动装配
    IMX6ULL学习笔记（7）——通过SD卡启动U-Boot
    Spring基础：接口实现AOP
    【批处理DOS-CMD命令-汇总和小结】-将文件夹映射成虚拟磁盘——subst
    @FeignClient configuration参数配置
    TS泛型的使用
    《第一行代码》读书笔记(2)—日志工具Log
    MFC3d立体按钮制作
    华为hcip考试，询问您解答
    MATLAB环境下基于稀疏最大谐波噪声比反卷积的信号处理方法
  • 原文地址：https://blog.csdn.net/weixin_59334478/article/details/127459264