Data Structure Stack

algorithm

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

前言

    栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。栈是只能在某一端插入和删除的特殊线性表。

栈

栈的应用场景:

1)子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中；

2)处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中；

3)表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)；

4)二叉树的遍历；

5)图形的深度优先一搜索法。

栈图解：


实现 栈的 思路分析：

  1. 使用数组来模拟栈；

  2. 定义一个 top 来表示栈顶，初始化 为 -1；

  3. 入栈的操作，当有数据加入到栈时， top++; stack[top] = data;

  4. 出栈的操作， int value = stack[top]; top–, return value。

数组，链表模拟栈代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
import java.util.Scanner;
import java.util.Stack;

/**
 * @Auther: Arsenal
 * @Date: 2020-03-11 20:33
 * @Description: 栈
 */
public class StackDemo {
    public static void main(String[] args) {
        //ArrayStack arrayStack = new ArrayStack(4);
        LinkedListStack arrayStack = new LinkedListStack();
        boolean loop = true;
        String key;
        Scanner scanner = new Scanner(System.in);
        while (loop) {
            System.out.println("输入push为入栈");
            System.out.println("输入pop为出栈");
            System.out.println("输入list为查看");
            System.out.println("输入exit为退出");
            key = scanner.next();
            switch (key) {
                case "push":
                    int value = scanner.nextInt();
                    arrayStack.push(value);
                    break;
                case "pop":
                    try {
                        arrayStack.pop();
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case "list":
                    arrayStack.list();
                    break;
                default:
                    loop = false;
                    break;
            }
        }
        System.out.println("程序运行结束");
    }

}

/**
 * 用数组模拟栈
 */
class ArrayStack {

    private int top = -1; //栈顶，默认为-1
    private int size; //栈的大小
    private int[] stack; //栈

    /**
     * 构造方法初始化栈
     * @param size
     */
    public ArrayStack(int size) {
        if (size < 1) {
            System.out.println("数据有误");
            return;
        }
        this.size = size;
        stack = new int[this.size];
    }

    /**
     * 判断栈是否已满
     * @return
     */
    public boolean isFull() {
        return top == size - 1;
    }

    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 入栈
     * @param value 栈值
     */
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈已满");
            return;
        }
        stack[++top] = value;
    }

    /**
     * 出栈
     * @return
     */
    public int pop() {
        if (isEmpty()) {
            System.out.println("栈已空");
            throw new RuntimeException("栈已空");
        }
        return stack[top--];
    }

    /**
     * 查询栈情况
     */
    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]);
        }
    }

}

/**
 * 链表模拟栈
 */
class LinkedListStack {

    Node head = new Node(-1);

    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty() {
        return head.next == null;
    }

    /**
     * 入栈
     * @param no 栈值
     */
    public void push(int no) {
        Node cur = head;
        while (true) {
            //找到最后一个节点
            if (cur.next == null) {
                break;
            }
            cur = cur.next;
        }
        Node node = new Node(no);
        cur.next = node;
    }

    /**
     * 出栈
     * @return 节点
     */
    public Node pop() {
        if (isEmpty()) {
            System.out.println("栈已空");
            throw new RuntimeException("栈已空");
        }
        Node cur = head;
        while (true) {
            //找到倒数第二个节点
            if (cur.next.next == null) {
                break;
            }
            cur = cur.next;
        }
        Node temp = cur.next;
        //删除
        cur.next = null;
        return temp;
    }

    /**
     * 遍历栈
     */
    public void list() {
        if (isEmpty()) {
            System.out.println("栈已空");
            return;
        }

        Stack<Integer> stack = new Stack<>();
        Node cur = head;
        int i = -1;
        while (true) {
            stack.push(cur.no);
            //System.out.println("stack[" + i + "]=" + cur.no);
            if (cur.next == null) {
                break;
            }
            i++;
            cur = cur.next;
        }

        for (int j = i; j >= 0; j--) {
            System.out.println("stack[" + j + "]=" + stack.pop());
        }
    }
}

/**
 * 节点
 */
class Node {
    public int no; //栈值
    public Node next; //下个节点

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

}

栈实现综合计算器

思路：

  1. 通过一个 index 值（索引），来遍历我们的表达式；
  2. 如果我们发现是一个数字, 就直接入数栈；
  3. 如果发现扫描到是一个符号, 就分如下情况；
  4. 1 如果发现当前的符号栈为 空，就直接入栈；
  5. 2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈， 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈；
  6. 当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行；
  7. 最后在数栈只有一个数字，就是表达式的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
