LJ的Blog

学海无涯苦做舟

0%

第三话--初探容器

发表于 更新于 分类于

写在前面

想看的东西太多，时间总是太少~ 好了，先甩个锅给时间不够，然后开始Java重造，抱歉的是可能有些东西我不会讲的太详细。对了，最近看了同学iamxiarui的文章。

容器

在日常撸code的过程中，很多时候我们都需要在运行时去创建新的对象。在此之前，我们可能不知道所需对象的数量甚至连类型都不知道，所以我们需要一个能在运行时保存对象引用的玩意。事实上数组是保存一组对象的最有效的方式，但是很多时候我们也不知道我们需要保存的对象的数量是多少，所以数组长度固定这一限制会让我们在实际应用中受到非常多的限制。不过好在Java提供了容器来帮我们搞定这些问题。首先上一个经典的容器图谱来理解一下~

经典.jpg

当然了关于数组有大小限制这个问题，也是可以解决的。我们先申请一个固定长度的数组，每当有元素向里面添加的时候就判断一下，当前数组是否已经满了，如果不满则直接添加进去，如果满了就按照** 一定策略 申请一个新大小的数组，将原来数组元素全部移至新数组。当数组空元素过多时，可以按照 一定策略 **缩小数组长度，这个策略取决于你的需求和应用场景。

容器&泛型

通常我们在使用容器的时候，需要的是一个类型统一的容器，即如果我插入了一个猫元素，那么我绝对不希望一只蟑螂被插入进去。我需要的是一个“猫”的容器而不是其他的，在Java SE5之前容器就存在着能向“猫”的容器中插入“蟑螂”的问题。但是说实话，《Thinking in java》作者也说了，在泛型没有出来之前，程序员会经常犯这种错误吗？不见得，在这种场景下泛型只是将错误提前在编译期就告知用户。但是在没有泛型之前，一个代码风格良好的写法应该是:

1
List cat = new ArrayList();

如此明显的一个cat集合你会插入什么其他奇奇怪怪的东西吗？所以说泛型之于容器是类型安全，但是泛型出现更重要的一个目的是 ** 让程序员编写更加通用的代码 **。

上面的话可能说的有些繁琐，请容我再整理一下：在很多实用容器的场景中，我们希望在未使用容器钱，容器容纳类型不确定，但是在放入一个类型后，我们只能使用该类型，泛型非常适合应用在这个场景。使用泛型可以让运行期的错误在编译器就被阻止。下面来个简单的例子来说明一下：

1
2
3
4
5
6
7
//<> 尖括号内的是类型参数
List<String> strList = new ArrayList<String>();
strList.add(1);//编译错误

List anotherList = new ArrayList();
anotherList.add(1);
anotherList.add("cat");//未检查警告，但是此操作不会报错

让我们用更直观的形式看一下这样操作的的结果：

情况如何

很明显使用泛型能够有效的避免将错误类型对象放置到容器中，但是关于泛型的使用不仅于此，更多的讨论放到文末。

迭代器

在《Thiniking in Java》中说到，任何容器类，都必须有某种方式可以插入元素并将它们再次取回（当然在某些书中你可能听说过bag这种只放入的容器，但是现在无需纠结这些东西）。

1
2
3
4
5
6
7
8
9
10
List<Integer> integerList = new ArrayList<Integer>();
for (int i = 0; i < 10; i++) {
    integerList.add(i);
}

Iterator<Integer> i = integerList.iterator();
while (i.hasNext()) {
    Integer j = i.next();
    System.out.println("i-->" + j);
}

以上是一个存放了0-9个值的集合，现在我们利用迭代器打印每个元素的值，先结果如下：

输出结果

LinkedList

其实我还有很多没提到的东西，但是这是初探容器啊肯定还会有再探容器啊

Java里的容器我用的比较多的大概就是HashMap、ArrayList和LinkedList，其中ArrayList用的最多。其实ArrayList和LinkedList都可以被理解为“链表”，只不过LinkedList更偏向于我们所熟知的“指针链表”，而ArrayList可以将之理解为内部是数组的链表。说实话，数组自带链子啊~

好了看上面的标题也该知道，我是不打算在这对其他的容器做更多的介绍的，大标题叫初探容器，说明我还会有再探容器的，那时再做更详细的介绍。最近看到一个有趣的东西，你输入一个”(1+(2-1))”这种格式的算是，可以用栈算出来，于是乎自己用jdk自带的LinkedList封装了一个stack，把那玩意做了出来，但是感觉不爽，因为链表用的是现成的，简单的封装也没什么难度。我不管我就要从Node开始搞一个Java的“指针链表”。

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
package thinking.Generator.other;

import java.util.NoSuchElementException;

/**
 * Created by luo-pc on 2016/9/30.
 * desc:一个双向链表
 */
public class LinkList<T> {

    /**
     * 链表的大小
     */
    int size = 0;

    /**
     * 表头
     */
    Node<T> first;

    /**
     * 表尾
     */
    Node<T> last;

    /**
     * 构造一个空的链表
     */
    public LinkList() {
    }

    public boolean add(T t) {
        insertToLast(t);
        return true;
    }

    /**
     * 在表尾插入一个元素
     *
     * @param t 元素值
     */
    private void insertToLast(T t) {
        //表尾元素
        Node<T> n = last;
        //新建一个指向表尾的元素
        Node<T> newNode = new Node<T>(n, t, null);
        //让表尾指向新元素
        last = newNode;
        //如果链表为空
        if (n == null)
            first = newNode;
        else
            n.next = newNode;
        size++;

    }

