循环队列

队列，先进先出(FIFO)数据结构。常规理解是：队头出，整体前移，然后队尾再加入。数组简单实现会有整体拷贝问题，可以用循环队列方式实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


class TheQueue(size: Int) {
    //不支持指针，用取模方式实现循环，+1与实际size匹配
    private var array = Array(size + 1) { 0 }
    private var inIndex: Int = 0
    private var outIndex: Int = 0

    fun put(data: Int): Boolean {
        if ((inIndex + 1) % array.size == outIndex) {
            println("队列满了~")
            return false
        }
        array[inIndex] = data
        inIndex = (inIndex + 1) % array.size

        return true
    }

    fun isEmpty(): Boolean {
        return inIndex == outIndex
    }

    fun get(): Int {
        if (isEmpty()) {
            throw Exception("队列空了~")
        }

        val tmp = array[outIndex]
        outIndex = (outIndex + 1) % array.size

        return tmp
    }

    fun printQueue() {
        var i = outIndex
        while (i != inIndex) {
            print("${array[i]},")
            i = (i + 1) % array.size
        }
        println()
    }
}