java-算法--栈

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

栈的介绍和描述：

栈的代码实现：

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]);
       }

    }


}

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() {
    }
}

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;
    }

}