栈(Stack)
- Last In First Out(LIFO) 后进先出
- 栈也是一种线性数据结构
代码实现栈
考虑到需要扩容，所以我们使用ArrayList最为底层的动态数组支持。
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() } }
栈的应用
- 常见的 Undo 操作，即撤销操作(ctrl+z,command+z 类似)
- 程序调用所使用的系统栈
比如我们在开发中常见的方法栈，即在 A方法中去调用B方法，B方法再去调用C方法。类似下面这样的代码,都是通过上次的中断位置找到接下来应该执行的位置继续执行。
需要注意的是每个线程都包含一个栈区，实际开发往往涉及多个线程，而我们下述代码只包含了一个线程示例，即主线程。
class StackTest { fun a() { println("Stack-fun-a进入") b() println("Stack-fun-b移除") } private fun b() { println("Stack-fun-b进入") c() println("Stack-fun-c移除") } private fun c() { println("Stack-fun-c进入") } } fun main() { StackTest().a() println("Stack-fun-a移除") }
Stack-fun-a进入 Stack-fun-b进入 Stack-fun-c进入 Stack-fun-c移除 Stack-fun-b移除 Stack-fun-a移除
队列(Queue)
- 队列也是一种线性结构
- 相比数组，队列对应的操作是数组的子集
- 只能从一端(队尾)添加元素，从另一端(队首取出元素)
- 队列是一种先进先出的数据结构。也可以理解为先到先得，类似为排队办理某个业务
- First In First Out (FIFO) 先进先出
代码实现队列(数组队列)
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 } }
循环队列
虽然我们上面实现了普通队列，但是普通的队列也有存在性能问题，比如当我们移除队首元素时，算法复杂度为O(n),这是我们不能接受的。
要改掉上面的问题，首先思考🤔，我们需要什么？
当删除队首元素时如果直接移动整个队列，效率势必最低，这个时候如何才能不移动队列中元素位置，还能便于下次删除队首时，能准确找到呢？
我们可以增加 两个变量，队首和队尾的下标位置，这样我们只需要每次删除队首时改变 队首当前下标，入队时，改变队尾下标。但是相应的，我们也需要考虑到数组的扩容与相应的缩容,所以我们使用循环队列来解决这个问题。
边界考虑
- 队首和队尾下标相等时则意味着队列为null，即默认状态；
- 需要考虑当前队列的元素个数；
- 扩容与缩容的考虑，当队尾位置与队首相同时，主动扩容，当队列元素小与默认容积时，考虑缩容处理。
代码实现循环队列
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() } }
循环队列和数组队列的比较
相同数据下，如果有移除元素的情况，循环队列的效率显著大于数组队列，因为相应的，数组队列移除元素时，需要移动整个队列元素，而 循环队列只需要更新队首元素位置，但是我们也需要考虑缩容情况，不过这种情况相比数组队列，效率也是提升巨大。即 O(1)||平摊----O(n)
栈与队列相同点
- 都是线性数据结构
- 底层都依靠数组，依靠 resize(扩容) 解决固定容量问题
