网站内怎么做搜索,微网站开发入门,网站是asp还是php,爱网站推广优化Deque双端队列#xff0c;一直在使用#xff0c;却从未了解过源码。 内部逻辑其实很简单
可扩容数组循环队列#xff0c;循环栈扩容倍数1.5#xff0c;sizesize(size shr 1)只从两端存取元素
fun main() {val deque MyArrayDeque()repeat(16) {deque.addLast(it)}while …Deque双端队列一直在使用却从未了解过源码。 内部逻辑其实很简单
可扩容数组循环队列循环栈扩容倍数1.5sizesize(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 arrayOfNullsInt(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 arrayOfNullsInt(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()}
}