/**
 * @Auther: Arsenal
 * @Date: 2020-03-11 22:13
 * @Description: 用栈实现计算器
 * 思路：
 * 1. 通过一个 index  值（索引），来遍历我们的表达式
 * 2. 如果我们发现是一个数字, 就直接入数栈
 * 3. 如果发现扫描到是一个符号,  就分如下情况
 * 3.1 如果发现当前的符号栈为 空，就直接入栈
 * 3.2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符，
 * 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，
 * 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
 * 4. 当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
 * 5. 最后在数栈只有一个数字，就是表达式的结果
 */
public class Calculator {
    public static void main(String[] args) {
        //需要处理的表达式
        String expression = "7*2*2-5+1-5+3-4"; // 15//如何处理多位数的问题？
        ArrayCalculatorStack numberStack = new ArrayCalculatorStack(10); //存放数值
        ArrayCalculatorStack operatorStack = new ArrayCalculatorStack(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 (operatorStack.isOperator(ch)) {//如果是运算符
                //判断当前的符号栈是否为空
                if (!operatorStack.isEmpty()) { //如果不是空
                    //如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
                    //在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
                    if (operatorStack.priority(ch) <= operatorStack.priority(operatorStack.peek())) {
                        num1 = numberStack.pop();
                        num2 = numberStack.pop();
                        oper = operatorStack.pop();
                        //把运算的结果如数栈
                        res = operatorStack.calculate(num1, num2, oper);
                        numberStack.push(res);
                        //然后将当前的操作符入符号栈
                        operatorStack.push(ch);
                    } else {
                        //当前操作符优先级大，则直接入操作符栈
                        operatorStack.push(ch);
                    }
                } else {
                    //如果为空直接入符号栈..
                    operatorStack.push(ch);
                }

            } else { //如果是数值，则如数值栈
                //numStack.push(ch - 48); //? "1+3" '1' => 1
                //分析思路
                //1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
                //2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
                //3. 因此我们需要定义一个变量 字符串，用于拼接

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

                //如果ch已经是expression的最后一位，就直接入栈
                if (index == expression.length() - 1) {
                    numberStack.push(Integer.parseInt(keepNum));
                } else {

                    //判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
                    //注意是看后一位，不是index++
                    if (operatorStack.isOperator(expression.substring(index + 1, index + 2).charAt(0))) {
                        //如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
                        numberStack.push(Integer.parseInt(keepNum));
                        //重要的!!!!!!, keepNum清空
                        keepNum = "";

                    }
                }
            }
            //让index + 1, 并判断是否扫描到expression最后.
            index++;
            if (index >= expression.length()) {
                break;
            }
        }

        //当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
        while (true) {
            //如果符号栈为空，则计算到最后的结果, 数栈中只有一个数字【结果】
            if (operatorStack.isEmpty()) {
                break;
            }
            num1 = numberStack.pop();
            num2 = numberStack.pop();
            oper = operatorStack.pop();
            res = numberStack.calculate(num1, num2, oper);
            numberStack.push(res);//入栈
        }
        //将数栈的最后数，pop出，就是结果
        int res2 = numberStack.pop();
        System.out.printf("表达式 %s = %d", expression, res2);

    }
}


class ArrayCalculatorStack {
    private int maxSize; // 栈的大小
    private int[] stack; // 数组，数组模拟栈，数据就放在该数组
    private int top = -1;// top表示栈顶，初始化为-1

