一、栈

1.特点：栈是先进后出的。
2.数组模拟栈的分析图
三、栈和队列 - 图1
实现 栈的 思路分析

  1. 使用数组来模拟栈

  2. 定义一个 top 来表示栈顶，初始化 为 -1

  3. 入栈的操作，当有数据加入到栈时， top++; stack[top] = data;

  4. 出栈的操作， int value = stack[top]; top—, return value

代码实现栈

  1. public class ArrayStack {
  2.     //栈需求实现
  4.     private int maxLength;
  5.     private int[] stack;
  6.     private int top = -1;
  8.     public ArrayStack(int maxLength) {
  9.         this.maxLength = maxLength;
  10.         stack = new int[maxLength];
  11.     }
  13.     public boolean isFull() {
  14.         return top == maxLength - 1;
  15.     }
  17.     public boolean isEmpty() {
  18.         return top == -1;
  19.     }
  21.     public void push(int val) {
  22.         if (isFull()) {
  23.             throw new RuntimeException("对不起，已满");
  24.         }
  25.         top++;
  26.         stack[top] = val;
  27.     }
  29.     public int pop() {
  30.         if (isEmpty()) {
  31.             throw new RuntimeException("对不起，是空栈");
  32.         }
  33.         int value = stack[top];
  34.         top--;
  35.         return value;
  36.     }
  38.     public void list() {
  39.         if (isEmpty()) {
  40.             throw new RuntimeException("对不起，是空栈");
  41.         }
  42.         for (int i = 0; i < stack.length; i++) {
  43.             System.out.printf("stack[%d]=%d\t", i, stack[i]);
  44.         }
  45.     }
  46.     //栈中元素存在的个数
  47.     public int length(){
  48.         return this.top+1;
  49.     }
  50. }

判断回文(利用栈)

  1. public class TestApp {
  2.     //判断回文
  3.     //hello   olleh 不是一个回文
  5.     public static void main(String[] args) {
  6.         System.out.println(detecation("aba"));
  7.     }
  8.     public static boolean detecation(String val){
  9.         ArrayStack  arrayStack = new ArrayStack(10);
  10.         //获取字符串长度
  11.         int length =val.length();
  12.         //放入栈
  13.         for(int i =0;i<length;i++){
  14.             //注意：这里将a转化成97
  15.             arrayStack.push(val.charAt(i));
  16.         }
  17.         //获取
  18.         String newVal = "";
  19.         int length1=arrayStack.length();
  20.         for(int i =0;i<length1;i++){
  21.             if(!arrayStack.isEmpty()){
  22.                 char pop =(char)arrayStack.pop();
  23.                 newVal=newVal+pop;
  24.             }
  25.         }
  28.         /*  equals方法的源代码:
  29.                 public boolean euqals(Object obj){
  30.                     return(this==obj);
  31.          */
  33.         if(val.equals(newVal)){
  34.             return true;
  35.         }
  36.         return  false;
  37.     }
  38. }

例题：计算机需求分析

