数据结构 | 使用Kotlin实现栈与队列

interface Stack<E> {
  	//获取栈的大小
    fun getSize(): Int
  	//栈是否为null
    fun isEmpty(): Boolean
  	//出栈
    fun pop(): E
  	//获取栈尾元素
    fun peek(): E
}

class ArrayStack<E>(private val capacity: Int = 10) : Stack<E> {
    
    private val array = ArrayList<E>(capacity)

    override fun getSize(): Int {
        return array.size
    }

    override fun isEmpty(): Boolean {
        return array.isEmpty()
    }
		
    override fun pop(): E {
        return array.removeLast()
    }

    override fun peek(): E {
        return array[getSize() - 1]
    }

    fun getCapacity(): Int {
        return capacity
    }

    fun push(e: E) {
        array.add(e)
    }

    override fun toString(): String {
        val res = StringBuilder("Stack:")
        res.append("Stack：").append("[")
        if (array.isNotEmpty()) {
            array.forEach {
                res.append("$it,")
            }
            res.deleteCharAt(res.length - 1)
        }
        res.append("] top ")
        return res.toString()
    }
}

interface Queue<E> {
    fun enqueue(e: E)   //复杂度 O(1)
 		
  	/** 移除队首元素 */
    fun dequeue(): E   //复杂度 O(n)
		/** 获取队首元素 */
    fun getFront(): E   //复杂度 O(1)
		/** 获取队列大小 */
    fun getSize(): Int  //复杂度 O(1)
		/** 判断队列是否为null */
    fun isEmpty(): Boolean  //复杂度 O(1)
}

class ArrayQueue<E>(private val initialCapacity) : Queue<E> {

    private var array = ArrayList<E>(initialCapacity)

    override fun enqueue(e: E) {
        array.add(e)
    }

    
    override fun dequeue(): E {
        return array.removeFirst()
    }

    
    override fun getFront(): E {
        return array.first()
    }

    override fun getSize(): Int {
        return array.size
    }

    override fun isEmpty(): Boolean {
        return array.isEmpty()
    }

    override fun toString(): String {
        val res = StringBuilder()
        res.append("Queue：")
        res.append("front [")
        if (array.isNotEmpty()) {
            array.forEach {
                res.append(it)
                res.append(",")
            }
            res.deleteCharAt(res.length - 1);
        }
        res.append("] tail")
        return res.toString()
    }

    fun getCapacity(): Int {
        return initialCapacity
    }
}

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