基本数据结构汇总

List

接口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public interface List<E> {
  
    int getSize();
    boolean isEmpty();

    void add(int index, E e);
    void addLast(E e);
    void addFirst(E e);

    E remove(int index);
    E removeLast();
    E removeFirst();
    void removeElement(E e);

    void set(int index, E e);

    E get(int index);
    E getLast();
    E getFirst();
    int indexOf(E e);
    boolean contains(E e);
}


ArrayList

动态数组包装类 MyArrayList

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
public final class MyArrayList<E> implements List<E> {
  
    private E[] data;
    private int size;

    public MyArrayList(int capacity) {
        this.data = (E[]) new Object[capacity];
        this.size = 0;
    }
    public MyArrayList() {
        this(16);
    }
    public MyArrayList(E[] array) {
        this.data = (E[]) new Object[array.length];
        for (int i = 0; i < array.length; i++)
            data[i] = array[i];
        this.size = array.length;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }

    @Override
    public int getSize() {
        return this.size;
    }
  
    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    public void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size)
            throw new IllegalArgumentException("Index is illegal.");
        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    /**
     * 添加 O(n)
     */
    @Override
    public void add(int index, E e) {
        if (index < 0 || index > size)
            throw new IllegalStateException("add failed. Require index >= 0 and <= size.");
        if (size == data.length) {
            int newCapacity = data.length == 0 ? 1 : 2 * data.length;
            resize(newCapacity);
        }
        // 每个元素向后挪一个位置
        for (int i = size; i > index; i--)
            data[i] = data[i-1];
        data[index] = e;
        size++;
    }

    /**
     * 尾部添加 O(1)
     */
    @Override
    public void addLast(E e) {
        add(size, e);
    }

    /**
     * 头部添加 O(n)
     */
    @Override
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 删除 O(n)
     */
    @Override
    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalStateException("remove failed. Index is illegal.");

        E result = data[index];
        for (int i = index+1; i < size; i++)
            data[i-1] = data[i];

        size--;
        data[size] = null; // 处理 loitering objects
        if (size == data.length/4 && data.length/2 >= 16) // 当元素个数是原来四分之一，且不是小数组，触发缩容
            resize(data.length/2); // 数组长度缩容为原来二分之一，防止复杂度的震荡

        return result;
    }

    /**
     * 删除尾元素 O(1)
     */
    @Override
    public E removeLast() {
        return remove(size-1);
    }

    /**
     * 删除头元素 O(n)
     */
    @Override
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 删除元素 O(n)
     */
    @Override
    public void removeElement(E e) {
        int index = indexOf(e);
        if (index != -1)
            remove(index);
    }

    /**
     * 修改 O(1)
     */
    @Override
    public void set(int index, E e) {
        if (index < 0 || index >= size)
            throw new IllegalStateException("set failed. Index is illegal.");
        data[index] = e;
    }

    /**
     * 根据索引查到对应元素 O(1)
     */
    @Override
    public E get(int index) {
        if (index < 0 || index >= size)
            throw new IllegalStateException("get failed. Index is illegal.");
        return data[index];
    }

    @Override
    public E getLast() {
        return get(size-1);
    }

    @Override
    public E getFirst() {
        return get(0);
    }

    /**
     * 根据元素查对应索引 O(n)
     */
    @Override
    public int indexOf(E e) {
        for (int i = 0; i < size; i++) {
            if (Objects.equals(data[i], e))
                return i;
        }
        return -1;
    }

    /**
     * 判断是否包含某个元素 O(n)
     */
    @Override
    public boolean contains(E e) {
        return indexOf(e) != -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("MyArrayList: size=%d, capacity=%d\n", size, data.length));
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i != size -1)
                sb.append(", ");
        }
        sb.append("]");
        return sb.toString();
    }
}


LinkedList

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
public class MyLinkedList<E> implements List<E> {

    private class Node {
        E e;
        Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }
        public Node(E e) {
            this(e, null);
        }
        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public MyLinkedList() {
        dummyHead = new Node(null, null);
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void add(int index, E e) { // O(n)
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");
        Node prev = dummyHead;
        for (int i = 0; i < index; i++)
            prev = prev.next;
        prev.next = new Node(e, prev.next); ////
        size++;
    }

    @Override
    public void addLast(E e) {  // O(n)
        add(size, e);
    }

    @Override
    public void addFirst(E e) { // O(1)
        add(0, e);
    }

    @Override
    public E remove(int index) { // O(n)
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        Node prev = dummyHead;
        for (int i = 0; i < index; i++)
            prev = prev.next;

        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size--;

        return delNode.e;
    }

    @Override
    public E removeLast() { // O(n)
        return remove(size-1);
    }

    @Override
    public E removeFirst() { // O(1)
        return remove(0);
    }

    @Override
    public void removeElement(E e) { // O(n)
        Node prev;
        for(prev = dummyHead; prev.next != null; prev = prev.next) {
            if (Objects.equals(e, prev.next.e)) break;
        }
        Node delNode = prev.next;
        if (delNode != null) {
            prev.next= delNode.next;
            delNode.next = null;
            size--;
        }
    }

    @Override
    public void set(int index, E e) { // O(n)
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed, illegal index.");
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;
        cur.e = e;
    }

    @Override
    public E get(int index) { // O(n)
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed, illegal index.");
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;
        return cur.e;
    }

    @Override
    public E getLast() { // O(n)
        return get(size-1);
    }

    @Override
    public E getFirst() { // O(1)
        return get(0);
    }

    @Override
    public int indexOf(E e) { // O(n)
        Node cur = dummyHead.next;
        for (int i = 0; i < size; i++) {
            if (Objects.equals(e, cur.e))
                return i;
            cur = cur.next;
        }
        return -1;
    }

    @Override
    public boolean contains(E e) { // O(n)
        return indexOf(e) != -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Node cur = dummyHead.next; cur != null; cur = cur.next)
            sb.append(cur).append("->");
        sb.append("NULL");
        return sb.toString();
    }
}