    /**
     * 构造方法初始化栈
     * @param maxSize 栈的大小
     */
    public ArrayCalculatorStack(int maxSize) {
        if (maxSize <= 0) {
            System.out.println("栈的大小设置有误！");
            return;
        }
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    /**
     * 判断栈是否已满
     * @return
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 入栈
     * @param value 栈值
     */
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈已满");
            return;
        }
        stack[++top] = value;
    }

    /**
     * 出栈
     * @return 出栈值
     */
    public int pop() {
        if (isEmpty()) {
            System.out.println("栈已空");
            throw new RuntimeException("栈已空");
        }
        return stack[top--];
    }

    /**
     * 查询栈情况
     */
    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]);
        }
    }

    /**
     * 查看栈顶值
     * @return 栈顶值
     */
    public int peek() {
        if (isEmpty()) {
            System.out.println("栈已空");
            throw new RuntimeException("栈已空");
        }
        return stack[top];
    }

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

    /**
     * 判断是否是操作符
     * @param val
     * @return
     */
    public boolean isOperator(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    /**
     * 计算方法
     * @param num1     数字
     * @param num2     数字
     * @param operator 操作符
     * @return 计算结果
     */
    public int calculate(int num1, int num2, int operator) {
        int res = 0; // res 用于存放计算的结果
        switch (operator) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;// 注意顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }
}

前缀、中缀、后缀表达式

前缀表达式(波兰表达式)

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

前缀表达式的计算机求值：

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

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

1)从右至左扫描，将6、5、4、3压入堆栈;
2)遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈;
3)接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈;
4)最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

中缀表达式

1)中缀表达式就是常见的运算表达式，如(3+4)×5-6;
2)中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式。

后缀表达式(逆波兰表达式)

1)后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后;
2)中举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –。

大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将 中缀表达式转成后缀表达式。

具体步骤如下:
1)初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2)从左至右扫描中缀表达式；
3)遇到操作数时，将其压s2；
4)遇到运算符时，比较其与s1栈顶运算符的优先级：
  (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
  (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；
  (3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较。

5)遇到括号时：
  (1) 如果是左括号“(”，则直接压入s1;
  (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃。
6)重复步骤2至5，直到表达式的最右边;
7)将s1中剩余的运算符依次弹出并压入s2;
8)依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。

递归-迷宫问题

递归的概念：
简单的说: 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

递归应用场景：

1)各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛);
2)各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等;
3)将用栈解决的问题–>第归代码比较简洁。

递归需要遵守的重要规则

1)执行一个方法时，就创建一个新的受保护的独立空间(栈空间)；
2)方法的局部变量是独立的，不会相互影响, 比如n变量；
3)如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据；
4)递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了；
5)当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

迷宫问题：


代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * @Auther: Arsenal
 * @Date: 2020-03-15 9:12
 * @Description: 用递归解决迷宫问题
 */
public class Maze {
    public static void main(String[] args) {

        //设置地图
        int[][] map = new int[8][7];

        //规定:0-没走过;1-表示墙;2-走过路径;3-走不通;
        //设置墙
        for (int i = 0; i < map.length; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        for (int i = 0; i < map[1].length; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }

        map[3][1] = 1;
        map[3][2] = 1;

        System.out.println("====初始化地图====");
        showMap(map);
        //从map[1][1] 开始走
        setWay(1, 1, map);
        System.out.println("====迷宫出口路线====");
        showMap(map);
    }

    /**
     * 找路策略是:下右上左
     * @param i   起点
     * @param j   起点
     * @param map 地图
     * @return 递归，走得通返回true,否则返回false
     */
    public static boolean setWay(int i, int j, int[][] map) {

        //map[6][5] 为出口
        if (map[6][5] == 2) {
            return true;
        } else {
            //假设这个点是走的通的
            if (map[i][j] == 0) {
                map[i][j] = 2;
                if (setWay(i + 1, j, map)) { //向下走
                    return true;
                } else if (setWay(i, j + 1, map)) { //向右走
                    return true;
                } else if (setWay(i - 1, j, map)) { //向上走
                    return true;
                } else if (setWay(i, j - 1, map)) { //向左走
                    return true;
                } else {
                    //走不通，设置该点为3
                    map[i][j] = 3;
                    return false;
                }
            } else {
                //如果map(i)(j)!=0
                //则值 1,2,3
                return false;
            }
        }
    }

    /**
     * 显示地图
     * @param map 地图
     */
    public static void showMap(int[][] map) {
        if (map == null) {
            System.out.println("地图未初始化");
            return;
        }

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "  ");
            }
            System.out.println();
        }
    }
}

迷宫最短路径问题

四种策略下，路径最短问题：
统计各种策略下所走的步数，比较输出即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
import java.util.HashMap;
import java.util.Map;

/**
 * @Auther: Arsenal
 * @Date: 2020-03-15 11:15
 * @Description: 最短路径迷宫问题
 */
