栈的递归操作

本文最后更新于：8 个月前

The problem

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
// App.java
import java.util.Random;
import java.util.Stack;

public class App {
    public static void main(String[] args) {
        System.out.println("Hello Stack !");
        Stack<Integer> s = new Stack<Integer>();
        int threshold = 55;
        Random r = new Random(); // Create a new random number generator
        for (int i = 1; i <= 10; i++) {
            s.push(r.nextInt(100)); // 100 is the upper bound on the random number
        }
        System.out.println("threshold: " + threshold);
        System.out.println("stack: " + s.toString());

        int removeCount = removeAll(s, threshold);
        System.out.println("remove count: " + removeCount);
    }

    public static int removeAll(Stack<Integer> s, int threshold) {
        int topData = s.pop();

        if (s.isEmpty()) {
            if (topData > threshold) {
                return 1;
            } else {
                s.push(topData);
                return 0;
            }
        } else {
            int count = 0;
            if (topData > threshold) {
                return removeAll(s, threshold) + 1;
            } else {
                count += removeAll(s, threshold);
                s.push(topData);
                System.out.println(s.toString());
                return count;
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
xiang@iMac MINGW64 ~/Desktop/mid2
$ javac App.java

xiang@iMac MINGW64 ~/Desktop/mid2
$ java App
Hello Stack !
threshold: 55
stack: [67, 64, 33, 13, 74, 72, 22, 22, 18, 72]
[33]
[33, 13]
[33, 13, 22]
[33, 13, 22, 22]
[33, 13, 22, 22, 18]
remove count: 5