关于kotlin中的list数组

最近在刷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方法。

   这后面的内容引用自这里

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