public class OptimalPathMaze {
    public static void main(String[] args) {
        Map<String, Object> result = new HashMap<>();
        int[][] map = initialMap();
        System.out.println("初始化地图");
        showMap(map);

        //策略是:下右上左
        System.out.println("策略是->下右上左");
        setWay1(1, 1, map);
        showMap(map);
        int pathStep = getPathStep(map);
        result.put("策略:下右上左; 步数为:", pathStep);

        //策略是:上右下左
        System.out.println("策略是->上右下左");
        map = initialMap();
        setWay2(1, 1, map);
        showMap(map);
        pathStep = getPathStep(map);
        result.put("策略:上右下左; 步数为:", pathStep);

        //策略是:右下左上
        System.out.println("策略是->右下左上");
        map = initialMap();
        setWay3(1, 1, map);
        showMap(map);
        pathStep = getPathStep(map);
        result.put("策略:右下左上; 步数为:", pathStep);

        //策略是:左上右下
        System.out.println("策略是->左上右下");
        map = initialMap();
        setWay4(1, 1, map);
        showMap(map);
        pathStep = getPathStep(map);
        result.put("策略:左上右下; 步数为:", pathStep);


        System.out.println(result);
    }

    /**
     * 找路策略是:左上右下
     * @param i   起点
     * @param j   起点
     * @param map 地图
     * @return 递归，走得通返回true,否则返回false
     */
    public static boolean setWay4(int i, int j, int[][] map) {

        //map[6][5] 为出口
        if (map[6][5] == 2) {
            return true;
        } else {
            //假设这个点是走的通的
            if (map[i][j] == 0) {
                map[i][j] = 2;
                if (setWay4(i, j - 1, map)) { //向左走
                    return true;
                } else if (setWay4(i + 1, j, map)) { //向上走
                    return true;
                } else if (setWay4(i, j + 1, map)) { //向右走
                    return true;
                } else if (setWay4(i + 1, j, map)) { //向下走
                    return true;
                } else {
                    //走不通，设置该点为3
                    map[i][j] = 3;
                    return false;
                }
            } else {
                //如果map(i)(j)!=0
                //则值 1,2,3
                return false;
            }
        }
    }


    /**
     * 找路策略是:右下左上
     * @param i   起点
     * @param j   起点
     * @param map 地图
     * @return 递归，走得通返回true,否则返回false
     */
    public static boolean setWay3(int i, int j, int[][] map) {

        //map[6][5] 为出口
        if (map[6][5] == 2) {
            return true;
        } else {
            //假设这个点是走的通的
            if (map[i][j] == 0) {
                map[i][j] = 2;
                if (setWay3(i, j + 1, map)) { //向右走
                    return true;
                } else if (setWay3(i + 1, j, map)) { //向下走
                    return true;
                } else if (setWay3(i, j - 1, map)) { //向左走
                    return true;
                } else if (setWay3(i - 1, j, map)) { //向上走
                    return true;
                } else {
                    //走不通，设置该点为3
                    map[i][j] = 3;
                    return false;
                }
            } else {
                //如果map(i)(j)!=0
                //则值 1,2,3
                return false;
            }
        }
    }

    /**
     * 找路策略是:上右下左
     * @param i   起点
     * @param j   起点
     * @param map 地图
     * @return 递归，走得通返回true,否则返回false
     */
    public static boolean setWay2(int i, int j, int[][] map) {

        //map[6][5] 为出口
        if (map[6][5] == 2) {
            return true;
        } else {
            //假设这个点是走的通的
            if (map[i][j] == 0) {
                map[i][j] = 2;
                if (setWay2(i - 1, j, map)) { //向上走
                    return true;
                } else if (setWay2(i, j + 1, map)) { //向右走
                    return true;
                } else if (setWay2(i + 1, j, map)) { //向下走
                    return true;
                } else if (setWay2(i, j - 1, map)) { //向左走
                    return true;
                } else {
                    //走不通，设置该点为3
                    map[i][j] = 3;
                    return false;
                }
            } else {
                //如果map(i)(j)!=0
                //则值 1,2,3
                return false;
            }
        }
    }