三、栈和队列 - 图2

  1. public class ArrayStack {
  2.     //栈需求实现
  4.     private int maxLength;
  5.     private int[] stack;
  6.     private int top = -1;
  8.     public ArrayStack(int maxLength) {
  9.         this.maxLength = maxLength;
  10.         stack = new int[maxLength];
  11.     }
  13.     public boolean isFull() {
  14.         return top == maxLength - 1;
  15.     }
  17.     public boolean isEmpty() {
  18.         return top == -1;
  19.     }
  21.     public void push(int val) {
  22.         if (isFull()) {
  23.             throw new RuntimeException("对不起，已满");
  24.         }
  25.         top++;
  26.         stack[top] = val;
  27.     }
  29.     public int pop() {
  30.         if (isEmpty()) {
  31.             throw new RuntimeException("对不起，是空栈");
  32.         }
  33.         int value = stack[top];
  34.         top--;
  35.         return value;
  36.     }
  38.     public void list() {
  39.         if (isEmpty()) {
  40.             throw new RuntimeException("对不起，是空栈");
  41.         }
  42.         for (int i = 0; i < stack.length; i++) {
  43.             System.out.printf("stack[%d]=%d\t", i, stack[i]);
  44.         }
  45.     }
  47.     //栈中元素存在的个数
  48.     public int length() {
  49.         return this.top + 1;
  50.     }
  52.     //判断是否是一个运算符 + - * /
  53.     public boolean isOper(char v) {
  54.         return v == '+' || v == '-' || v == '*' || v == '/';
  55.     }
  58.     //判断运算符优先级，数字越大的优先级越大
  59.     public int priority(int oper) {
  60.         if (oper == '*' || oper == '/') {
  61.             return 1;
  62.         } else if (oper == '+' || oper == '-') {
  63.             return 0;
  64.         } else {
  65.             return -1;
  66.         }
  67.     }
  69.     //获取栈顶数据
  70.     public int peek() {
  71.         return this.stack[top];
  72.     }
  74.     //获取栈容量
  75.     public int stackLength() {
  76.         return this.stack.length;
  77.     }
  79.     /**
  80.      * 计算两个数进行运算后的结果
  81.      * 2+3
  82.      * 3:num1,2:num2
  83.      */
  84.     public int calculate(int num1, int num2, int oper) {
  85.         int result = 0;
  86.         switch (oper) {
  87.             case '+':
  88.                 result = num1 + num2;
  89.                 break;
  90.             case '-':
  91.                 result = num2 - num1;
  92.                 break;
  94.             case '*':
  95.                 result = num1 * num2;
  96.                 break;
  98.             case '/':
  99.                 result = num2 / num1;
  100.                 break;
  102.             default:
  103.                 break;
  104.         }
  105.         return result;
  107.     }
  108. }
  1. public class TestStack {
  2.     public static void main(String[] args) {
  3.         String str="4+3+2*3-1";
  4.         //1、需要遍历字符串，获取每一个字符。
  5.         //2、判断当前字符是一个运算符还是数字
  6.         //3、把数字放入数字栈，把运算符放入运算符栈
  7.         //4、运算符栈:如果是一个空栈，那么运算符直接入栈，如果运算符栈中已经
  8.         //有其他运算符就需要先对比运算符优先级，新进来的运算符如果小于等于原栈中运算符，
  9.         //那么需要把原运算符弹出来，数字栈中的数字进行弹栈，进行运算，运算后的结果重新
  10.         //放入数字栈，新运算符直接入栈，如果新的运算符优先级大于原栈中的运算符，那么运算符直接入栈。
  11.         ArrayStack numStack = new ArrayStack(10);
  12.         ArrayStack symbolStack = new ArrayStack(10);
  14.         //获取字符串的长度
  16.         int temp1=0;
  17.         int temp2=0;
  18.         int symbolChar = 0;
  19.         int result = 0;
  20.         int length =str.length();
  21.         String values = "";
  22.         for(int i =0;i<length;i++){
  23.             char c =str.charAt(i);
  24.             //是否是一个运算符
  25.             if(symbolStack.isOper(c)){
  26.                 if(!symbolStack.isEmpty()){
  27.                     //比较运算符的优先级
  28.                     if(symbolStack.priority(c)<=symbolStack.priority(symbolStack.peek())){
  29.                         //1、去符号栈中获取栈顶的符号
  30.                         //2、去数字栈中获取两个数字
  31.                         temp1 = numStack.pop();
  32.                         temp2 = numStack.pop();
  33.                         symbolChar = symbolStack.pop();
  34.                        result= numStack.calculate(temp1,temp2,symbolChar);
  35.                        //把运算结果再次放入数字栈中
  36.                         numStack.push(result);
  38.                         //把当前符号压入符号栈中
  39.                         symbolStack.push(c);
  40.                     }else {
  41.                         symbolStack.push(c);
  42.                     }
  43.                 }else{
  44.                     //如果是空符号栈，将运算结果直接压栈
  45.                     symbolStack.push(c);
  46.                 }
  47.             }else {
  48.                 //比如  33+44
  49.                 values +=c;
  50.                 if(i==length-1){
  51.                     numStack.push(Integer.parseInt(values));
  52.                 }else{
  53.                     //substring包括起始，不包括终止
  54.                     char data = str.substring(i+1,i+2).charAt(0);
  55.                     if(symbolStack.isOper(data)){
  56.                         numStack.push(Integer.parseInt(values));
  57.                         values="";
  58.                     }
  59.                 }
  60.             }
  61.         }
  62.         while (true){
  63.             if(symbolStack.isEmpty()){
  64.                 break;
  65.             }
  66.            temp1= numStack.pop();
  67.             temp2= numStack.pop();
  69.             symbolChar = symbolStack.pop();
  71.            result= numStack.calculate(temp1,temp2,symbolChar);
  72.            numStack.push(result);
  74.         }
  75.       int res = numStack.pop();
  76.         System.out.println("结果是"+res);
  78.     }
  79. }