Tree

接口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public interface Tree<E> {
    
    int getSize();
    boolean isEmpty();

    void add(E e);
    void remove(E e);

    boolean contains(E e);
    E floor(E e);
    E ceil(E e);

    void traverse();
    void levelTraverse();
    void printTree();
}


二叉树

二分查找树 BST 的实现

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
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
public class MyBst<E extends Comparable<E>> implements Tree<E> {
    private class Node {
        E e;
        Node left, right;

        public Node(E e) {
            this.e = e;
        }
    }

    private Node root;
    private int size;

    public MyBst() {
        this.root = null;
        this.size = 0;
    }

    @Override
    public int getSize() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 添加 O(h) ≈ O(log2N)
     */
    @Override
    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0)
            node.left = add(node.left, e);
        else if (e.compareTo(node.e) > 0)
            node.right = add(node.right, e);
        // 相等：什么都不做
        return node;
    }

    /**
     * 删除 O(h) ≈ O(log2N)
     */
    @Override
    public void remove(E e) {
        this.root = remove(this.root, e);
    }
    private Node remove(Node curRoot, E e) {
        if (curRoot == null)
            return null;
        if (e.compareTo(curRoot.e) < 0) {
            curRoot.left = remove(curRoot.left, e);
            return curRoot;
        } else if(e.compareTo(curRoot.e) > 0) {
            curRoot.right = remove(curRoot.right, e);
            return curRoot;
        } else {
            // 待删除节点左子树为空的情况
            if (curRoot.left == null) {
                Node rightNode = curRoot.right;
                curRoot.right = null;
                size--;
                return rightNode;
            }

            // 待删除节点右子树为空的情况
            if (curRoot.right == null) {
                Node leftNode = curRoot.left;
                curRoot.left = null;
                size--;
                return leftNode;
            }

            // 待删除节点左右子树都不为空的情况
            // 找到待删除节点右子树的最小节点，用这个节点顶替待删除节点的位置
            Node successor = findMin(curRoot.right);
            successor.right = removeMin(curRoot.right);
            successor.left = curRoot.left;
            // 将 curRoot 脱离树结构，并统一维护 size
            curRoot.left = curRoot.right = null;
            size--;
            // 返回后继结点作为当前的根节点
            return successor;
        }
    }
    private Node removeMin(Node curRoot) {
        // 当前节点不能继续再往左走了，也就是当前节点就是要删除的最小的节点
        if (curRoot.left == null) {
            Node rightNode = curRoot.right; // 右子树不能丢
            curRoot.right = null; // 脱离当前节点的右节点
            // removeMin 只负责拆节点，不负责维护 size，谁调用 removeMin 谁就负责维护 size
            return rightNode; // 返回右节点作为当前的根节点
        }
        curRoot.left = removeMin(curRoot.left);
        return curRoot;
    }

    /**
     * 查找 O(h) ≈ O(log2N)
     */
    @Override
    public boolean contains(E e) {
        return contains(root, e);
    }
    private boolean contains(Node node, E e) {
        if (node == null)
            return false;
        if (e.compareTo(node.e) == 0)
            return true;
        else if (e.compareTo(node.e) < 0)
            return contains(node.left, e);
        else
            return contains(node.right, e);
    }
    private Node findMin(Node curNode) {
        while (curNode.left != null)
            curNode = curNode.left;
        return curNode;
    }

    /**
     * 返回 BST 中 ≤ e 的最大元素，不存在返回 null
     */
    @Override
    public E floor(E e) {
        if (e == null) return null;
        Node res = floor(root, e);
        return res == null ? null : res.e;
    }
    private Node floor(Node node, E e) {
        if (node == null) return null;

        int cmp = e.compareTo(node.e);
        if (cmp == 0) {
            // 精确命中
            return node;
        }
        if (cmp < 0) {
            // e 比当前节点小，答案只能在左子树
            return floor(node.left, e);
        }
        // e > node.e，当前节点是候选，但右子树可能有更"大"且仍然 ≤ e 的
        Node rightCandidate = floor(node.right, e);
        return rightCandidate != null ? rightCandidate : node;
    }

    /**
     * 返回 BST 中 ≥ e 的最小元素，不存在返回 null
     */
    @Override
    public E ceil(E e) {
        if (e == null) return null;
        Node res = ceil(root, e);
        return res == null ? null : res.e;
    }
    private Node ceil(Node node, E e) {
        if (node == null) return null;

        int cmp = e.compareTo(node.e);
        if (cmp == 0) {
            // 精确命中
            return node;
        }
        if (cmp > 0) {
            // e 比当前大，答案只在右子树
            return ceil(node.right, e);
        }
        // e < node.e，当前节点是候选，左子树可能有更"小"且仍然 ≥ e 的
        Node leftCandidate = ceil(node.left, e);
        return leftCandidate != null ? leftCandidate : node;
    }

    /**
     * 前、后、中序遍历
     */
    @Override
    public void traverse() {
        System.out.print("递归前序遍历："); preOrder(root); System.out.println();
        System.out.println("迭代前序遍历：" + preOrder2());

        System.out.print("递归后序遍历："); postOrder(root); System.out.println();
        System.out.println("迭代后序遍历：" + postOrder2());

        System.out.print("递归中序遍历："); inOrder(root); System.out.println();
        System.out.println("迭代中序遍历：" + inOrder2());
    }
    private void preOrder(Node node) {
        // 前序遍历，最常用
        if (node == null) return;
        System.out.print(node.e + " "); // 根
        preOrder(node.left);  // 左
        preOrder(node.right); // 右
    }
    private void postOrder(Node node) {
        // 后序遍历，优先处理叶子节点（深度优先）
        if (node == null) return;
        postOrder(node.left); // 左
        postOrder(node.right); // 右
        System.out.print(node.e + " "); // 根
    }
    private void inOrder(Node node) {
        // 中序遍历，遍历出的结果从小到大排列
        if (node == null) return;
        inOrder(node.left); // 左
        System.out.print(node.e + " "); // 根
        inOrder(node.right); // 右
    }
    private List<E> preOrder2() {
        List<E> res = new MyArrayList<>();
        if (root == null) return res;

        Stack<Node> stack = new MyArrayStack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            res.addLast(node.e);
            // 注意：先压右，再压左，出栈顺序才是 左 -> 右
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return res;
    }
    private List<E> postOrder2() {
        List<E> res = new MyLinkedList<>();
        if (root == null) return res;

        Stack<Node> stack = new MyArrayStack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            // 关键点：每次插入到索引 0 位置（相当于做一次反转）
            // 弹出顺序 根 -> 右 -> 左，插入头部后变成 左 -> 右 -> 根
            res.addFirst(node.e);
            // 先压左，再压右
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return res;
    }
    private List<E> inOrder2() {
        List<E> res = new MyArrayList<>();
        Stack<Node> stack = new MyArrayStack<>();
        Node cur = root;
        while (cur != null || !stack.isEmpty()) {
            // 1. 一路向左，将所有左子节点压栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 2. 弹出并访问
            cur = stack.pop();
            res.addLast(cur.e);
            // 3. 转向右子树
            cur = cur.right;
        }
        return res;
    }

    /**
     * 层序遍历（广度优先）
     */
    @Override
    public void levelTraverse() {
        if (root == null)
            throw new IllegalStateException("BST is empty.");
        System.out.print("迭代层序遍历：");
        Queue<Node> queue = new MyArrayLoopQueue<>();
        queue.enqueue(root);
        while (!queue.isEmpty()) {
            Node cur = queue.dequeue();
            System.out.print(cur.e + " ");

            if (cur.left != null)
                queue.enqueue(cur.left);
            if (cur.right != null)
                queue.enqueue(cur.right);
        }
    }

    @Override
    public void printTree() {
        printTree(root, 0);
    }
    private void printTree(Node node, int level) {
        // 如果需要分别对左右子树做分别处理，可以增加入参标识
        if (node == null) return;

        // 1. 先打印右子树（因为在视觉上右子树在上方）
        printTree(node.right, level + 1);

        // 2. 打印当前节点：根据层级进行缩进
        if (level == 0) {
            System.out.println(node.e);
        } else {
            String subPrefix = "|    ".repeat(level - 1);
            System.out.println(subPrefix + "|----" + node.e);
        }

        // 3. 最后打印左子树
        printTree(node.left, level + 1);
    }

    public static void main(String[] args) {
        MyBst<Integer> bst = new MyBst<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums) {
            bst.add(num);
        }
        ///////////////
        //     5     //
        //   3   6   //
        // 2  4   8  //
        ///////////////

        bst.traverse();
        /*
        递归前序遍历：5 3 2 4 6 8
        迭代前序遍历：[5, 3, 2, 4, 6, 8]
        递归后序遍历：2 4 3 8 6 5
        迭代后序遍历：[2, 4, 3, 8, 6, 5]
        递归中序遍历：2 3 4 5 6 8
        迭代中序遍历：[2, 3, 4, 5, 6, 8]
        */

        bst.levelTraverse();
        System.out.println();
        // 迭代层序遍历：5 3 6 2 4 8

        Integer floor = bst.floor(7);
        System.out.println(floor); // 6
        Integer ceil = bst.ceil(7);
        System.out.println(ceil); // 8

        bst.printTree();
        System.out.println();
        bst.remove(3); //
        bst.printTree();
        ///////////////
        //     5     //
        //   4   6   //
        // 2      8  //
        ///////////////
    }
}


