kotlin实现ArrayDeque

Deque双端队列，一直在使用，却从未了解过源码。
内部逻辑其实很简单

1. 可扩容数组
2. 循环队列，循环栈
3. 扩容倍数1.5，size=size+(size shr 1)
4. 只从两端存取元素

fun main() {
    val deque = MyArrayDeque()
    repeat(16) {
        deque.addLast(it)
    }
    while (deque.isNotEmpty()) {
        println(deque.removeLast())
    }

}

class MyArrayDeque {
    // 存元素，不能存null，初始容量为16，避免频繁扩容，一次扩容1.5倍
    private var arr = arrayOfNulls<Int>(16)

    // 头尾节点，tail一直为null
    private var head: Int = 0
    private var tail: Int = 0

    // 实际容量
    private var size: Int = 0

    fun addFirst(value: Int) {
        // 扩容
        grow()
        head = dec(head)
        arr[head] = value
        size++
    }

    fun addLast(value: Int) {
        // 扩容
        grow()
        arr[tail] = value
        tail = inc(tail)
        size++
    }

    fun removeFirst(): Int {
        if (isEmpty()) {
            return -1
        }
        val res = arr[head]!!
        head = inc(head)
        size--
        return res
    }

    fun removeLast(): Int {
        if (isEmpty()) {
            return -1
        }
        tail = dec(tail)
        size--
        return arr[tail]!!
    }

    // 加一
    fun inc(i: Int) = if (i == arr.lastIndex) 0 else i + 1

    // 减一
    fun dec(i: Int) = if (i == 0) arr.lastIndex else i - 1

    // 扩容，内部不一定扩容
    private fun grow() {
        // 至少还有一个容量
        if (size < arr.size - 1) {
            return
        }
        // 一次扩容1.5倍
        val newArr = arrayOfNulls<Int>(arr.size + (arr.size shr 1))
        // 从0开始
        if (head < tail) {
            for (i in head..<tail) {
                newArr[i - head] = arr[i]
            }
        } else {
            // 临时下标
            var index = 0
            // 现存头部
            for (i in head..arr.lastIndex) {
                newArr[index++] = arr[i]
            }
            // 尾部移动后面
            for (i in 0..<tail) {
                newArr[index++] = arr[i]
            }
        }
        // 扩容后，head和tail重新计算
        arr = newArr
        head = 0
        tail = size
    }

    fun size() = size
    fun isEmpty() = size() == 0

    fun isNotEmpty() = size() > 0

    override fun toString(): String {
        if (size == 0) {
            return ""
        }
        val sb = StringBuilder()
        if (head < tail) {
            for (i in head..<tail) {
                if (sb.isNotEmpty()) {
                    sb.append(", ")
                }
                sb.append(arr[i])
            }
        } else {
            for (i in head..arr.lastIndex) {
                if (sb.isNotEmpty()) {
                    sb.append(", ")
                }
                sb.append(arr[i])
            }
            for (i in 0..<tail) {
                // 此时一定有至少一个元素，不用判断
                sb.append(", ").append(arr[i])
            }
        }
        return sb.toString()
    }
}
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