【数据结构】栈结构与应用

一、栈的概述

1、栈的介绍

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

2、栈的应用场景

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

3、栈的代码实现

1）数组实现

package work.rexhao.stack;

public class arrayStackdemo {
   

    public static void main(String[] args) {
   
        arrayStact as = new arrayStact(10);
        as.push(1);
        as.push(2);
        as.list();
        System.out.println(as.pop());
        System.out.println(as.pop());
        as.list();
    }

}

class arrayStact {
   
    int maxSize;
    int[] data;
    int top;

    /**
     * 栈的构造器
     * 
     * @param maxSize 栈的大小
     */
    arrayStact(int maxSize) {
   
        this.maxSize = maxSize;
        data = new int[maxSize];
        top = -1;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
   
        return top == -1;
    }

    /**
     * 判满
     */
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    /**
     * 弹出
     */
    public int pop() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return -1;
        }
        return data[top--];
    }

    /**
     * 压栈
     */
    public void push(int num) {
   
        if (isFull()) {
   
            System.out.println("栈满");
        } else {
   
            data[++top] = num;
        }
    }

    /**
     * 遍历
     */
    public void list() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return;
        }
        for (int i = 0; i <= top; i++) {
   
            System.out.printf("data[%d] = %d\n", i, data[i]);
        }
    }
}

2）链表实现

package work.rexhao.stack;

public class linkedListStackDemo {
   
    public static void main(String[] args) {
   
        linkedListStack lls = new linkedListStack();
        try {
   
            lls.pop();
        } catch (Exception e) {
   
            System.out.println(e.getMessage());
        }
        lls.push(1);
        lls.push(2);
        lls.pop();
        lls.push(3);
        lls.push(4);
        lls.show();
    }
}

class linkedListStack {
   
    private stackNode head = new stackNode(-1);

    /**
     * 压栈
     */
    public void push(int num) {
   
        if (head.next == null) {
   
            head.next = new stackNode(num);
            return;
        }
        stackNode temp = head.next;
        while (true) {
   
            if (temp.next == null) {
   
                temp.next = new stackNode(num);
                return;
            }
            temp = temp.next;
        }

    }

    /**
     * 出栈
     */
    public int pop() {
   
        if (isEmpty()) {
   
            throw new RuntimeException("栈空");
        }
        stackNode temp = head;
        while (true) {
   
            if (temp.next.next == null) {
   
                break;
            }
            temp = temp.next;
        }
        int ans = temp.next.getData();
        temp.next = null;
        return ans;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
   
        return head.next == null;
    }

    /**
     * 遍历
     */
    public void show() {
   
        if (isEmpty()) {
   
            return;
        }
        stackNode temp = head.next;
        while (true) {
   
            if (temp == null) {
   
                return;
            }
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }
}

class stackNode {
   
    private int data;
    public stackNode next;

    stackNode(int data) {
   
        this.data = data;
    }

    public int getData() {
   
        return data;
    }

    public void setData(int data) {
   
        this.data = data;
    }

    @Override
    public String toString() {
   
        return data + "";
    }
}

二、栈实现综合计算器

1、思路

1. 通过一个index 值（索引），来遍历我们的表达式
2. 扫描到一个数字，直接入数栈
3. 扫描到一个符号
   1. 符号栈为空，就直接入栈
   2. 有操作符，就进行比较
      1. 如果当前的操作符的优先级小于或者等于栈顶的操作符，就需要从数栈中pop出两个数，在从符号栈中pop出一个符号，进行运算，将得到结果入数栈，然后将当前的操作符入符号栈
      2. 如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
4. 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号
5. 最后在数栈只有一个数字，就是表达式的结果

2、代码实现

package work.rexhao.stack;

import java.util.Scanner;

/**
 * 个位数四则计算器
 *
 */
public class calculatorDemo {
   
    public static void main(String[] args) {
   
        System.out.println("请输入表达式");
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        sc.close();
        System.out.println("表达式值为:" + calculator.calculate(s));
    }

}

class calculator {
   

    /**
     * 计算
     * 
     * @param s 表达式
     * @return 结果
     */
    public static int calculate(String s) {
   
        /*
         * 初始化栈
         */
        numStact ns = new numStact(20); // 数栈
        signStact ss = new signStact(20); // 运算符栈

        /*
         * 扫描字符串
         */
        int slen = s.length();
        // int index = 0; // 扫描索引
        for (int i = 0; i < slen; i++) {
   
            char c = s.charAt(i);
            if (c == '*' || c == '/') {
   
                ss.push(c);
            } else if (c == '+' || c == '-') {
   
                while (true) {
   
                    // 栈空：入栈
                    if (ss.isEmpty()) {
   
                        break;
                    }
                    // 栈非空：比较
                    if (ss.top() == '+' || ss.top() == '-') {
   
                        // 同优先级
                        break;
                    } else {
   
                        // 大于优先级
                        // 1.取出两个数和运算符
                        int ans = count(ns.pop(), ns.pop(), ss.pop());
                        // 2.结果入栈
                        ns.push(ans);
                    }
                }
                ss.push(c);
            } else {
   
                ns.push(c - '0');
            }
        }
        while(ns.top != 0) {
   
            ns.push(count(ns.pop(), ns.pop(), ss.pop()));
        }
        return ns.pop();
    }