线段树

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
/**
 * 线段树
 * 这里我们使用数组的存储方式，对于n个元素，开4n长度数组，就完全可以存储整棵线段树
 * 线段树实际只用 2n ~ 4n
 *
 *                    A[0..9]
 *          ┌────────────┴──────────────┐
 *       A[0..4]                     A[5..9]
 *    ┌─────┴─────┐               ┌─────┴─────┐
 *  A[0..1]    A[2..4]         A[5..6]     A[7..9]
 *  ┌──┴──┐    ┌──┴──┐         ┌──┴──┐     ┌──┴──┐
 * A[0] A[1]  A[2]  A[3..4]   A[5]  A[6]  A[7]  A[8..9]
 *                  ┌──┴──┐                     ┌──┴──┐
 *                 A[3]  A[4]                  A[8]  A[9]
 *
 * data 是原始数组（输入），tree 是线段树本身（查询结果存的地方）。
 * data 存在的意义是：建树时提供叶子节点的值 + 「单点更新」时作为“真值源”。
 */
public class SegmentTree<E> {

    public interface Merger<E> {
        E merge(E a, E b);
    }

    private E[] tree; // 线段树本体（堆式存储），存的是区间聚合值
    private E[] data; // 原始数据数组，保留用户视角的完整输入
    private Merger<E> merger; // 聚合逻辑（如：Integer::sum / Math::max / Math::min）