    /**
     * 找路策略是:下右上左
     * @param i   起点
     * @param j   起点
     * @param map 地图
     * @return 递归，走得通返回true,否则返回false
     */
    public static boolean setWay1(int i, int j, int[][] map) {

        //map[6][5] 为出口
        if (map[6][5] == 2) {
            return true;
        } else {
            //假设这个点是走的通的
            if (map[i][j] == 0) {
                map[i][j] = 2;
                if (setWay1(i + 1, j, map)) { //向下走
                    return true;
                } else if (setWay1(i, j + 1, map)) { //向右走
                    return true;
                } else if (setWay1(i - 1, j, map)) { //向上走
                    return true;
                } else if (setWay1(i, j - 1, map)) { //向左走
                    return true;
                } else {
                    //走不通，设置该点为3
                    map[i][j] = 3;
                    return false;
                }
            } else {
                //如果map(i)(j)!=0
                //则值 1,2,3
                return false;
            }
        }
    }


    /**
     * 初始化地图
     * @return 地图
     */
    public static int[][] initialMap() {
        //设置地图
        int[][] map = new int[8][7];

        //规定:0-没走过;1-表示墙;2-走过路径;3-走不通;
        //设置墙
        for (int i = 0; i < map.length; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        for (int i = 0; i < map[1].length; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }

        map[3][1] = 1;
        map[3][2] = 1;
        return map;
    }

    /**
     * 显示地图
     * @param map 地图
     */
    public static void showMap(int[][] map) {
        if (map == null) {
            System.out.println("地图未初始化");
            return;
        }

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "  ");
            }
            System.out.println();
        }
    }


    /**
     * 获取走过路径的步数
     * @param map
     * @return
     */
    public static int getPathStep(int[][] map) {
        int step = 0;
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 2) {
                    step++;
                }
            }
        }
        return step;
    }

}

递归-八皇后问题(回溯算法)

八皇后问题算法思路分析：

1)第一个皇后先放第一行第一列;
2)第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适;
3)继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解;
4)当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到;
5)然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤 。

说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class Queue8 {

	//定义一个max表示共有多少个皇后
	int max = 8;
	//定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3} 
	int[] array = new int[max];
	static int count = 0;
	static int judgeCount = 0;
	public static void main(String[] args) {
		//测试一把 ， 8皇后是否正确
		Queue8 queue8 = new Queue8();
		queue8.check(0);
		System.out.printf("一共有%d解法", count);
		System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w
		
	}
	
	
	
	//编写一个方法，放置第n个皇后
	//特别注意： check 是 每一次递归时，进入到check中都有  for(int i = 0; i < max; i++)，因此会有回溯
	private void check(int n) {
		if(n == max) {  //n = 8 , 其实8个皇后就既然放好
			print();
			return;
		}
		
		//依次放入皇后，并判断是否冲突
		for(int i = 0; i < max; i++) {
			//先把当前这个皇后 n , 放到该行的第1列
			array[n] = i;
			//判断当放置第n个皇后到i列时，是否冲突
			if(judge(n)) { // 不冲突
				//接着放n+1个皇后,即开始递归
				check(n+1); //  
			}
			//如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行得 后移的一个位置
		}
	}
	
	//查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
	/**
	 * 
	 * @param n 表示第n个皇后
	 * @return
	 */
	private boolean judge(int n) {
		judgeCount++;
		for(int i = 0; i < n; i++) {
			// 说明
			//1. array[i] == array[n]  表示判断 第n个皇后是否和前面的n-1个皇后在同一列
			//2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
			// n = 1  放置第 2列 1 n = 1 array[1] = 1
			// Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
			//3. 判断是否在同一行, 没有必要，n 每次都在递增
			if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
				return false;
			}
		}
		return true;
	}
	
	//写一个方法，可以将皇后摆放的位置输出
	private void print() {
		count++;
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}

}

延伸

    栈的作用
    数据结构— 栈
    韩顺平数据结构和算法
    Data Structure and Algorithms - Stack

Article Title:Data Structure Stack

Article Author:Funing Ma

Release Time:2020-03-11 18:18:18

Last Update:2020-03-30 09:58:51

Original Link:https://mafuning.github.io/2020/03/11/2020-03-11-Data-Structure-Stack/

License Agreement: "CC-BY-SA-4.0"

Content
  1. 1. 前言
  2. 2. 栈
  3. 3. 栈实现综合计算器
  4. 4. 前缀、中缀、后缀表达式
    1. 4.1. 前缀表达式(波兰表达式)
    2. 4.2. 中缀表达式
    3. 4.3. 后缀表达式(逆波兰表达式)
  5. 5. 递归-迷宫问题
  6. 6. 迷宫最短路径问题
  7. 7. 递归-八皇后问题(回溯算法)
  8. 8. 延伸