YuanbaoQiang
0%

Posted on In Valine:
Symbols count in article: 7.8k Reading time ≈ 7 mins.

入栈和出栈参考

二叉树前序-中序-后序遍历（递归、栈结构）

以下代码均可直接运行：

其中单链表的两种方法，主要在于pop()和push()的方式不太一样，其余都大同小异。同样也可以用双链表实现，和单链表也没差差别，定义Node的时候多加一个Node pre属性即可；

数组实现

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
public class ArrayStackDemo {

    public static void main(String[] args) {
        // 测试一个ArrayStack是否正确
        // 先测试ArrayStack对象-->表示栈
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean loop = true; // 控制是否退出菜单
        Scanner scanner = new Scanner(System.in);


        while (loop) {
            System.out.println("show: 表示显示栈");
            System.out.println("exit: 退出程序");
            System.out.println("push: 表示添加数据到栈（入栈）");
            System.out.println("pop: 表示从栈取出数据（出栈）");
            System.out.print("请输入你的选择：");
            key = scanner.next();
            switch (key) {
                case "show":
                    stack.list();
                    break;
                case "push":
                    System.out.print("请输入一个数：");
                    int value = scanner.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":
                    scanner.close();
                    loop = false;
                    break;
            }
        }
        System.out.println("程序退出！");

    }
}

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

    // 构造器
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.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]);
        }
    }


}

单链表（头插法）实现

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
public class SingleLinkedListHeadInsertDemo {
    public static void main(String[] args) {
        SingleLinkedList sll = new SingleLinkedList(5);
        Node dum = sll.dum;
        boolean flag = true;

        String key = "";
        Scanner scanner = new Scanner(System.in);

        while(flag){
            System.out.println("show: 显示链表");
            System.out.println("push: 加入节点");
            System.out.println("pop: 弹出链表节点");
            System.out.println("exit: 退出循环");
            System.out.print("请输入你的选项: ");
            key = scanner.next();
            switch (key){
                case "show":
                    sll.list();
                    break;
                case "push":
                    System.out.print("请输入一个节点值: ");
                    int value = scanner.nextInt();
                    Node node = new Node(value);
                    sll.push(node);
                    break;
                case "pop":
                    sll.pop(dum);
                    break;
                case "exit":
                    flag = false;
                    break;
            }
        }
        System.out.println("程序已结束~");
    }

}

class SingleLinkedList{
    int maxSize; // 最大节点数量

    /*
     * @description: 单链表构造器
     * @author: YuanbaoQiang
     * @date: 2020/8/25 11:59
     * @param maxSize 定义该链表的最大节点数（不包含伪头）
     * @return:
     */
    public SingleLinkedList(int maxSize){
        this.maxSize = maxSize;
    }

    // 创建伪头，val为0
    Node dum = new Node(0);


    /*
     * @description: 头插入节点
     * @author: YuanbaoQiang
     * @date: 2020/8/25 12:31
     * @param node
     * @return: void
     */
    public void push(Node node){
        if(isFull()){
            System.out.println("链表已满~");
            return;
        }

        // 节点始终插在dum后
        node.next = dum.next;
        dum.next = node;
    }

    /*
     * @description: pop出链表节点
     * @author: YuanbaoQiang
     * @date: 2020/8/25 12:05
     * @param node
     * @return: void
     */
    public void pop(Node node){
        if(isEmpty()){
            System.out.println("链表为空~");
        }
        if(dum.next != null){
            Node cur = dum.next;
            dum.next = cur.next;
            System.out.printf("弹出：节点 %d \n",cur.val);
        }
    }


    /*
     * @description: 判断链表是否已满
     * @author: YuanbaoQiang
     * @date: 2020/8/25 11:46
     * @param
     * @return: boolean
     */
    public boolean isFull(){
        return size(dum) == maxSize;

    }

    /*
     * @description: 判断链表是否为空
     * @author: YuanbaoQiang
     * @date: 2020/8/25 11:47
     * @param
     * @return: boolean
     */
    public boolean isEmpty(){
        return size(dum) == 0;
    }

    /*
     * @description: 遍历链表
     * @author: YuanbaoQiang
     * @date: 2020/8/25 10:38
     * @param
     * @return: void
     */
    public void list(){
        if(isEmpty()){
            System.out.println("此时链表为空~");
        }
        Node cur = dum.next;
        while(true){
            if(cur == null){
                break;
            }
            System.out.printf("节点 %d\n",cur.val);
            cur = cur.next;
        }
    }

    /*
     * @description: 计算链表长度（不包含伪头）
     * @author: YuanbaoQiang
     * @date: 2020/8/25 10:53
     * @param node
     * @return: int
     */
    public int size(Node node){
        int count = 0;
        Node cur = dum.next;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

}


class Node{

    Node next;
    int val;


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

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}

单链表（普通末尾添加顺序）实现

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
public class SingleLinkedListStackDemo {
    public static void main(String[] args) {
        SingleLinkedList sll = new SingleLinkedList(5);
        Node dum = sll.dum;
        boolean flag = true;

        String key = "";
        Scanner scanner = new Scanner(System.in);

        while(flag){
            System.out.println("show: 显示链表");
            System.out.println("push: 加入节点");
            System.out.println("pop: 弹出链表节点");
            System.out.println("exit: 退出循环");
            System.out.print("请输入你的选项: ");
            key = scanner.next();
            switch (key){
                case "show":
                    sll.list();
                    break;
                case "push":
                    System.out.print("请输入一个节点值: ");
                    int value = scanner.nextInt();
                    Node node = new Node(value);
                    sll.push(node);
                    break;
                case "pop":
                    sll.pop(dum);
                    break;
                case "exit":
                    flag = false;
                    break;
            }
        }
        System.out.println("程序已结束~");
    }
}



class SingleLinkedList{
    int maxSize; // 最大节点数量