    /**
     * 根据原始数组构建线段树
     *
     * @param array  原始元素数组（不会被直接引用，内部拷贝一份到 data）
     * @param merger 区间合并策略：告诉线段树"父节点如何由两个子节点算出来"
     */
    public SegmentTree(E[] array, Merger<E> merger) {
        this.merger = merger;
        // 深拷贝原始数组（避免外部修改影响线段树内部状态）
        data = (E[]) new Object[array.length];
        System.arraycopy(array, 0, data, 0, array.length);
        // 开 4n 空间，保证完全二叉树不会越界
        tree = (E[]) new Object[array.length * 4];
        // 从根节点 treeIndex=0 开始递归建树
        buildSegmentTree(0, 0, data.length-1);
    }

    /**
     * 递归建树：在 tree[treeIndex] 处，为区间 [left..right] 建立节点
     *
     * 递归过程：
     * 1. 到达叶子（left==right）：tree 节点值 = data[left]，即单个元素本身
     * 2. 非叶子：先递归建左右子树，再 merge 左右子树的结果作为当前节点的值
     */
    private void buildSegmentTree(int treeIndex, int left, int right) {
        // 递归结束条件
        if (left == right) {
            // 建树时，递归到叶子时，需要知道 [left..right] 这个区间对应的原始元素是谁，所以必须要存 data 这个数组
            tree[treeIndex] = data[left];
            return;
        }

        // 构建递归过程
        int leftTreeIndex = leftChildIndex(treeIndex);
        int rightTreeIndex = rightChildIndex(treeIndex);

        int middle = left + (right- left) / 2;
        buildSegmentTree(leftTreeIndex, left, middle);
        buildSegmentTree(rightTreeIndex, middle+1, right);

        // 具体的业务逻辑
        tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
    }

    public int getSize() {
        return data.length;
    }

    /**
     * 获取原始数组中 index 位置的元素（O(1)）
     */
    public E get(int index) {
        if (index < 0 || index >= data.length)
            throw new IllegalArgumentException("Index is illegal.");
        return data[index];
    }

    private int leftChildIndex(int index) {
        return 2 * index + 1;
    }
    private int rightChildIndex(int index) {
        return 2 * index + 2;
    }

    /**
     * 查询 O(logN)
     * 用 merger 定义的规则，返回区间 [queryLeft, queryRight] 上的聚合结果
     * 如：求和 / 最大值 / 最小值
     */
    public E query(int queryLeft, int queryRight) {
        if (queryLeft < 0 || queryLeft >= data.length ||
            queryRight < 0 || queryRight >= data.length ||
            queryLeft > queryRight) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        return query(0, 0, data.length-1, queryLeft, queryRight);
    }

    /**
     * 内部递归查询：
     * 当前节点 treeIndex 负责区间 [left..right]
     * 要查询的目标区间是 [queryLeft..queryRight]
     */
    private E query(int treeIndex, int left, int right, int queryLeft, int queryRight) {
        // 情况1：当前节点区间完全覆盖查询区间 → 直接返回当前节点值（不需要再往下走），递归结束！
        if (left == queryLeft && right == queryRight)
            return tree[treeIndex];

        int middle = left + (right - left) / 2;
        int leftTree = leftChildIndex(treeIndex);
        int rightTree = rightChildIndex(treeIndex);

        if (queryLeft >= middle + 1)
            // 情况2：查询区间完全在右半边
            return query(rightTree, middle + 1, right, queryLeft, queryRight);
        else if (queryRight <= middle)
            // 情况3：查询区间完全在左半边
            return query(leftTree, left, middle, queryLeft, queryRight);
        else {
            // 情况4：查询区间横跨中点 → 拆成左右两段分别查，再 merge 结果
            E leftRes = query(leftTree, left, middle, queryLeft, middle);
            E rightRes = query(rightTree, middle + 1, right, middle + 1, queryRight);
            return merger.merge(leftRes, rightRes);
        }
    }

    /**
     * 更新 O(logN)
     * 对于普通数组，更新和查询的复杂度都是 O(N)
     * 但是对于线段树，更新和查询的复杂度能够降低到 O(logN)
     */
    public void set(int index, E e) {
        if (index < 0 || index >= data.length)
            throw new IllegalArgumentException("Index is illegal.");
        data[index] = e;
        set(0, 0, data.length-1, index, e);
    }

    private void set(int treeIndex, int left, int right, int index, E e) {
        if (left == right) {
            tree[treeIndex] = e;
            return;
        }

        int middle = left + (right-left)/2;
        int leftTreeIndex = leftChildIndex(treeIndex);
        int rightTreeIndex = rightChildIndex(treeIndex);
        if (index >= middle + 1)
            set(rightTreeIndex, middle+1, right, index, e);
        else
            set(leftTreeIndex, left, middle, index, e);

        // 回溯：左右子树更新完后，重新计算当前节点的值
        tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
    }

    @Override
    public String toString() {
        StringBuilder ret = new StringBuilder();
        ret.append('[');
        for (int i = 0; i < tree.length; i++) {
            if (tree[i] != null)
                ret.append(tree[i]);
            else
                ret.append("null");
            if (i != tree.length-1)
                ret.append(',');
        }
        ret.append(']');
        return ret.toString();
    }

    public static void main(String[] args) {
        // 给定一个数组，求出索引i到索引j的和
        Integer[] array = {-2,0,3,-5,2,-1};
        SegmentTree<Integer> segmentTree = new SegmentTree<>(array, Integer::sum);
        System.out.println(segmentTree);
        Integer query = segmentTree.query(2, 5);
        System.out.println(query);

        // 针对这个特殊的问题，一个更好的方式是使用预处理
        Integer[] sumArray = new Integer[array.length+1]; // sumArray[i] 存储前n个元素的和
        sumArray[0] = 0;
        for (int i = 1; i < sumArray.length; i++) {
            sumArray[i] = sumArray[i-1] + array[i-1];
        }
        int result = sumArray[5+1] - sumArray[2];
        System.out.println(result);
    }
}