中缀转后缀表达式

  1. package test;
  3. public class ArrayStack {
  4.     //数组的最大长度
  5.     private int maxLength;
  6.     //定义一个数组
  7.     private int[] stack;
  8.     //初始化指针为-1
  9.     private int top = -1;
  10.     //通过构造方法构造数组
  11.     public ArrayStack(int maxLength) {
  12.         this.maxLength = maxLength;
  13.         stack = new int[maxLength];
  14.     }
  15.     //判断是否满
  16.     public boolean isFull() {
  17.         //如果top指针与顶端相等则放回为true
  18.         return top == maxLength - 1;
  19.     }
  20.     //判断是否空
  21.     public boolean isEmpty() {
  22.         //如果top指针与-1相等则放回为true
  23.         return top == -1;
  24.     }
  25.     //入栈
  26.     public void push(int val) {
  27.         if (isFull()) {
  28.             throw new RuntimeException("对不起，已满");
  29.         }
  30.         //将指针往上移一位
  31.         top++;
  32.         //将加入的数移动到相应的位置
  33.         stack[top] = val;
  34.     }
  35.     //出栈
  36.     public int pop() {
  37.         if (isEmpty()) {
  38.             throw new RuntimeException("对不起，是空栈");
  39.         }
  40.         //将这个数保存到一个变量
  41.         int value = stack[top];
  42.         //指针往下移动一位
  43.         top--;
  44.         //将这个值返回
  45.         return value;
  46.     }
  47. }
  1. package test;
  4. public class PostInfix {
  5.     /*（在实际代码中我们添加了大于10的数字情况的处理）
  6.      1:从左到右顺序读取表达式中的字符:
  7.      2.是操作数,复制到后缀表达式字符串
  8.      3:是左括号，把字符压入栈中
  9.      4:是右括号，从栈中弹出符号到后缀表达式，直到遇到左括号，然后把左括号弹出。
  10.      5:是操作符，如果此时栈顶操作符优先级大于或等于此操作符，弹出栈顶操作符到后缀表达
  11.     式,直到发现优先级级更低的元素位置，把操作符压入。
  12.      6:读到输入的末尾，将栈元素弹出直到该栈变成空栈，将符号写到后缀表达式中
  13. */
  14.     public String doTransfer(String str){
  15.         ArrayStack arrayStack = new ArrayStack(20);
  16.         StringBuffer stringBuffer = new StringBuffer();
  17.         String values="";
  18.         char[] chars=str.toCharArray();
  20.         // 1:从左到右顺序读取表达式中的字符:
  21.         for(int i=0;i<chars.length;i++){
  22.             char c = (char)chars[i];
  23.             // 1.1是操作符，进行分级操作
  24.             if(c=='+'||c=='-'){
  25.                 doOperation(arrayStack,stringBuffer,c,1);
  26.             }else if(c=='*'||c=='/'){
  27.                 doOperation(arrayStack,stringBuffer,c,2);
  29.                 //1.2如果是左括号压栈
  30.             }else  if (c=='('){
  31.                 arrayStack.push(c);
  33.                 //1.3如果是右括号...
  34.             }else  if(c==')'){
  35.                 doRightBracket(arrayStack,stringBuffer);
  38.                 // 1.4是操作数,复制到后缀表达式字符串
  39.             }else {
  40.                 values+=c;
  42.                 char data = str.substring(i+1,i+2).charAt(0);
  43.                 if(data<49||data>57){
  44.                     stringBuffer.append(values+",");
  45.                     values="";
  46.                 }
  48.             }
  49.         }
  50.         while (!arrayStack.isEmpty()){
  51.             stringBuffer.append((char)arrayStack.pop());
  52.         }
  54.         String news=stringBuffer.toString();
  55.           news=  news.replace(","," ");
  56.         return  news;
  57.     }
  59.     public  void doOperation(ArrayStack arrayStack,StringBuffer buffer,char c,int  level){
  60.         //1.依次从栈顶获取一个值
  61.         while(!arrayStack.isEmpty()){
  62.             char topc =(char)arrayStack.pop();
  63.             //2.这个值跟传入的数据作比较
  64.             //2.1栈顶数据是(,不动就是把他压回去
  65.             if(topc=='('){
  66.                 arrayStack.push(topc);
  67.                 break;
  68.             }else {
  69.                 //首先获取到栈顶元素所对应的级别
  70.                 int topLevel=0;
  71.                 if(topc=='+'|| topc=='-'){
  72.                     topLevel=1;
  73.                 }else {
  74.                     topLevel=2;
  75.                 }
  76.                 //2.2栈顶数据优先级别大于传入的，输出到后缀表达式
  77.                 if(topLevel>=level){
  78.                     buffer.append(topc+",");
  79.                     break;
  80.                 }else {
  81.                     //2.3如果栈顶的优先级小于传入的，不动
  82.                     arrayStack.push(topc);
  83.                     break;
  84.                 }
  85.             }
  86.         }
  87.         //3.找到位置后，把传入的操作符压入
  88.         arrayStack.push(c);
  89.     }
  91.     public  void doRightBracket(ArrayStack arrayStack,StringBuffer buffer){
  92.         //1.从栈中弹出数据，输出到后缀表达式
  93.         while (!arrayStack.isEmpty()){
  94.             char topc=(char)arrayStack.pop();
  95.             //2.直到遇到"("为止
  96.             if(topc=='('){
  97.                 break;
  98.             }else {
  99.                 buffer.append(topc+",");
  100.             }
  101.         }
  102.     }
  104.     public static  void main(String[] args){
  105.         PostInfix t =new PostInfix();
  106.         String s= "(33+3+2)/5-((77+8)*4-5)";
  107.         System.out.println("中缀的表现形式:"+s);
  110.         String ret=t.doTransfer("(33+3+2)/5-((77+8)*4-5)");
  111.         System.out.println("后缀的表现形式"+"res==="+ret);
  112.     }
  113. }

