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()
    }
}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>