kotlin实现ArrayDeque

2023-10-12 05:52

文章标签 实现 kotlin arraydeque

本文主要是介绍kotlin实现ArrayDeque，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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一直为nullprivate var head: Int = 0private var tail: Int = 0// 实际容量private var size: Int = 0fun addFirst(value: Int) {// 扩容grow()head = dec(head)arr[head] = valuesize++}fun addLast(value: Int) {// 扩容grow()arr[tail] = valuetail = 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 = newArrhead = 0tail = size}fun size() = sizefun isEmpty() = size() == 0fun isNotEmpty() = size() > 0override 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()}
}