从零开始的算法之路01——基本的数据结构

栈

下压栈（或简称栈）是一种基于后进先出（LIFO）策略的集合类型。

学习栈可以先从一个经典的例子切入：算术表达式求值。

算术表达式求值

1
( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

上述表达式的结果为101，但用 java 语言如何实现这个运算呢？答案之一就是：Dijkstra的双栈算术表达式求值算法。基本思路如下：

  • 创建2个栈（一个保存运算符，一个保存操作数）
  • 将操作数压入操作数栈
  • 将运算符压入运算符栈
  • 忽略左括号
  • 遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈

实现代码如下：

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
public static void main(String[] args) {
        // 运算符栈
        Stack<String> ops = new Stack<>();
        // 操作数栈
        Stack<Double> vals = new Stack<>();

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            if (s.equals("(")) ; // 忽略左括号
            else if (s.equals("+")) ops.add(s); // 运算符入栈
            else if (s.equals("-")) ops.add(s); // 运算符入栈
            else if (s.equals("*")) ops.add(s); // 运算符入栈
            else if (s.equals("/")) ops.add(s); // 运算符入栈
            else if (s.equals("sqrt")) ops.add(s); // 运算符入栈
            else if (s.equals(")")) { //遇到右括号，弹栈运算
                String op = ops.pop();
                Double val = vals.pop();
                if (op.equals("+")) val = vals.pop() + val;
                else if (op.equals("-")) val = vals.pop() - val;
                else if (op.equals("*")) val = vals.pop() * val;
                else if (op.equals("/")) val = vals.pop()/ val;
                else if (op.equals("sqrt")) val = Math.sqrt(val);
                vals.push(val);
            } else vals.push(Double.parseDouble(s)); // 操作数入栈
        }
        
        // 打印最终结果
        System.out.println(vals.pop());
    }

了解了栈的一种使用场景后，我们可以尝试自己来实现一个 stack ，其基本的 API 如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Stack<Item> implements Iterable<Item> {
    // 创建一个空栈
    public Stack() {}
    
    // 添加一个元素
    public void push(Item item) {}
    
    // 删除最近添加的元素
    public Item pop() {}
    
    // 栈是否为空
    public boolean isEmpty() {}
    
    // 栈中元素数量
    public int size() {}
}

用数组实现动态变容栈

首先我们可以用 java 中最常见的数据类型来做实现——数组。

由于 java 中数组是定长的，所以还需要考虑数组扩容、缩容，我们可以采用新建一个不同长度数组并把数据引用指向旧数组对应位置的方式进行 resize。

此外这里还实现了 Iterable 接口，是因为能够使用 for each 语句进行迭代遍历是集合数据类型的基本操作之一。自己写的 stack 不实现这个细节也是 ok 的，这里就不展开谈了。

实现代码如下：

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
import java.util.Iterator;

public class Stack<Item> implements Iterable<Item> {
    public Item[] items; // 数组
    public int N; // size

    // 创建一个空栈
    public Stack() {
        new Stack(16); // 默认给16的容量
    }

    public Stack(int cap) {
        /**
         * 允许用户自行定义初始数组大小
         * 另java是无法创建泛型数组的，只能用object和类型转换代替
         */
        items = (Item[]) new Object[cap];
    }

    /**
     * 将items数据移动到另一个大小不同的数组中
     *
     * @param max 新数组长度
     */
    private void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i=0; i<N; i++)
            temp[i] = items[i];
        items = temp;
    }

    // 添加一个元素
    public void push(Item item) {
        // 如果元素数量达到数组上限，双倍扩容
        if (N == items.length)
            resize(2 * items.length);
        items[N++] = item;
    }

    // 删除最近添加的元素
    public Item pop() {
        Item item = items[--N];
        items[N] = null; // 释放数组中该位置的引用，方便jvm回收
        // 如果元素数量只有数组的1/4，缩容
        if (N > 0 && N == items.length / 4)
            resize(items.length / 2);
        return item;
    }

    // 栈是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    // 栈中元素数量
    public int size() {
        return N;
    }

    @Override
    public Iterator<Item> iterator() {
        return new StackIterator();
    }
    
    // 迭代具体实现
    class StackIterator implements Iterator<Item> {
        private int i = 0;
        
        @Override
        public boolean hasNext() {
            return i < N;
        }

        @Override
        public Item next() {
            return items[i++];
        }
    }
}

链表

可以看到使用数组来表示集合类的抽象数据类型并不那么合适，频繁的扩容缩容都是对资源、性能的一种浪费。那有没有哪种数据结构可以作为更优解呢？答案是：链表。

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。

下面是一个单向链表的结点实现：

1
2
3
4
class Node {
    Item item; // 泛型元素
    Node next; // 指向另一条链表的引用
}

用链表实现栈

学会如何构造链表的结点以后，就可以拿来实现栈了。

当然我们还需要知道如何在链表中做到插入、删除数据，如何遍历链表。

