設計一個環形佇列（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
TIP
核心思路：用陣列加上頭尾指針模擬環形結構，或用鏈結串列維護首尾節點。
- 環形佇列的核心是固定容量下的 FIFO 操作
- 陣列實作：用 head 和 count 管理，index 取餘數實現環繞
- 鏈結串列實作：維護 head、tail 指針和 size
Approaches
1. Array-based — O(1) / O(k)
- Idea: 用固定大小陣列，head 指向隊首，透過 count 和取餘數管理環繞
- Time: 所有操作
O(1) - Space:
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 — O(1) / O(k)
- Idea: 使用單向鏈結串列，維護 head 和 tail 指針以及 size 和 capacity
- Time: 所有操作
O(1) - Space:
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: 環形佇列是基礎資料結構，陣列版本用取餘數實現環繞，鏈結串列版本用頭尾指針管理
- Key trick: 陣列版本用 count 而非 head/tail 雙指針可以避免「滿」和「空」難以區分的經典問題