    /*
     * @description: 单链表构造器
     * @author: YuanbaoQiang
     * @date: 2020/8/25 11:59
     * @param maxSize 定义该链表的最大节点数（不包含伪头）
     * @return:
     */
    public SingleLinkedList(int maxSize){
        this.maxSize = maxSize;
    }

    // 创建伪头，val为0
    Node dum = new Node(0);

    /*
     * @description: 添加节点
     * @author: YuanbaoQiang
     * @date: 2020/8/25 10:33
     * @param node
     * @return: void
     */
    public void push(Node node){
        if(isFull()){
            System.out.println("链表已满~");
            return;
        }
        Node cur = dum;
        while(true){
            if(cur.next == null){
                break;
            }
            cur = cur.next;
        }
        cur.next = node;
    }



    /*
     * @description: pop出链表节点
     * @author: YuanbaoQiang
     * @date: 2020/8/25 12:05
     * @param node
     * @return: void
     */
    public void pop(Node node){
        if(isEmpty()){
            System.out.println("链表为空~");
        }
        Node cur = dum;
        for(int i = 0; i < size(dum) - 1; i++){
            cur = cur.next;
        }
        if(cur.next != null){
            Node temp = cur.next; // 记录pop出的节点
            cur.next = null; // 倒数第二个节点指向null
            System.out.printf("弹出：节点 %d \n",temp.val);
        }
    }



    /*
     * @description: 判断链表是否已满
     * @author: YuanbaoQiang
     * @date: 2020/8/25 11:46
     * @param
     * @return: boolean
     */
    public boolean isFull(){
        return size(dum) == maxSize;

    }

    /*
     * @description: 判断链表是否为空
     * @author: YuanbaoQiang
     * @date: 2020/8/25 11:47
     * @param
     * @return: boolean
     */
    public boolean isEmpty(){
        return size(dum) == 0;
    }

    /*
     * @description: 遍历链表
     * @author: YuanbaoQiang
     * @date: 2020/8/25 10:38
     * @param
     * @return: void
     */
    public void list(){
        if(isEmpty()){
            System.out.println("此时链表为空~");
        }
        Node cur = dum.next;
        while(true){
            if(cur == null){
                break;
            }
            System.out.printf("节点 %d\n",cur.val);
            cur = cur.next;
        }
    }

    /*
     * @description: 计算链表长度（不包含伪头）
     * @author: YuanbaoQiang
     * @date: 2020/8/25 10:53
     * @param node
     * @return: int
     */
    public int size(Node node){
        int count = 0;
        Node cur = dum.next;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

}


class Node{

    Node next;
    int val;


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

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}

Posted on In Valine:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

单向链表解法

迭代解法见：LeetCode-Josephu问题（圆圈中最后剩下的数字）

约瑟夫用单链表解决比较简单，只需要定义两个指针即可，处理方法见deal()方法。除此之外详细的节点定义及构建已给出。

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
public class Josephu2 {
    public static void main(String[] args) {
        SLL sll = new SLL(8); // 8个人
        sll.construct();
        int deal = sll.deal(3); // 每次报3下
        System.out.println(deal); // 6
    }
}


class SLL {
    int n; // 最大节点数量

    // 创建头节点，val为0
    Node first = new Node(0);


    /*
     * @description: 创建长度为n的环形链表
     * @author: YuanbaoQiang
     * @date: 2020/8/25 20:41
     * @param n 节点数量
     * @return:
     */
    public SLL(int n) {
        this.n = n;
    }


    /*
     * @description: 构建单向环形链
     * @author: YuanbaoQiang
     * @date: 2020/8/25 20:56
     * @param
     * @return: void
     */
    public void construct(){
        Node cur = first;
        for(int i = 1; i <= n; i++){
            Node node = new Node(i);
            add(node);
            cur = node;
        }
        cur.next = first;
    }


    /*
     * @description: 添加节点
     * @author: YuanbaoQiang
     * @date: 2020/8/25 10:33
     * @param node
     * @return: void
     */
    public void add(Node node){
        Node cur = first;
        while(true){
            if(cur.next == null){
                break;
            }
            cur = cur.next;
        }
        cur.next = node;
    }



    /*
     * @description: 遍历数组
     * @author: YuanbaoQiang
     * @date: 2020/8/25 20:37
     * @param
     * @return: void
     */
    public void list(){
        Node cur = first;
        while(true){
            if(cur.next == first){
                break;
            }
            System.out.printf("节点 %d\n",cur.val);
            cur = cur.next;
        }
    }


    /*
     * @description: 处理约瑟夫问题
     * @author: YuanbaoQiang
     * @date: 2020/8/25 21:03
     * @param
     * @return: void
     */
    public int deal(int m){
        // 定义两个指针 helper 和 cur
        Node cur = first;
        Node helper = cur;

        // helper 定位在 cur的前一个位置
        for(int i = 0; i < n - 1; i++){
            helper = helper.next;
        }


        while(true){
            if(helper == cur){
                break;
            }

            // cur 和 helper同时后移 m-1次
            // cur到达目标位置
            for(int i = 0; i < m - 1; i++){
                helper = helper.next;
                cur = cur.next;
            }

            helper.next = cur.next;
            cur = cur.next;
        }
        return cur.val;
    }
    
}


// 定义节点
class Node{

    Node next;
    int val;


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

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}