栈

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

出栈(pop)和入栈(push)的概念

栈的应用

• 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
• 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
• 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
• 二叉树的遍历。
• 图形的深度优先(depth一first)搜索法。

利用数组来模拟栈

package stack;

import javax.sql.rowset.JoinRowSet;

public class ArrayStack {
    public static void main(String[] args) {

    }

}
class ArrayStackDemo01{
    private int maxSize;
    private int top;
    private int tail;
    private int[] stack;
    public ArrayStackDemo01(int max) {
        // TODO Auto-generated constructor stub
        stack =  new int[max];
        top = -1;
        tail = 0;
    }
    //判断栈空
    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++;
        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("栈空，无法遍历数据");
        }
        for(int i = top;i>=0;i--) {
            System.out.println(stack[top]);
        }
    }
}

栈的实际应用-利用栈来实现一个基于中缀表达式的计算器

package stack;

import javax.management.remote.SubjectDelegationPermission;

public class CaculatorDemo02 {
    //先创建一个栈
    public static void main(String[] args) {
        int num1;
        int num2;
        int index;
        int temp;
        String exci = "3+5*9*2";
        ArrayStackDemo02 oper = new ArrayStackDemo02(20);
        ArrayStackDemo02 number = new ArrayStackDemo02(20);
        for(int i = 0;i<exci.length();i++) {
            temp = exci.charAt(i);
            if(temp == '+' || temp == '-' || temp == '*'||temp == '/') {
                if( !oper.isEmpty()) {
                    int prio = oper.prio(temp);
                    if(prio<=oper.prio(oper.elmentHead())) {
                        num1 = number.pop();
                        num2 = number.pop();
                        int calculator = number.calculator(num1, num2, temp);
                        number.push(calculator);
                    }else {
                        oper.push(temp);
                    }
                }else {
                    oper.push(temp);
                }
            }else {
                number.push(temp-48);
            }
        }
        while(!oper.isEmpty()) {
            num1 = number.pop();
            num2 = number.pop();
            temp = oper.pop();
            int calculator = number.calculator(num1, num2, temp);
            number.push(calculator);
        }
        System.out.println(number.pop());
    }

}
class ArrayStackDemo02{
    private int maxSize;
    private int top;
    private int tail;
    private int[] stack;
    public ArrayStackDemo02(int max) {
        // TODO Auto-generated constructor stub
        this.maxSize = max;
        stack =  new int[maxSize];
        top = -1;
        tail = 0;
    }
    //判断栈空
    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++;
        stack[top] = value;
    }
    //出栈
    public int  pop() {
        if(isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }
    //查看头部元素
    public int elmentHead() {
        return stack[top];
    }
    //遍历栈
    public void list() {
        if(isEmpty()) {
            System.out.println("栈空，无法遍历数据");
        }
        for(int i = top;i>=0;i--) {
            System.out.println(stack[top]);
        }
    }
    //判断符号的优先级
    public int prio(int oper) {
        if(oper == '+'||oper == '-') {
            return 0;
        }else {
            return 1;
        }
    }
    //计算
    public int calculator(int num1,int num2,int oper) {
        if(oper == '+') {
            return num1+num2;
        }else if(oper == '-') {
            return num2-num1;
        }else if(oper == '*') {
            return num1*num2;
        }else {
            return num2/num1;
        }
    }
}