栈

栈(stack)

• 栈是一个先入后出的有序列表
• 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底
• 根据栈的定义可知，最先放入栈中的元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

栈的思路分析

• 使用数组来模拟栈
• 定义一个top来表示栈顶，初始化为-1
• 入栈的操作，当有数据加入到栈时，top++;stack[top]=value;
• 出栈的操作，int value=stack[top];top–;return value;

数组模拟栈

import java.util.Scanner;

public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean loop = true;// 控制是否退出菜单
        Scanner sc = new Scanner(System.in);
        while (loop) {
            System.out.println("show:表示显示栈");
            System.out.println("exit:退出程序");
            System.out.println("push:表示添加数据到栈（入栈）");
            System.out.println("pop:表示从栈取出数据（出栈）");
            System.out.println("请输入你的选择：");
            key = sc.next();
            switch (key) {
            case "show":
                stack.list();
                break;
            case "push":
                System.out.println("请输入一个数：");
                int value = sc.nextInt();
                stack.push(value);
                break;
            case "pop":
                try {
                    int res = stack.pop();
                    System.out.printf("出栈的数据是%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case "exit":
                sc.close();
                loop = false;
                break;
            default:
                break;
            }
        }
        System.out.println("程序退出~");
    }
}

class ArrayStack {
    private int maxSize;
    private int top;
    private int[] stack;

    public ArrayStack(int maxSize) {
        top = -1;
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public void push(int value) {
        if (isFull()) {
            System.out.println("栈满，不能添加数据~");
            return;
        }
        top++;
        stack[top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空,没有数据~");
        }
        int value = stack[top];
        top--;
        return value;
    }

    public void list() {
        if (isEmpty()) {
            System.out.println("栈空，没有数据~");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }
}

链表模拟栈

public class LinkedListStackDemo {
    public static void main(String[] args) {
        LinkedListStack stack = new LinkedListStack();
        Node node1 = new Node(10);
        Node node2 = new Node(20);
        Node node3 = new Node(30);
        Node node4 = new Node(40);
        Node node5 = new Node(50);
        System.out.println("入栈~");
        stack.push(node1);
        stack.push(node2);
        stack.push(node3);
        stack.push(node4);
        stack.push(node5);
        stack.list();
        System.out.println("出栈~");
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        stack.list();

    }
}

class LinkedListStack {
    Node head = new Node(0);

    public void push(Node node) {
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
        node.pre = temp;
    }

    public int pop() {
        Node temp = head;
        if (temp.next == null) {
            System.out.println("栈空，没有数据~");
        }
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        int value = temp.data;
        temp.pre.next = temp.next;
        return value;
    }

    public void list() {
        if (head.next == null) {
            System.out.println("栈空");
            return;
        }
        Node temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

class Node {
    public int data;
    public Node next;
    public Node pre;

    public Node(int data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node [data=" + data + "]";
    }
}

栈实现数学表达式的运算

思路：

• 通过一个index值（索引），来遍历表达式
• 如果发现是一个数字，就直接入数栈
• 如果发现扫描到的是一个符号，就分如下情况：
  • 如果当前符号栈为空，就直接入栈
  • 如果符号栈有操作符，就进行比较
    • 如果当前操作符优先级小于或等于栈中的操作符，就需要从数栈中pop出两个数，再从符号栈中pop出一个符号，进行运算，将得到的结果，入数栈。然后将当前操作符入符号栈
    • 如果当前操作符优先级大于栈中的操作符，就直接入符号栈
• 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行
• 最后在数栈只有一个数字，就是表达式的结果

public class Calculator {
    public static void main(String[] args) {
        String expression = "3-2*6-2";
        // 定义两个栈，一个数栈，另一个符号栈
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);
        // 定义需要的相关变量
        int index = 0;// 用于扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' ';// 将每次扫描得到的char保存到ch
        String keepNum = "";// 用于拼接多位数
        // 开始while循环的扫描expression
        while (true) {
            // 依次得到expression的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            // 判断ch是什么，然后作相应处理
            if (operStack.isOper(ch)) {
                if (!operStack.isEmpty()) {
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1, num2, oper);
                        // 把运算的结果入数栈
                        numStack.push(res);
                        // 然后将当前的操作符入符号栈
                        operStack.push(ch);
                    } else {
                        operStack.push(ch);
                    }
                } else {
                    // 如果为空直接入栈
                    operStack.push(ch);
                }
            } else {
                // 如果是数，直接入数栈
                // numStack.push(ch-48);
                // 当处理多位数时，不能发现一个数就入数栈，也可能是多位数
                // 在处理数时，需要向expression表达式的index后再看一位，如果是数，继续扫描，如果是符号才入栈
                // 需要定义一个变量，用于拼接

                // 处理多位数
                keepNum += ch;

                // 如果ch已经是expression的最后一位，就直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    // 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈

                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        // 如果后一位是运算符，则入栈
                        numStack.push(Integer.parseInt(keepNum));
                        // keepNum要清空
                        keepNum = "";
                    }
                }
            }
            // 让index+1，并判断是否扫描到expression最后
            index++;
            if (index >= expression.length()) {
                break;
            }
        }

        while (true) {
            // 如果符号栈为空，则计算到最后的结果，数栈中只有一个数字
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            numStack.push(res);
        }
        System.out.printf("表达式%s=%d", expression, numStack.pop());
    }
}

class ArrayStack2 {
    private int maxSize;
    private int top;
    private int[] stack;

    public ArrayStack2(int maxSize) {
        top = -1;
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    // 增加一个方法，可以返回当前栈顶的值，但不是pop
    public int peek() {
        return stack[top];
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public void push(int value) {
        if (isFull()) {
            System.out.println("栈满，不能添加数据~");
            return;
        }
        top++;
        stack[top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空,没有数据~");
        }
        int value = stack[top];
        top--;
        return value;
    }

    public void list() {
        if (isEmpty()) {
            System.out.println("栈空，没有数据~");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }

    // 返回运算符优先级,优先级使用数字表示，数字越大，优先级越高
    public int priority(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1;// 假定目前的表达式只有+,-,*,/
        }
    }

    public boolean isOper(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    // 计算方法
    public int cal(int num1, int num2, int oper) {
        int res = 0;// 用于存放计算结果
        switch (oper) {
        case '+':
            res = num2 + num1;
            break;
        case '-':
            res = num2 - num1;
            break;
        case '*':
            res = num2 * num1;
            break;
        case '/':
            res = num2 / num1;
            break;

        default:
            break;
        }
        return res;
    }
}

前缀表达式（波兰表达式）

• 前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
• 举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

前缀表达式的计算机求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤*如下*