Heap

接口定义

1
2
3
4
5
6
7
8
9
10
11
public interface Heap<E> {

    int getSize();
    boolean isEmpty();

    void add(E e);
    E extractMax();
    E replace(E e);

    E findMax();
}


MaxHeap

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
/**
 * 堆的定义
 * 1. 堆是一棵完全二叉树
 * 2. 所有父节点不小于（不大于）【这个节点】的子节点
 * 基于堆的特点，可以使用数组存放二叉堆这种结构。
 *
 *               62[0]
 *             /       \
 *         41[1]        30[2]
 *         /     \       /    \
 *      28[3]   16[4]  22[5]  13[6]
 *     /    \     /
 * 19[7]  17[8] 15[9]
 *
 * 父节点索引 = (孩子节点索引 - 1) / 2
 * 左孩子节点索引 = (2 * 父节点索引) + 1
 * 右孩子节点索引 = (2 * 父节点索引) + 2
 *
 * 其实对于MaxHeap，它也可以完全支持最小堆的逻辑，只需要适当定义 compareTo 即可
 * 堆其实也是一种平衡二叉树（高度差最多为1）
 */
public class MaxHeap<E extends Comparable<E>> implements Heap<E> {

    private MyArrayList<E> data;

    public MaxHeap(int capacity) {
        this.data = new MyArrayList<>(capacity);
    }
    public MaxHeap() {
        data = new MyArrayList<>();
    }
    public MaxHeap(E[] array) { // 将任意数组整理成堆的形状
        this.data = new MyArrayList<>(array);
        for (int i = parentIndex(array.length-1); i >= 0; i--)
            siftDown(i);
    }

    @Override
    public int getSize() {
        return data.getSize();
    }

    @Override
    public boolean isEmpty() {
        return data.isEmpty();
    }

    private int parentIndex(int index) {
        if (index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }
    private int leftChildIndex(int index) {
        return 2 * index + 1;
    }
    private int rightChildIndex(int index) {
        return 2 * index + 2;
    }

    /**
     * 向堆中添加元素 O(logN)
     */
    @Override
    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }
    private void siftUp(int k) {
        while (k > 0 && data.get(parentIndex(k)).compareTo(data.get(k)) < 0) { // 一路上浮
            data.swap(k, parentIndex(k));
            k = parentIndex(k);
        }
    }

    /**
     * 取出堆中最大的元素 O(logN)
     */
    @Override
    public E extractMax() {
        E ret = findMax();

        // 将堆中最后一个元素与最大元素交换位置
        data.swap(0, data.getSize()-1);
        // 删除最后一个位置的元素，也就是最大的元素
        data.removeLast();
        // 下沉操作，让整个堆重新满足堆的性质
        siftDown(0);

        return ret;
    }
    private void siftDown(int k) {
        while (leftChildIndex(k) < data.getSize()) {
            // 找出左右孩子节点中的较大的那个
            int j = leftChildIndex(k);
            if (j + 1 < data.getSize() && data.get(j+1).compareTo(data.get(j)) > 0) {
                // 有右孩子节点，并且比左孩子节点要大，那么使用 j 暂存右节点的索引
                j++;
            }
            // 当前k位置节点与左右孩子节点中较大的那个比较，如果满足堆的条件则终止循环
            if (data.get(k).compareTo(data.get(j)) >= 0) break;
            // 否则交换 k、j 位置元素，继续循环
            data.swap(k, j);
            k = j;
        }
    }

    /**
     * 取出堆中最大的元素，并且替换成元素e
     */
    @Override
    public E replace(E e) {
        E ret = findMax();

        data.set(0, e);
        siftDown(0);

        return ret;
    }

    /**
     * 查看堆中最大的元素 O(1)
     */
    @Override
    public E findMax() {
        if (data.getSize() == 0)
            throw new IllegalStateException("Cannot findMax when heap is empty.");
        return data.get(0);
    }


    /**
     * 获取 topK（降序），O(nlogK)
     */
    public static <T extends  Comparable<T>> T[] topK(T[] array, int k) {
        MaxHeap<T> heap = new MaxHeap<>();
        for (T t : array) {
            if (heap.getSize() < k) {
                heap.add(t);
            } else if (t.compareTo(heap.findMax()) > 0) {
                heap.replace(t);
            }
        }

        T[] ret = (T[]) new Object[k];
        int index = 0;
        while (!heap.isEmpty()) {
            ret[index++] = heap.extractMax();
        }
        return ret;
    }

    public static void main(String[] args) {
        int n = 1000000; // 测试100万数据的堆排序

        long start = System.nanoTime();
        MaxHeap<Integer> maxHeap = new MaxHeap<>();
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            maxHeap.add(random.nextInt(Integer.MAX_VALUE));
        }

        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = maxHeap.extractMax();
        }

        for (int i = 1; i < n; i++) {
            if (array[i-1] < array[i])
                throw new IllegalStateException("测试不通过");
        }
        long end = System.nanoTime();
        System.out.println("测试正常，耗时：" + (end-start)/1000000000.0); // 1.27677449
    }
}


Map and Set

接口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public interface Map<K,V> {
    int getSize();
    boolean isEmpty();

    void put(K key, V value);
    V remove(K key);

    boolean containsKey(K key);
    V get(K key);
}


