java-算法--栈

2021/7/10 1:07:50

本文主要是介绍java-算法--栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

  1. 栈的介绍和描述:
    1.  

       

       

       

       

       

       

  2. 栈的代码实现:
      1. package com.model.stack;
        
        import java.util.Arrays;
        import java.util.Scanner;
        
        /**
         * @Description:测试类
         * @Author: 张紫韩
         * @Crete 2021/7/9 16:12
         * 演示栈的实现,数组实现栈的出栈(pop)和入栈(push)
         */
        public class StackDemo01 {
            public static void main(String[] args) {
                arrayStack stack = new arrayStack(5);
                Scanner scanner = new Scanner(System.in);
                char key = ' ';
                boolean loop = true;
                while (loop) {
                    System.out.println("s(show):显示队列");
                    System.out.println("e(exit):退出程序");
                    System.out.println("p(push):添加数据到队列");
                    System.out.println("pop(pop):从队列中取出数据");
                    System.out.println("h(head):查看队列的头数据");
                    key = scanner.next().charAt(0);
                    switch (key) {
                        case 'p':
                            try {
                                System.out.println("请输入一个数据,加入到队列中");
                                int value = scanner.nextInt();
                                stack.push(value);
                            } catch (Exception e) {
                                e.printStackTrace();
                            }
                            break;
                        case 'o':
                            try {
                                System.out.printf("取出的栈的数据是:%d\n", stack.pop());
                            } catch (Exception e) {
                                e.printStackTrace();
                            }
                            break;
                        case 'e':
                            scanner.close();
                            loop = false;
                            break;
                        case 's':
                            stack.show();
                            break;
                        case 'h':
                            System.out.printf("队列的头是:%d\n", stack.getHead());
                            break;
                        default:
                            break;
        
                    }
                }
                System.out.println("退出程序~");
            }
        }
        class arrayStack{
            private int head=-1;
            private int[] stack=null;
            private int maxSize;
            public arrayStack(int maxSize) {
                this.maxSize=maxSize;
                stack=new int[maxSize];
            }
        
            //判断是否为空
            public boolean isEmpty(){
                if (head==-1){
                    return true;
                }
                return false;
            }
        
            public int getHead() {
                return stack[head];
            }
        
            //    判断是否已经满了
            public boolean isFull(){
                if (head==maxSize-1) {
                    return true;
                }
                return false;
        
            }
        //    压栈
            public void push(int num){
                if(isFull()){
                   throw new RuntimeException("队列已经满了,不能进行添加了");
                }
                head++;
                stack[head]=num;
            }
        //    弹栈
            public int pop(){
                if (isEmpty()){
                   throw new RuntimeException("队列已经为空,不能在取出");
                }
                int val=stack[head];
                head--;
                return val;
        
            }
            public void show(){
                if (isEmpty()){
                    System.out.println("栈为空,没有数据");
                    return;
                }
               for (int i=head;i>=0;i--){
                   System.out.println(stack[i]);
               }
        
            }
        
        
        }

      1. package com.model.stack;
        
        /**
         * @Description:测试类
         * @Author: 张紫韩
         * @Crete 2021/7/9 17:27
         * 用链表模拟栈
         */
        public class StackDemo02 {
            public static void main(String[] args) {
        //        LinkedList list = new LinkedList();
        //        list.add(new Node(1,"a"));
        //        list.add(new Node(2,"a"));
        //        list.add(new Node(3,"a"));
        //        list.show();
        
                LinkedListStock stock = new LinkedListStock();
                stock.push(new Node(1,"a"));
                stock.push(new Node(2,"b"));
                stock.push(new Node(3,"c"));
                stock.push(new Node(4,"d"));
                stock.show();
                System.out.println(stock.pop());
                System.out.println(stock.pop());
                System.out.println(stock.pop());
                System.out.println(stock.pop());
                System.out.println(stock.pop());
        
        
        
            }
        }
        
        class LinkedListStock{
           private LinkedList list=new LinkedList();
           private Node top= list.head;
           public boolean isEmpty(){
               if (top==list.head){
                   return true;
               }
               return false;
           }
           public void push(Node node){
               list.add(node);
               top=node;
           }
           public Node pop(){
               if (isEmpty()){
                   throw new RuntimeException("栈为空,不能进行pop");
               }
               Node temp= list.head;
               Node temp2;
               while(true){
                   if (temp.next==top){
                       top=temp;
                        temp2=temp.next;
                       temp.next=null;
                       break;
                   }
                   temp=temp.next;
               }
               return temp2;
           }
           public void show(){
               if (isEmpty()){
                   System.out.println("栈为空");
                   return;
               }
               Node temp= list.head;
               Node temp2=top;
               while(true){
                   if (temp2==list.head.next){
                       System.out.println(temp2);
                       break;
                   }
                   if (temp.next==temp2){
                       System.out.println(temp2);
                       temp2=temp;
                       temp= list.head;
                   }
        
                   temp=temp.next;
               }
        
           }
        
        
        }
        class LinkedList{
            public Node head=new Node();
            public void add(Node node){
                Node temp=head;
                while(true){
                    if (temp.next==null){
                        temp.next=node;
                        break;
                    }
                    temp=temp.next;
                }
            }
            public void show(){
                if (isEmpty()){
                    return;
                }
                Node temp=head.next;
                while(true){
                    if (temp==null){
                        break;
                    }
                    System.out.println(temp.toString());
                    temp=temp.next;
                }
            }
            public boolean isEmpty(){
                if (head.next==null){
                    return true;
                }
                return false;
            }
        }
        
        class Node{
            public int id;
            public String name;
            public Node next;
        
            public Node(int id, String name) {
                this.id = id;
                this.name = name;
            }
        
            @Override
            public String toString() {
                return "Node{" +
                        "id=" + id +
                        ", name='" + name + '\'' +
                        '}';
            }
        
            public Node() {
            }
        }
      1. package com.model.stack;
        
        /**
         * @Description:测试类
         * @Author: 张紫韩
         * @Crete 2021/7/9 20:11
         * 使用Stock实现综合计算器
         */
        public class StockDemo03 {
            public static void main(String[] args) {
        
                String str="7+2*6-4";
                String str1="70*2+2*6-4";//错误的,思考如何处理多位数的计算问题
                System.out.println(res(str1));
        
            }
            public static int res(String str){
                int res=0;
                String numKeep="";
                arrayStack numStack = new arrayStack(5);
                arrayStack operatorStack = new arrayStack(5);
                for (int i=0;i<str.length();i++){
                    char c = str.charAt(i);
                    int distinguish = distinguish(c);
                    if (distinguish==0){//是操作符
                       if (operatorStack.isEmpty()){//为空直接加入到空队列中
                           operatorStack.push(c);
                       }else{
                           int operator = operator(c);
                           int operator1 = operator((char) operatorStack.getHead());
                           if (operator<=operator1){
                               int num1 = numStack.pop();
                               int num2 = numStack.pop();
                               int pop = operatorStack.pop();
                               int calculation = calculation(num1, num2, (char) pop);
                               numStack.push(calculation);
                               operatorStack.push(c);
                           }if (operator>operator1){
                               operatorStack.push(c);
                           }
                       }
                    }
                    else{
                        //添加数的入栈式,要判断是否是多位数
                       numKeep+=c;
                       if (i==str.length()-1){
                           numStack.push(Integer.parseInt(numKeep));
                       }else {
                           if (distinguish(str.charAt(i + 1)) == 0) {
                               numStack.push(Integer.parseInt(numKeep));
                               numKeep = "";
                           }
                       }
        
        
                    }
        
                }
                while(true){
                    if (operatorStack.isEmpty()){
                        break;
                    }
                    int num1=numStack.pop();
                    int num2=numStack.pop();
                    int calculation = calculation(num2, num1, (char) operatorStack.pop());
                    numStack.push(calculation);
                }
                res= numStack.getHead();
                return res;
            }
            //返回操作符的优先级
            public static int operator(char c){
                if (c=='+'||c=='-'){
                    return 0;
                }else if(c=='*'||c=='/'){
                    return 1;
                }else {
                    return -1;
                }
            }
        //    返回字符是操作符还是数字
            public static int distinguish(char c){
                if (c=='+'||c=='-'||c=='*'||c=='/') {
                    return 0;
                }
                if('0'>=c&&c<='9'){
                    return 1;
                }
                return -1;
        
            }
        
        //    返回两个数计算的结果
            public static int calculation(int num1,int num2,char c){
              int res=0;
              switch (c){
                  case '+':
                      res=num1+num2;
                      break;
                  case '-':
                      res=num1-num2;
                      break;
                  case '*':
                      res=num1*num2;
                      break;
                  case '/':
                      res=num1/num2;
                      break;
                  default:
                      break;
              }
              return res;
            }
        
        }
  3. 前缀,中缀,后缀表达式
    1.  
    2.  

       

       

       

        


这篇关于java-算法--栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程