队列的几种实现方式

1. 顺序队列

用数组实现的队列叫做顺序队列：

class ArrayQueue<T>(private val n: Int) {

    private val items: Array<T?> = arrayOfNulls<Any>(n) as Array<T?>
    private var head = 0
    private var tail = 0

    fun enqueue(item: T?): Boolean {
        //如果队尾指针已经在数组最后面
        if (tail == n) {
            //此时队列已满
            if (head == 0)
                return false
            //队列未满，我们将数据搬移到数组从 0 开始的位置
            for (pos in head until tail) {
                items[pos - head] = items[pos]
            }
            tail -= head
            head = 0
        }
        items[tail++] = item
        return  true
    }

    fun dequeue(): T? {
        if (head == tail) return null
        return items[head++]
    }

}

出队时间复杂度为 O(1)，但是入队的时间复杂度稍微复杂一点：

• 入队最好情况时间复杂度为 O(1)
• 入队最坏情况时间复杂度为 O(n)
• 入队平均(均摊)时间复杂度为 O(1)

2. 链式队列

用链表实现的队列叫做链式队列：

class LinkedQueue<T> {

    internal class Node<T> (data: T?){
        var item: T? = data
        var next: Node<T>? = null
    }

    private var head: Node<T>? = null
    private var tail: Node<T>? = null

    fun enqueue(item: T?): Boolean {
        val node = Node(item)
        if (tail == null) {
            tail = node
            head = tail
        } else {
            tail?.next = node
            tail = node
        }
        return true
    }

    fun dequeue(): T? {
        if (head == null)
            return null
        val item = head
        head = head?.next
        if (head == null)
            tail = null
        return item?.item
    }

}

与通过数组实现的顺序队列相比，链式队列没有存储空间的限制，但是它比顺序队列需要存储额外的指针数据。

3. 循环队列

在前面数组实现的队列当中，当队列队尾指针移动到数组最后时，如果再次进行入队操作，会进行数组的数据搬移操作，这会有性能损耗。如果把数组想象成一个圆环，数组的头与尾相接，那么入队时怎么也不会有数据搬移了。稍微复杂点的就是队空与队满的判断了。

循环队列

上图是一个数组大小为 9 且队满的队列，tail 指针位置不存储数据（标记作用，方便判断队满情况），所以该循环队列实际最多能存储 8 个数据。队空的判断条件仍然是 head == tail，队满的判断条件则是 (tail + 1) % 9 == head。

class CircularQueue<T>(capacity: Int) {

    //循环队列，用一个空的数组空间来指向队尾
    private val n = capacity + 1
    private val items: Array<T?> = arrayOfNulls<Any>(n) as Array<T?>
    private var head = 0
    private var tail = 0

    fun enqueue(item: T?): Boolean {
        if ((tail + 1) % n == head)
            return false
        items[tail] = item
        tail = (tail + 1) % n
        return true
    }

    fun dequeue(): T? {
        if (head == tail) return null
        val item = items[head]
        head = (head + 1) % n
        return item
    }
}

时间复杂度：O(1)
空间复杂度：O(1)