public interface Set<E> {
    int getSize();
    boolean isEmpty();

    void add(E e);
    void remove(E e);
    boolean contains(E e);
}


LinkedMap and Set

MyLinkedMap

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
public class MyLinkedMap<K, V> implements Map<K,V> {

    private class Node {
        K key;
        V value;
        Node next;

        public Node(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public Node(K key) {
            this(key, null, null);
        }
        public Node() {
            this(null, null, null);
        }

        @Override
        public String toString() {
            return key.toString() + " " + value.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public MyLinkedMap() {
        dummyHead = new Node();
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void put(K key, V value) { // O(n)
        Node node = getNode(key);
        if (node == null) {
            dummyHead.next = new Node(key, value, dummyHead.next);
            size++;
        } else {
            node.value = value;
        }
    }

    @Override
    public V remove(K key) { // O(n)
        Node prev = dummyHead;
        while (prev.next != null && !Objects.equals(prev.next.key, key)) {
            prev = prev.next;
        }
        if (prev.next != null) {
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
            return delNode.value;
        }
        return null;
    }

    @Override
    public boolean containsKey(K key) {
        return getNode(key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(key);
        return node != null ? node.value : null;
    }

    private Node getNode(K key) { // O(n)
        Node cur = dummyHead.next;
        while (cur != null) {
            if (Objects.equals(cur.key, key))
                return cur;
            cur = cur.next;
        }
        return null;
    }
}


MyLinkedSet

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
public class MyLinkedSet<E> implements Set<E> {

    private MyLinkedList<E> list;
    public MyLinkedSet() {
        this.list = new MyLinkedList<>();
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void add(E e) {
        if (list.contains(e)) return;
        list.addFirst(e);
    }

    @Override
    public void remove(E e) {
        list.removeElement(e);
    }

    @Override
    public boolean contains(E e) {
        return list.contains(e);
    }
}


BstMap and Set

MyBstMap

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
/**
 * 基于二分搜索树实现的 map（对应 Java 的实现 TreeMap）
 * 与 MyBinarySearchTree 基本相同，只需要更改 Node 的定义即可
 */
public class MyBstMap<K extends Comparable<K>, V> implements Map<K, V> {

    private class Node {
        K key;
        V value;
        Node left, right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private Node root;
    private int size;

    public MyBstMap() {
        root = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void put(K key, V value) {
        if (key == null)
            throw new IllegalArgumentException("key cannot be null in BST Map");
        root = put(root, key, value);
    }
    private Node put(Node node, K key, V value) {
        if (node == null) {
            size++;
            return new Node(key, value);
        }
        if (key.compareTo(node.key) < 0)
            node.left = put(node.left, key, value);
        else if (key.compareTo(node.key) > 0)
            node.right = put(node.right, key, value);
        else // 相等
            node.value = value;
        return node;
    }

    @Override
    public V remove(K key) {
        Node removedNode = new Node(null, null);
        this.root = remove(this.root, key, removedNode);
        return removedNode.value; // 没删到就是 null
    }
    private Node remove(Node curRoot, K key, Node removedNode) {
        if (curRoot == null)
            return null;
        if (key.compareTo(curRoot.key) < 0) {
            curRoot.left = remove(curRoot.left, key, removedNode);
            return curRoot;
        } else if(key.compareTo(curRoot.key) > 0) {
            curRoot.right = remove(curRoot.right, key, removedNode);
            return curRoot;
        } else {
            //
            removedNode.value = curRoot.value;

            // 待删除节点左子树为空的情况
            if (curRoot.left == null) {
                Node rightNode = curRoot.right;
                curRoot.right = null;
                size--;
                return rightNode;
            }

            // 待删除节点右子树为空的情况
            if (curRoot.right == null) {
                Node leftNode = curRoot.left;
                curRoot.left = null;
                size--;
                return leftNode;
            }

            // 待删除节点左右子树都不为空的情况
            // 找到待删除节点右子树的最小节点，用这个节点顶替待删除节点的位置
            Node successor = findMin(curRoot.right);
            successor.right = removeMin(curRoot.right);
            successor.left = curRoot.left;
            // 将 curRoot 脱离树结构，并统一维护 size
            curRoot.left = curRoot.right = null;
            size--;
            // 返回后继结点作为当前的根节点
            return successor;
        }
    }
    private Node removeMin(Node curRoot) {
        // 当前节点不能继续再往左走了，也就是当前节点就是要删除的最小的节点
        if (curRoot.left == null) {
            Node rightNode = curRoot.right; // 右子树不能丢
            curRoot.right = null; // 脱离当前节点的右节点
            // removeMin 只负责拆节点，不负责维护 size，谁调用 removeMin 谁就负责维护 size。
            return rightNode; // 返回右节点作为当前的根节点
        }
        curRoot.left = removeMin(curRoot.left);
        return curRoot;
    }
    private Node findMin(Node curNode) {
        while (curNode.left != null)
            curNode = curNode.left;
        return curNode;
    }

    @Override
    public boolean containsKey(K key) {
        return getNode(root, key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(root, key);
        return node != null ? node.value : null;
    }

    private Node getNode(Node node, K key) {
        if (node == null)
            return null;
        if (key.compareTo(node.key) == 0)
            return node;
        else if (key.compareTo(node.key) < 0)
            return getNode(node.left, key);
        else
            return getNode(node.right, key);
    }


    private static int[] intersection(int[] nums1, int[] nums2) { // 返回两个数组的交集（允许重复）
        MyBstMap<Integer, Integer> map = new MyBstMap<>();
        for (int num : nums1) {
            if (!map.containsKey(num)) {
                map.put(num, 1);
            } else {
                map.put(num, map.get(num) + 1);
            }
        }

        List<Integer> list = new MyArrayList<>();
        for (int num : nums2) {
            if (map.containsKey(num)) {
                list.addLast(num);
                map.put(num, map.get(num)-1);
                if (map.get(num) == 0)
                    map.remove(num);
            }
        }

        int[] res = new int[list.getSize()];
        for (int i = 0; i < list.getSize(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public static void main(String[] args) {
        int[] nums1 = {1,2,3,4,4,5};
        int[] nums2 = {3,4,4,5,6,7};
        int[] res = intersection(nums1, nums2);
        System.out.println(Arrays.toString(res)); // [3, 4, 4, 5]
    }
}


MyBstSet

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
/**
 * 对应的 Java 的实现 TreeSet
 */
public class MyBstSet<E extends Comparable<E>> implements Set<E> {

    private MyBst<E> bst;
    public MyBstSet() {
        this.bst = new MyBst<>();
    }

    @Override
    public int getSize() {
        return bst.getSize();
    }

    @Override
    public boolean isEmpty() {
        return bst.isEmpty();
    }

    @Override
    public void add(E e) {
        bst.add(e);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }

    @Override
    public boolean contains(E e) {
        return bst.contains(e);
    }

    private static int[] intersection(int[] nums1, int[] nums2) { // 返回两个数组的交集（不允许重复）
        MyBstSet<Integer> set = new MyBstSet<>();
        for (int num : nums1)
            set.add(num);

        List<Integer> list = new MyArrayList<>();
        for (int num : nums2) {
            if (set.contains(num)) {
                list.addLast(num);
                set.remove(num);
            }
        }

        int[] res = new int[list.getSize()];
        for (int i = 0; i < list.getSize(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public static void main(String[] args) {
        int[] nums1 = {1,2,3,4,4,5};
        int[] nums2 = {3,4,4,5,6,7};
        int[] res = intersection(nums1, nums2);
        System.out.println(Arrays.toString(res)); // [3, 4, 5]
    }
}


Stack

接口定义

1
2
3
4
5
6
7
8
9
public interface Stack<E> {
    int getSize();
    boolean isEmpty();

    void push(E e);
    E pop();

    E peek();
}


ArrayStack

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
public class MyArrayStack<E> implements Stack<E> {

    private final List<E> array;
    public MyArrayStack(int capacity) {
        array = new MyArrayList<>(capacity);
    }
    public MyArrayStack() {
        array = new MyArrayList<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public void push(E e) { // O(1)
        array.addLast(e);
    }

    @Override
    public E pop() {  // O(1)
        return array.removeLast();
    }

    @Override
    public E peek() { // O(1)
        return array.getLast();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Stack: [");
        for (int i = 0; i < array.getSize(); i++) {
            sb.append(array.get(i));
            if (i != array.getSize()-1)
                sb.append(", ");
        }
        sb.append("] top");
        return sb.toString();
    }

    // 判断括号是否匹配
    public static void main(String[] args) {
        String s = "{[()]}(a+b)";
        Stack<Character> stack = new MyArrayStack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') { // 显式匹配右括号
                if (stack.isEmpty()) {
                    System.out.println("匹配失败");
                    return;
                }
                char topChar = stack.pop();
                if ((c == ')' && topChar != '(') ||
                    (c == ']' && topChar != '[') ||
                    (c == '}' && topChar != '{')) {
                    System.out.println("匹配失败");
                    return;
                }
            }
        }
        if (stack.isEmpty()) {
            System.out.println("匹配成功");
        } else {
            System.out.println("匹配失败");
        }
    }
}


LinkedStack

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
public class MyLinkedStack<E> implements Stack<E> {

    private final List<E> list;
    public MyLinkedStack() {
        this.list = new MyLinkedList<>();
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void push(E e) { // O(1)
        list.addFirst(e);
    }

    @Override
    public E pop() { // O(1)
        return list.removeFirst();
    }

    @Override
    public E peek() { // O(1)
        return list.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Stack: top ");
        sb.append(list);
        return sb.toString();
    }

    private static double testStack(Stack stack, int opCount) {
        long start = System.nanoTime();
        Random random = new Random();
        for (int i = 0; i < opCount; i++)
            stack.push(random.nextInt(Integer.MAX_VALUE));
        for (int i = 0; i < opCount; i++)
            stack.pop();
        long end = System.nanoTime();
        return (end - start) / 1000000000.0;
    }
    public static void main(String[] args) {
        int opCount = 1000000;

        Stack<Integer> stack1 = new MyArrayStack<>();
        double t1 = testStack(stack1, opCount);
        System.out.println("array stack time: " + t1); // 0.073697873

        Stack<Integer> stack2 = new MyLinkedStack<>();
        double t2 = testStack(stack2, opCount);
        System.out.println("linked stack time: " + t2); // 0.238648321
    }
}


Queue

接口定义

1
2
3
4
5
6
7
8
9
public interface Queue<E> {
    int getSize();
    boolean isEmpty();

    void enqueue(E e);
    E dequeue();

    E getFront();
}


ArrayQueue

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
/**
 * 普通数组队列
 * 问题是出队的复杂度是 O(n)，可以使用循环队列的思路进行优化
 */
public class MyArrayQueue<E> implements Queue<E> {

    private final List<E> array;
    public MyArrayQueue(int capacity) {
        array = new MyArrayList<>(capacity);
    }
    public MyArrayQueue() {
        array = new MyArrayList<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public void enqueue(E e) { // O(1)
        array.addLast(e);
    }

    @Override
    public E dequeue() { // O(n)
        return array.removeFirst();
    }

    @Override
    public E getFront() { // O(1)
        return array.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Queue: front [");
        for (int i = 0; i < array.getSize(); i++) {
            sb.append(array.get(i));
            if (i != array.getSize()-1) {
                sb.append(", ");
            }
        }
        sb.append("] tail");
        return sb.toString();
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new MyArrayQueue<>();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);
            if (i % 3 == 2) { // 每入队3次，出队1次
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}


ArrayLoopQueue

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
/**
 * 循环数组队列，所有操作保证在 O(1) 复杂度完成
 * 当 tail 到达数组末尾（索引 7）时，通过模运算 (tail + 1) % data.length 回到数组头部（索引 0）。
 * 入队 H、I，直到 tail + 1 追上 front，此时还剩 1 个空位，但为了与队空做区分，判定为队满。
 *
 *   索引 (index):     0     1     2     3     4     5     6     7
 *                 +-----+-----+-----+-----+-----+-----+-----+-----+
 *   数据 (data):  |  I  |     |  C  |  D  |  E  |  F  |  G  |  H  |
 *                +-----+-----+-----+-----+-----+-----+-----+-----+
 *                        ▲      ▲
 *                       tail  front
 *
 * 队空条件：front == tail
 * 队满条件：(tail + 1) % data.length == front
 * 入队指针推进：tail = (tail + 1) % data.length
 * 出队指针推进：front = (front + 1) % data.length
 * 有效元素个数：size = (tail - front + data.length) % data.length
 * 对于有效元素的个数：若维护了独立的 size 变量则可直接使用 size
 *
 */
public class MyArrayLoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front, tail;

    public MyArrayLoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
    }

    public MyArrayLoopQueue() {
        this(16);
    }

    private int getCapacity() {
        return data.length - 1;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        int size = getSize();
        for (int i = 0; i < size; i++)
            newData[i] = data[(i + front) % data.length];
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public int getSize() {
        return (tail - front + data.length) % data.length;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public void enqueue(E e) { // O(1)
        if ((tail + 1) % data.length == front) // 满了
            resize(getCapacity() * 2);
        data[tail] = e;
        tail = (tail + 1) % data.length;
    }

    @Override
    public E dequeue() { // O(1)
        if (front == tail)
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        E result = data[front];
        data[front] = null;
        front = (front + 1) % data.length;

        int size = getSize();
        int capacity = getCapacity();
        if (size == capacity/4 && capacity/2 >= 16) // 可以防止在小数组范围内频繁做无效缩容
            resize(capacity/2);

        return result;
    }

    @Override
    public E getFront() { // O(1)
        if (isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        int size = getSize();
        sb.append(String.format("Queue: size=%d, capacity=%d\n", size, getCapacity()));
        sb.append("front [");
        for (int i = front; i != tail; i = (i+1) % data.length) {
            sb.append(data[i]);
            if ((i+1) % data.length != tail)
                sb.append(", ");
        }
        sb.append("] tail");
        return sb.toString();
    }
}


MyLinkedQueue

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
public class MyLinkedQueue<E> implements Queue<E> {

    private class Node {
        E e;
        Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }
        public Node(E e) {
            this(e, null);
        }
        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head, tail;
    private int size;

    public MyLinkedQueue() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void enqueue(E e) { // O(1)
        if (tail == null) {
            tail = new Node(e);
            head = tail;
        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    @Override
    public E dequeue() {  // O(1)
        if (isEmpty())
            throw new IllegalStateException("Cannot dequeue from an empty queue.");
        Node retNode = head;
        head = head.next;
        if (head == null) tail = null;
        retNode.next = null;
        size--;
        return retNode.e;
    }

    @Override
    public E getFront() { // O(1)
        if (isEmpty())
            throw new IllegalStateException("Queue is empty.");
        return head.e;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Queue: front ");

        Node cur = head;
        while (cur != null) {
            sb.append(cur + "->");
            cur = cur.next;
        }
        sb.append("NULL tail");
        return sb.toString();
    }

    private static double testQueue(Queue<Integer> q, int opCount) {
        long start = System.nanoTime();
        Random random = new Random();
        for (int i = 0; i < opCount; i++)
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        for (int i = 0; i < opCount; i++)
            q.dequeue();
        long end = System.nanoTime();
        return (end - start) / 1000000000.0;
    }
    public static void main(String[] args) {
        int opCount = 100000;

        Queue<Integer> arrayQueue = new MyArrayQueue<>();
        double t1 = testQueue(arrayQueue, opCount);
        System.out.println("Array queue, time: " + t1); // 14.850290652 s

        Queue<Integer> arrayLoopQueue = new MyArrayLoopQueue<>();
        double t2 = testQueue(arrayLoopQueue, opCount);
        System.out.println("Array loop queue, time: " + t2); // 0.013634191 s

        Queue<Integer> linkedQueue = new MyLinkedQueue<>();
        double t3 = testQueue(linkedQueue, opCount);
        System.out.println("Linked queue, time: " + t3); // 0.009182091 s
    }
}


PriorityQueue

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
/**
 * Java 提供的 PriorityQueue 默认使用的是最小堆实现的。
 * 既然优先队列是一种队列，那么从某种角度来看，栈其实特是一种特殊的队列。
 */
public class MyPriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private final MaxHeap<E> maxHeap;
    public MyPriorityQueue() {
        this.maxHeap = new MaxHeap<>();
    }

    @Override
    public int getSize() {
        return maxHeap.getSize();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }

    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeue() {
        return maxHeap.extractMax();
    }

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }
}
标题：
基本数据结构汇总
作者：
kinglyjn
声明：
引用 本文 请务必注明出处，原创不易，感谢尊重。