如何在Kotlin中实现环形数组或环形栈？

环形栈通过复用数组存储空间，避免普通栈频繁扩容带来的性能损耗，Kotlin官方库没有提供现成实现，以下是一个可直接使用的封装：

class CircularStack<T>(initialCapacity: Int = 8) {
    private var elements: Array<Any?> = arrayOfNulls(initialCapacity)
    private var top = -1
    private var size = 0

    // 判断栈是否为空
    fun isEmpty(): Boolean = size == 0

    // 判断栈是否已满
    fun isFull(): Boolean = size == elements.size

    // 获取栈顶元素（不移除）
    fun peek(): T? {
        if (isEmpty()) return null
        @Suppress("UNCHECKED_CAST")
        return elements[top] as T
    }

    // 入栈操作
    fun push(item: T) {
        if (isFull()) {
            // 栈满时扩容为原容量的2倍
            val newCapacity = elements.size * 2
            val newElements = arrayOfNulls<Any?>(newCapacity)
            // 复制原有元素到新数组
            for (i in elements.indices) {
                newElements[i] = elements[(top + 1 + i) % elements.size]
            }
            elements = newElements
            top = size - 1
        }
        top = (top + 1) % elements.size
        elements[top] = item
        size++
    }

    // 出栈操作
    fun pop(): T? {
        if (isEmpty()) return null
        @Suppress("UNCHECKED_CAST")
        val item = elements[top] as T
        elements[top] = null // 避免内存泄漏
        top = (top - 1 + elements.size) % elements.size
        size--
        return item
    }

    // 获取栈内元素数量
    fun size(): Int = size
}

关键实现说明 #

• 环形空间复用：通过取模运算(top + 1) % elements.size计算新栈顶位置，(top - 1 + elements.size) % elements.size更新出栈后的栈顶，实现数组空间循环利用
• 动态扩容：当栈满时自动将容量翻倍，同时按顺序复制原有元素到新数组，保证数据连续性
• 安全边界处理：所有读写操作前先判断栈空/栈满状态，避免数组越界异常

使用示例 #

fun main() {
    val stack = CircularStack<String>()
    stack.push("Kotlin")
    stack.push("Circular")
    stack.push("Stack")

    println(stack.peek()) // 输出: Stack
    println(stack.pop())  // 输出: Stack
    println(stack.size()) // 输出: 2
    println(stack.isEmpty()) // 输出: false
}

内容的提问来源于stack exchange，提问作者Michael Muzicenko