重学数据结构-栈与队列

image.png

栈(Stack)

• Last In First Out(LIFO) 后进先出
• 栈也是一种线性数据结构

image-20200822100456400

代码实现栈

考虑到需要扩容，所以我们使用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)

image-20200825142900859

• 队列也是一种线性结构
• 相比数组，队列对应的操作是数组的子集
• 只能从一端(队尾)添加元素，从另一端(队首取出元素)
• 队列是一种先进先出的数据结构。也可以理解为先到先得，类似为排队办理某个业务
• 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(扩容) 解决固定容量问题

参考视频：慕课网liuyubobobo

我是 Petterp ,如果你觉得我的文章对你有所帮助，欢迎点赞👏 ，如果有任何想法和问题，随时欢迎评论区一起讨论。👨‍💻‍