链表完成栈模拟和栈模拟计数器原理

package shuJuJieGouYuSuanFa.stack;
 
/**
 * @ClassName ListStackDom
 * @Author 瞿肖
 * @Date 2022/7/30 19:02
 */
public class ListStackDom {
    public static void main(String[] args) {
        ListStackUtil a = new ListStackUtil();
        ListStack l1 = new ListStack(1);
        ListStack l2 = new ListStack(2);
        ListStack l3 = new ListStack(3);
        a.push(l1);
        a.push(l2);
        a.push(l3);
        a.pop();
        a.pop();
        a.pop();
        a.pop();
    }
}
 
class ListStackUtil {
    public ListStack fist = new ListStack(-1);
 
    public boolean isEmpty() {
        return fist.next == null;
    }
 
    public void push(ListStack data) {
        ListStack t = fist;
        while (true) {
            if (t.next == null) {
                break;
            }
            t = t.next;
        }
        t.next = data;
        data.per = t;
    }
 
    public void pop() {
        if (isEmpty()) {
            System.out.println("为空！");
            return;
        }
        ListStack t = fist.next;
        while (true) {
            if (t.next == null) {
                break;
            }
            t = t.next;
        }
        System.out.println(t);
        t.per.next = t.next;
        if (t.next != null) {
            t.next.per = t.per;
        }
    }
}
 
class ListStack {
    public ListStack(int value) {
        this.value = value;
    }
 
    public int value;
 
    @Override
    public String toString() {
        return ""+value;
    }
 
    public ListStack next;
    public ListStack per;
}

和双向链表相同，注意最后一个取出的时候，不用将后一个的前指针指向本元素的前方

计数器模拟：

package shuJuJieGouYuSuanFa.stack;
 
/**
 * @ClassName jsq
 * @Author 瞿肖
 * @Date 2022/7/30 20:01
 */
public class jsq {
    public static void main(String[] args) {
        jsqStack dataStack = new jsqStack(10);
        jsqStack UtilStack = new jsqStack(10);
        String s = "32+2*2-4";
        int indx = 0;
        String date = "";
        int fh = 0;
        int num1 = 0;
        int num2 = 0;
        int res = 0;
        char c = ' ';
        while (true) {
            c = s.charAt(indx);
            if (dataStack.isfh(c)) {//判断数值或运算符
                if (!UtilStack.isEmpty()) {//运算符栈不为空
                    if (UtilStack.priority(c) <= UtilStack.priority(UtilStack.stak())) {//优先级
                        num1 = dataStack.pop();
                        num2 = dataStack.pop();
                        fh = UtilStack.pop();
                        res = dataStack.cal(num1, num2, fh);
                        dataStack.push(res);
                        UtilStack.push(c);
                    } else {//优先级大于就入栈
                        UtilStack.push(c);
                    }
                } else {//运算符栈为空
                    UtilStack.push(c);
                }
            } else {//数值
                date += c;
                if (indx <= s.length() - 2) {//是否到了最后一位，最后一位固定为数值
                    if (dataStack.isfh(s.charAt(indx + 1))) {//往后查看一位，是否为数值
                        dataStack.push(Integer.parseInt(date));
                        date = "";
                    }
                } else {
                    dataStack.push(Integer.parseInt(date));
                }
            }
            indx++;
            if (indx >= s.length()) {
                break;
            }
        }
        while (true) {
            if (UtilStack.isEmpty()) {
                break;
            }
            num1 = dataStack.pop();
            num2 = dataStack.pop();
            fh = UtilStack.pop();
            res = dataStack.cal(num1, num2, fh);
            dataStack.push(res);
        }
        System.out.println(s + "=" + dataStack.pop());
    }
}
 
class jsqStack {
    public int maxSize;
    public int[] arr;
    public int top = -1;
 
    public jsqStack(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
    }
 
    public boolean isEmpty() {
        return top == -1;
    }
 
    public boolean isFull() {
        return top == maxSize - 1;
    }
 
    public void push(int value) {
        if (isFull()) {
            System.out.println("已满");
            return;
        }
        top++;
        arr[top] = value;
    }
 
    public int pop() {
        if (isEmpty()) {
            System.out.println("为空");
            return -1;
        }
        int t = arr[top];
        arr[top] = 0;
        top--;
        return t;
    }
 
    public boolean isfh(int fh) {
        return fh == '+' || fh == '-' || fh == '*' || fh == '/';
    }
 
    public int priority(int fh) {
        if (fh == '*' || fh == '/') {
            return 1;
        } else {
            return 0;
        }
    }
 
    public int stak() {
        return arr[top];
    }
 
    public int cal(int a, int b, int fh) {
        int res = 0;
        switch (fh) {
            case '+':
                res = a + b;
                break;
            case '-':
                res = b - a;
                break;
            case '*':
                res = a * b;
                break;
            case '/':
                res = b / a;
                break;
        }
        return res;
    }
}

把每个数据取出，

判断运算符或数字

为运算符时判断运算符栈是否为空，是就直接入栈

否则判断运算符栈头优先级是否大于等于本次运算符，大于就将数字栈出栈两个，运算符栈出栈一个，进行运算，结果入数字栈，

遍历到最后一位后，退出循环，进入计算循环：

进行数字栈出栈两个，运算符栈出栈一个进行运算，结果入数字栈，直到数字栈剩一个时，就是答案吧