    /**
     * 获取表尾元素
     *
     * @return 返回表尾元素的值
     */
    public T getLast() {
        Node<T> n = last;
        if (n == null)
            throw new NoSuchElementException();
        return n.item;
    }

    /**
     * 根据索引获取对应元素的值
     *
     * @param index 索引
     * @return T 值
     */
    public T get(int index) {
        return node(index).item;
    }

    /**
     * 根据索引查找元素
     *
     * @param index 索引
     */
    Node<T> node(int index) {
        if (index < (size >> 1)) {
            Node<T> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<T> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.pre;
            return x;
        }
    }


    public T remove(int index) {
        checkNodeIndex(index);
        return unlink(node(index));
    }

    private void checkNodeIndex(int index) {
        if (!isNodeIndex(index))
            throw new IndexOutOfBoundsException("Index:" + index + "Size:" + size);
    }

    T unlink(Node<T> x) {
        T value = x.item;
        Node<T> next = x.next;
        Node<T> prev = x.pre;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.pre = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.pre = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        return value;
    }

    /**
     * 检查该索引是否是该链表内的元素
     *
     * @param index 索引
     * @return 是或者不是
     */
    public boolean isNodeIndex(int index) {
        return index >= 0 && index < size;
    }

    /**
     * 遍历并打印链表
     */
    public void travelList() {
        Node travelNode = first;
        if (travelNode == null)
            return;
        while (travelNode.next != null) {
            System.out.println(travelNode.item);
            travelNode = travelNode.next;
        }
    }

    public int size(){
        return this.size;
    }

    //--------------------------------Node-------------------------------//

    /**
     * 链表单个元素的类型
     *
     * @param <T>
     */
    private static class Node<T> {
        T item;
        Node<T> next;
        Node<T> pre;

        Node(Node<T> prev, T element, Node<T> next) {
            this.item = element;
            this.next = next;
            this.pre = prev;
        }
    }

    public static void main(String[] args) {
        LinkList<String> strList = new LinkList<>();
        strList.add("str1");
        strList.add("str2");
        strList.add("str3");
        strList.add("str4");

        strList.travelList();

    }
}

我这实现了一个双向链表，操作起来方便一点，实现的时候参考了一下Java的LinkedList。底下的main()函数仅仅作为测试之用。接下来简单的封装一下，将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
package thinking.Generator.other;

import java.util.NoSuchElementException;

/**
 * Created by luo-pc on 2016/10/1.
 * desc:
 */
@SuppressWarnings("unused")
public class MyStack<T> {
    private LinkList<T> stack;

    public MyStack() {
        stack = new LinkList<T>();
    }

    /**
     * 弹出栈顶元素并返回
     */
    public T pop() {
        if (stack.size() > 0) {
            return stack.remove(stack.size() - 1);
        } else {
            throw new NoSuchElementException();
        }
    }

    /**
     * 入栈操作
     *
     * @param t 入栈的值
     * @return 操作结果
     */
    public boolean push(T t) {
        return stack.add(t);
    }

    /**
     * 返回栈顶元素的值但是不弹出他
     */
    public T peek() {
        return stack.getLast();
    }

    public boolean isEmpty() {
        return stack.size == 0;
    }

    public int size() {
        return stack.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
public static void main(String[] args) {
    /**
     * 关于表达式（由括号、运算符和操作数组成）处理的规则：
     * 1.将操作数压入栈
     * 2.将运算符压入运算符栈
     * 3.忽略左括号
     * 4.在遇到右括号时弹出一个运算符，弹出所需数量的操作数，并将
     * 运算符和操作数的运算结果压入操作数的栈
     */
    //操作数栈
    MyStack<Double> integerStack = new MyStack<>();
    //运算符栈
    MyStack<Character> opStack = new MyStack<>();

    String integers = "0123456789";
    String a = "(1+((2+3)*(4*5)))";
    char[] b = new char[a.length()];
    for (int i = 0; i < b.length; i++) {
        b[i] = a.charAt(i);
    }
    for (char i : b) {
        //1.将操作数压入栈
        if (contain(integers, i)) {
            integerStack.push(Double.parseDouble("" + i));
        } else if (i == '+' || i == '-' || i == '*' || i == '/') {//2.将操作符压入栈
            opStack.push(i);
        } else if (i == '(') {//3.忽略左括号
        } else if (i == ')') {//4.运算
            double opt1 = integerStack.pop();
            double opt2 = integerStack.pop();
            double opt3 = 0.0;
            char operator = opStack.pop();
            if (operator == '+') {
                opt3 = opt1 + opt2;
                System.out.println(opt1 + "+" + opt2 + "=" + opt3);
            }
            if (operator == '-') {
                opt3 = opt1 - opt2;
                System.out.println(opt1 + "-" + opt2 + "=" + opt3);
            }
            if (operator == '*') {
                opt3 = opt1 * opt2;
                System.out.println(opt1 + "*" + opt2 + "=" + opt3);

            }
            if (operator == '/') {
                opt3 = opt1 / opt2;
                System.out.println(opt1 + "/" + opt2 + "=" + opt3);
            }
            integerStack.push(opt3);
        }
    }
    System.out.println("the result is:" + integerStack.peek());
}

public static boolean contain(String s, char a) {
    char[] str = new char[s.length()];
    for (int i = 0; i < s.length(); i++) {
        str[i] = s.charAt(i);
    }
    for (char i : str) {
        if (a == i)
            return true;
    }
    return false;
}

看下结果~

看下结果

结果是不是很有趣~好了这次的复习就先到这，等到下次再探容器的时候再好好的了解一下容器。