image.png

二、队列

1. 队列遵循先入先出原则。放的时候从尾部放，取得时候从 头部取。
K~0PU2_EZN54O6I0KG(I9]I.png

2.环形队列

三、栈和队列 - 图5

1： front变量的含义：front指向队列的第一个元素。 front 的初始值 = 0
2： rear 变量的含义: rear指向队列的最后一个元素的后一个位置。因为希望出一个空间作为约定。 rear 的初始值 = 0
3. 当队列满时，条件是 (rear + 1) % maxSize == front 【满】
4. 对队列为空的条件， rear == front 空
5. 当我们这样分析， 队列中有效的数据的个数 (rear + maxSize - front) % maxSize
6. 我们就可以在原来的队列上修改得到，一个环形队列

3: (7+1)%8==0;
5: (1+8-3)%8=6;

  1. import java.util.Scanner;
  3. public class shuzu_huanxingduilie {
  5.     public static void main(String[] args) {
  6.         // TODO 自动生成的方法存根
  7.         /*
  8.          * 用数组来模拟环形队列
  9.          * 环形是通过取模（%）来实现的，取模来循环下标，满了就回到原点
  10.          * 在上一个代码的基础是进行修改
  11.          */
  12.         //测试
  13.         CircleArray queue = new CircleArray(4);//这里设置4，其有效内存是3，因为最后一个是要空出来的
  14.         Scanner scanner = new Scanner(System.in);//获取控制台
  15.         char key = ' ';//用来接受用户输入
  16.         boolean loop = true;//用来控制系统是否退出
  17.         while(loop) {
  18.             System.out.println("s(show):显示队列");
  19.             System.out.println("e(exit):退出程序");
  20.             System.out.println("a(add):添加数据到队列");
  21.             System.out.println("g(get):从队列中取出数据");
  22.             System.out.println("h(head):查看队列头的数据");
  23.             System.out.println("\n请输入指令：");
  24.             key = scanner.next().charAt(0);//接收一个字符（0就是一个）
  25.             switch(key) {
  26.             case's':
  27.                 queue.showQueue();
  28.                 break;
  29.             case'a':
  30.                 System.out.println("请输入需要添加的数");
  31.                 int value = scanner.nextInt();
  32.                 queue.addQueue(value);
  33.                 break;
  34.             case'g':
  35.                 try {
  36.                     int res = queue.getQueue();//上抛了异常,所以要处理异常
  37.                     System.out.printf("取出的数据是%d\n",res);
  38.                 }catch(Exception e) {
  39.                     System.out.println(e.getMessage());
  40.                 }
  41.                 break;
  42.             case'h':
  43.                 try {
  44.                     int res = queue.headQueue();
  45.                     System.out.println("队列头数据是"+res);
  46.                 }catch(Exception e) {
  47.                     System.out.println(e.getMessage());
  48.                 }
  49.                 break;
  50.             case'e':
  51.                 scanner.close();//关闭控制台
  52.                 loop = false;
  53.                 break;
  54.             }
  55.         }
  56.         System.out.println("程序退出成功!");
  57.     }
  58. }
  61. //使用数组模拟队列，编写一个类ArrayQueue类
  62. class CircleArray {
  63.     private int maxSize;//表示数组最大容量
  64.     private int front;//队列头
  65.     private int rear;//队列尾
  66.     private int[] arr;//该数组用来存放数据，模拟队列
  68.     //创建队列的构造器
  69.     public CircleArray(int arrMaxSize) {
  70.         maxSize = arrMaxSize;//最大容量
  71.         arr = new int[maxSize];//创建数组
  72.         front = 0;//指向队列头部，分析出front是指向队列头所在位置（包含）
  73.         rear = 0;//指向队列尾的后一位
  74.     }
  76.     //判断队列是否满
  77.     public boolean isFull() {
  78.         return rear == maxSize-1;
  79.     }
  80.     //判断队列是否为空
  81.     public boolean isEmpty() {
  82.         return rear == front;
  83.     }
  85.     //添加数据到队列
  86.     public void addQueue(int n) {
  87.         if(isFull()) {
  88.             System.out.println("队列已满，无法添加");
  89.             return;
  90.         }
  91.         arr[rear] = n;//修改队尾所指定的数据为要添加的数据，添加完成
  92.         //将rear后移，这里必须考虑取模，避免rear溢出；取模来实现环形
  93.         rear = (rear + 1) % maxSize;
  94.     }
  96.     //获取队列数据，出队列
  97.     public int getQueue() {
  98.         if(isEmpty()) {
  99.             //因为需要返回值，没有数据可取时，可以抛出异常
  100.             throw new RuntimeException("队列为空，没有数据可以取出");
  101.         }
  102.         //这里需要分析出front是指向队列的第一个元素
  103.         //1、先把front对应的值保存到一个临时变量
  104.         //2、将front后移，需要取模
  105.         //将临时变量的值返回（如果前面直接把front的值返回，就没有后移的机会了）
  106.         int value = arr[front];
  107.         front = (front + 1) % maxSize;//front一直在数组里面，不会溢出，因为已经取模
  108.         return value;
  109.     }
  111.     //打印数组所有数据（队列在其中）
  112.     public void showQueue() {
  113.         if(isEmpty()) {
  114.             System.out.println("队列为空，没有数据可以显示");
  115.             return;
  116.         }
  117.         //思路：从front开始遍历，遍历有效个数size()个
  118.         for(int i=front;i<front+size();i++) {
  119.             System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]);
  120.         }
  121.     }
  123.     //求出队列中的有效个数
  124.     public int size() {
  125.         return (rear + maxSize - front) % maxSize;
  126.     }
  128.     //显示队列的头数据（是显示，不是取出，还在队列里面）
  129.     public int headQueue() {
  130.         if(isEmpty()) {
  131.             throw new RuntimeException("队列为空，不存在头数据");
  132.         }
  133.         return arr[front];
  134.     }
  135. ｝