    /**
     * 辅助计算
     */
    private static int count(int a, int b, char c) {
   
        if (c == '+') {
   
            return a + b;
        } else if (c == '-') {
   
            return b - a;
        } else if (c == '*') {
   
            return a * b;
        } else if (c == '/') {
   
            return a / b;
        }
        throw new RuntimeException("NaN");
    }
}

/**
 * 数栈
 * 
 */
class numStact {
   
    int maxSize;
    int[] data;
    int top;

    /**
     * 栈的构造器
     * 
     * @param maxSize 栈的大小
     */
    numStact(int maxSize) {
   
        this.maxSize = maxSize;
        data = new int[maxSize];
        top = -1;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
   
        return top == -1;
    }

    /**
     * 判满
     */
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    /**
     * 弹出
     */
    public int pop() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return -1;
        }
        return data[top--];
    }

    /**
     * 压栈
     */
    public void push(int num) {
   
        if (isFull()) {
   
            System.out.println("栈满");
        } else {
   
            data[++top] = num;
        }
    }

    /**
     * 遍历
     */
    public void list() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return;
        }
        for (int i = 0; i <= top; i++) {
   
            System.out.printf("data[%d] = %d\n", i, data[i]);
        }
    }
}

/**
 * 符号栈
 *
 */
class signStact {
   
    int maxSize;
    char[] data;
    int top;

    /**
     * 栈的构造器
     * 
     * @param maxSize 栈的大小
     */
    signStact(int maxSize) {
   
        this.maxSize = maxSize;
        data = new char[maxSize];
        top = -1;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
   
        return top == -1;
    }

    /**
     * 判满
     */
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    /**
     * 弹出
     */
    public char pop() {
   
        if (isEmpty()) {
   
            throw new RuntimeException("栈空");
        }
        return data[top--];
    }

    /**
     * 压栈
     */
    public void push(char c) {
   
        if (isFull()) {
   
            System.out.println("栈满");
        } else {
   
            data[++top] = c;
        }
    }

    /**
     * 遍历
     */
    public void list() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return;
        }
        for (int i = 0; i <= top; i++) {
   
            System.out.printf("data[%d] = %s\n", i, data[i]);
        }
    }

    /**
     * 栈顶元素
     */
    public char top() {
   
        return data[top];
    }
}

三、逆波兰计算器

package work.rexhao.stack;

public class polandNotationDemo {
   

    public static void main(String[] args) {
   
        System.out.println(polandNotation.calculate("34+5*6-"));
    }

}

class polandNotation {
   
    public static int calculate(String s) {
   
        numStact ns = new numStact(20);
        // 不需要符号栈
        int slen = s.length();
        for (int i = 0; i < slen; i++) {
   
            char c = s.charAt(i);
            if (c == '*' || c == '/' || c == '+' || c == '-') {
   
                ns.push(count(ns.pop(), ns.pop(), c));
            } else {
   
                ns.push(c - '0');
            }
        }
        return ns.pop();
    }

    /**
     * 辅助计算
     */
    private static int count(int a, int b, char c) {
   
        if (c == '+') {
   
            return a + b;
        } else if (c == '-') {
   
            return b - a;
        } else if (c == '*') {
   
            return a * b;
        } else if (c == '/') {
   
            return a / b;
        }
        throw new RuntimeException("NaN");
    }
}

四、中缀转后缀

1、思路

后缀表达式适合计算式进行运算，但是却不太容易写出来，尤其是表达式很长的情况下

因此在开发中，我们常常需要将中缀表达式转成后缀表达式

1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2;
2. 从左至右扫描中缀表达式
3. 遇到操作数时，将其压s2
4. 遇到运算符时，比较其与 s1栈顶运算符的优先级
   1. 如果s1为空，或栈顶运算符为左括号(，压入s1
   2. 若该运算符优先级比栈顶运算符的高，压入s1
   3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到与与s1中新的栈顶运算符相比较
5. 遇到括号
   1. 如果是左括号(，则直接压入s1
   2. 如果是右括号)，则依次弹出s1的运算符压s2，直到遇到左括号为止，将这一对括号丢弃
6. 重复步骤直到表达式的最右边
7. 将s1中剩余的运算符依次弹出并压入s2
8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

2、代码实现

/**
 * 中缀转后缀
 * 
 * @param s 中缀表达式
 * @return 后缀表达式
 */
public static String toPoland(String s) {
   
    sStact s1 = new sStact(20);// 运算符栈
    sStact s2 = new sStact(20);// 中间结果栈
    int slen = s.length();
    for (int i = 0; i < slen; i++) {
   
        char c = s.charAt(i);
        if (s1.isEmpty() || c == '(') {
   
            s1.push(c);
        } else if (c == ')') {
   
            while (true) {
   
                char temp = s1.pop();
                if (temp == '(') {
   
                    break;
                }
                s2.push(temp);
            }
        } else if (c == '+' || c == '-') {
   
            while (true) {
   
                if (s1.isEmpty() || s1.top() == '(') {
   
                    s1.push(c);
                    break;
                }
                s2.push(s1.pop());
            }
        } else if (c == '*' || c == '/') {
   
            while (true) {
   
                if (s1.isEmpty() || s1.top() == '+' || s1.top() == '-' || s1.top() == '(') {
   
                    s1.push(c);
                    break;
                }
                s2.push(s1.pop());
            }
        } else {
   
            // 数字
            s2.push(c);
        }
    }
    while (!s1.isEmpty()) {
   
        s2.push(s1.pop());
    }
    StringBuilder sb = new StringBuilder();
    while (!s2.isEmpty()) {
   
        sb.append(s2.pop());
    }
    return sb.reverse().toString();
}