622. Design Circular Queue

Medium

Description

設計一個環形佇列（Circular Queue）。實作 MyCircularQueue 類別：enQueue(value) 加入元素、deQueue() 移除元素、Front() 取得前端元素、Rear() 取得後端元素、isEmpty() 和 isFull() 檢查狀態。

Example:

Input: [“MyCircularQueue”,“enQueue”,“enQueue”,“enQueue”,“enQueue”,“Rear”,“isFull”,“deQueue”,“enQueue”,“Rear”], [[3],[1],[2],[3],[4],[],[],[],[4],[]] Output: [null,true,true,true,false,3,true,true,true,4]

Intuition#

核心思路：用陣列加上頭尾指針模擬環形結構，或用鏈結串列維護首尾節點。

環形佇列的核心是固定容量下的 FIFO 操作
陣列實作：用 head 和 count 管理，index 取餘數實現環繞
鏈結串列實作：維護 head、tail 指針和 size

Approaches#

1: Array-based#

概念: 用固定大小陣列，head 指向隊首，透過 count 和取餘數管理環繞
時間複雜度: 所有操作 O(1)
空間複雜度: O(k) - k 為容量

class MyCircularQueue(private val k: Int) {

    private val data = IntArray(k)
    private var head = 0
    private var count = 0

    fun enQueue(value: Int): Boolean {
        if (isFull()) return false
        data[(head + count) % k] = value
        count++
        return true
    }

    fun deQueue(): Boolean {
        if (isEmpty()) return false
        head = (head + 1) % k
        count--
        return true
    }

    fun Front(): Int {
        if (isEmpty()) return -1
        return data[head]
    }

    fun Rear(): Int {
        if (isEmpty()) return -1
        return data[(head + count - 1) % k]
    }

    fun isEmpty(): Boolean = count == 0

    fun isFull(): Boolean = count == k
}

⭐2: Linked List-based#

概念: 使用單向鏈結串列，維護 head 和 tail 指針以及 size 和 capacity
時間複雜度: 所有操作 O(1)
空間複雜度: O(k)

class MyCircularQueue(private val k: Int) {

    private class Node(val `val`: Int, var next: Node? = null)

    private var head: Node? = null
    private var tail: Node? = null
    private var size = 0

    fun enQueue(value: Int): Boolean {
        if (isFull()) return false
        val node = Node(value)
        if (isEmpty()) {
            head = node
            tail = node
        } else {
            tail?.next = node
            tail = node
        }
        size++
        return true
    }

    fun deQueue(): Boolean {
        if (isEmpty()) return false
        head = head?.next
        if (head == null) tail = null
        size--
        return true
    }

    fun Front(): Int {
        if (isEmpty()) return -1
        return head!!.`val`
    }

    fun Rear(): Int {
        if (isEmpty()) return -1
        return tail!!.`val`
    }

    fun isEmpty(): Boolean = size == 0

    fun isFull(): Boolean = size == k
}

🔑 Takeaways#

Pattern: 環形佇列是基礎資料結構，陣列版本用取餘數實現環繞，鏈結串列版本用頭尾指針管理
關鍵技巧: 陣列版本用 count 而非 head/tail 雙指針可以避免「滿」和「空」難以區分的經典問題