最近在刷leetcode的时候，突然发现有一些算法需要使用到队列和栈。
我本想着这东西并不是很难，但是认真考究一下，发现在kotlin中，并没有对于栈和队列的直接实现，而只有基础的数组和集合。
尽管他有很多的语法糖，包括removeFirst(),removeLast()，之类，使其可以轻松的实现队列和栈才能完成的功能。
但是对于removeFirst方法他是如何实现的呢？

removeFirst

在这里先提出两种推测，

  1. 他使用的是基于数组的形式实现。那么他完成removeFirst只能通过创建一个新的数组然后对原数组进行完整的遍历。这样子时间复杂度为O(n)，效率将会很低。
  2. 他使用基于链表的形式，使每一个数组中的对象通过next连接，这样子，他完成removeFirst的话,他的时间复杂度只是O(1)。
    我并不能确定kotlin底层是否自动的帮我们基于不同的功能实现了不同类型的集合对象。像是java中的ArrayList，LinkedList。那么他的效率应该可以实现最优。于是我做了个测试
    刚开始设置数组容量为100000时，他们相差不大

    可是当我把数组容量提高100倍。

    他的效率显著的下降了。
    因此可以验证出，他是基于第一种方法，他完成removeFirst时，会对整个数组进行一次遍历。他的效率会非常低。而在kotlin中并没有LinkedList这样子的一个集合方法。所以在某种程度上要实现一个队列的话，他的效率会非常受影响。因此这里有一种采取循环队列的方式来实现高效的removeFirst方法。

    这后面的内容引用自这里

    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
    class LoopQueue<E : Any>(private val capacity: Int = 10) : Queue<E?> {

        var data = arrayOfNulls<Any>(capacity + 1) as Array<E?>
        //队首下标
        private var front = 0
        //队尾下标
        private var tail = 0
        //当前数据长度
        private var size = 0
        //实际容量位置
        private var arraySize = data.size

        override fun enqueue(e: E?) {
            //大于数组长度，扩容
            if ((tail + 1) % arraySize == front) {
                resize(capacity * 2)
            }
            arraySize = data.size
            //入队
            data[tail] = e
            //确定队尾位置
            tail = (tail + 1) % arraySize
            //增加数据长度
            ++size
        }

        private fun resize(newCapacity: Int) {
            //扩容大小为传入容量+1，因为我们一定会浪费一个空间
            val newData = arrayOfNulls<Any>(newCapacity + 1) as Array<E?>
            //先确定当前容量大小
            arraySize = data.size
            //遍历旧数据源，存入新数组
            
            // it+front原因很简单，从 原队首 位置开始遍历相加
            (0..size).forEach {
                newData[it] = data[(it + front) % arraySize]
            }
            data = newData
            //新队首位置为0
            front = 0
            //新队尾位置为原数组的长度
            tail = size
        }

        override fun dequeue(): E? {
          	//容错判断
            if (isEmpty()) throw IllegalArgumentException("队列为null")
          	//拿到队首位置
            val ret = data[front]
            data[front] = null
          	//移动队首位置
            front = (front + 1) % arraySize
            --size
            //缩容 
            if (size == capacity / 4 && capacity / 2 != 0) resize(capacity / 2)
            return ret
        }


        override fun getFront(): E? {
            if (isEmpty()) throw IllegalArgumentException("队列为null")
            return data[front]
        }

        override fun getSize(): Int {
            return size
        }

        override fun isEmpty(): Boolean {
            return front == tail
        }

        override fun toString(): String {
            val res = StringBuilder().append("Queue：").append("front [")
            if (!isEmpty()) {
                //数据打印除重
                data.filterNotNull().forEach {
                    res.append(it).append(",")
                }
                res.deleteCharAt(res.length - 1);
            }
            res.append("] tail")
            return res.toString()
        }
    }