这里需要注意的是单向链表可以方便地实现头部插入和尾部插入这两种形式，但是删除比较方便的实现就只有一种：头部删除。考虑到栈的后进先出（LIFO）特点，这里采用头插和头删。

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
import java.util.Iterator;

public class Stack<Item> implements Iterable<Item> {

    private class Node {
        Item item; // 泛型元素
        Node next; // 指向另一条链表的引用

        Node() {}

        Node(Item item) {
            this.item = item;
        }
    }

    private Node first; // 链表(头节点)
    private int N; // size

    // 创建一个空栈
    public Stack() {}

    // 添加一个元素
    public void push(Item item) {
        Node node = new Node(item); // 新建一个结点
        node.next = first; // 该结点插在头部，即next指向先前的头结点
        first = node; // 将first引用指向新的头节点
        N++;
    }

    // 删除最近添加的元素
    public Item pop() {
        Item item = first.item; // 取出头节点的元素
        first = first.next; // 将first引用指向后面一个结点，即删除头节点
        N--;
        return item;
    }

    // 栈是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    // 栈中元素数量
    public int size() {
        return N;
    }

    @Override
    public Iterator<Item> iterator() {
        return new StackIterator();
    }

    class StackIterator implements Iterator<Item> {
        Node current = first;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

队列

队列与栈很相似，要说不同点在于它是一种先进先出（FIFO）的集合类型。它的 API 如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Queue<Item> implements Iterable<Item> {
    // 创建空队列
    public Queue() {}
    
    // 添加一个元素
    public void enqueue(Item item) {}
    
    // 删除最早添加的元素
    public Item dequeue() {}
    
    // 队列是否为空
    public boolean isEmpty() {}
    
    // 队列中的元素数量
    public int size() {}
}

用链表实现队列也很简单，这里使用尾插和头删，与栈相比只需要多管理一个尾结点：

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
import java.util.Iterator;

public class Queue<Item> implements Iterable<Item> {
    private class Node {
        Item item; // 泛型元素
        Node next; // 指向另一条链表的引用

        Node() {}

        Node(Item item) {
            this.item = item;
        }
    }

    private Node first; // 链表（头节点）
    private Node last; // 尾结点
    private int N; // size

    // 创建空队列
    public Queue() {}

    // 添加一个元素
    public void enqueue(Item item) {
        Node node = new Node(item); // 新建一个结点
        if (isEmpty())
            first = node; // 若链表为空，则头节点指向该结点
        else
            last.next = node; // 若链表不为空，则尾结点的下个结点指向它
        last = node; // 更新last引用，指向新的尾结点
        N++;
    }

    // 删除最早添加的元素
    public Item dequeue() {
        Item item = first.item;
        first = first.next;
        if (--N == 0)
            last = null; // 若删除后链表为空，则将尾结点指向null
        return item;
    }

    // 队列是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    // 队列中的元素数量
    public int size() {
        return N;
    }

    @Override
    public Iterator<Item> iterator() {
        return new QueueIterator();
    }

    class QueueIterator implements Iterator<Item> {
        private Node current = first;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

背包

背包是一种不支持从中删除元素的集合数据类型。与队列和栈不同，它不在意元素的处理顺序。

要理解背包的概念，可以想象一个非常喜欢收集弹子球的人，一次一个，并且会不时在所有的弹子球中寻找某一颗拥有某种特点的弹子球。

一个简单的背包 API 如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Bag<Item> implements Iterable<Item> {
    // 创建一个空背包
    public Bag() {}

    // 添加一个元素
    public void add(Item item) {}

    // 背包是否为空
    public boolean isEmpty() {}
    
    // 背包中元素数量
    public int size() {}
}

这里也用链表实现一下，这里也和栈一样采用头插：

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
public class Bag<Item> implements Iterable<Item> {
    private class Node {
        Item item; // 泛型元素
        Node next; // 指向另一条链表的引用

        Node() {}

        Node(Item item) {
            this.item = item;
        }
    }
    
    private Node first;
    private int N;

    // 创建一个空背包
    public Bag() {}

    // 添加一个元素
    public void add(Item item) {
        Node node = new Node(item);
        node.next = first;
        first = node;
        N++;
    }

    // 背包是否为空
    public boolean isEmpty() {
       return N == 0;
    }

    // 背包中元素数量
    public int size() {
        return N;
    }

    @Override
    public Iterator<Item> iterator() {
        return null;
    }
    
    class BagIterator implements Iterator<Item> {
        private Node cur =  first;

        @Override
        public boolean hasNext() {
            return cur != null;
        }

        @Override
        public Item next() {
            Item item = cur.item;
            cur = cur.next;
            return item;
        }
    }
}

算法
#java #算法 #数据结构
从零开始的算法之路01——基本的数据结构
https://honosv.github.io/2021/12/17/从零开始的算法之路01——基本的数据结构/
作者
Nova
发布于
2021年12月17日
许可协议