622.design-circular-queue.md

622. Design Circular Queue

We can use a static array to implement a circular queue.

• front is the actual front position.
• rear is the actual rear position of the queue.
• size is the number of elements in the queue.

Some solutions have the different definition of front and rear, some use next position, please mind the difference and the timing to update front and rear while enqueue and dequeue.

• 定义循环变量 front 和 rear 。一直保持这个定义，到底是先赋值还是先移动指针就很容易想清楚了。

For this kind of problem, always have a very clear definition of the pointers:

• Pointer to actual element (In our implementation)
• Pointer to next position
• Hybrid of the two

Pointer	Meaning	Why this init?
front = 0	First element will go here	Safe default; front doesn't move until dequeue
rear = -1	No element inserted yet	After first insert, rear = 0

class MyCircularQueue(k: Int) {

    private val arrays = IntArray(k)
    private var front = 0
    private var rear = -1
    private var size = 0
    
    fun enQueue(value: Int): Boolean {
        if (isFull()) return false
        rear = (rear + 1) % arrays.size
        // Or we can rotate the pointer to the beginning
        // rear++
        // if (rear >= k) rear = 0
        arrays[rear] = value
        size++
        return true
    }

    fun deQueue(): Boolean {
        if (isEmpty()) return false
        front = (front + 1) % arrays.size
        // Or we can rotate the pointer
        // front++
        // if (front >= k) front = 0
        size--
        return true
    }

    fun Front(): Int {
        if (isEmpty()) return -1
        return arrays[front]
    }

    fun Rear(): Int {
        if (isEmpty()) return -1
        return arrays[rear]
    }

    fun isEmpty(): Boolean {
        return size == 0
    }

    fun isFull(): Boolean {
        return size == arrays.size
    }
}

Or we can derive rear from front + size in static array so that we don't have to maintain rear property:

class MyCircularQueue(k: Int) {

    private val arrays = IntArray(k)
    private var front = 0
    private var size = 0
    
    fun enQueue(value: Int): Boolean {
        if (isFull()) return false
        arrays[(front + size) % size] = value
        size++
        return true
    }

    fun deQueue(): Boolean {
        if (isEmpty()) return false
        front = (front + 1) % arrays.size
        size--
        return true
    }

    fun Front(): Int {
        if (isEmpty()) return -1
        return arrays[front]
    }

    fun Rear(): Int {
        if (isEmpty()) return -1
        return arrays[(front + size - 1) % size]
    }

    fun isEmpty(): Boolean {
        return size == 0
    }

    fun isFull(): Boolean {
        return size == arrays.size
    }
}

Edge Cases

• Call Front() or Rear() when queue is empty.
• Call enQueue() when queue is full.
• Call deQueue() when queue is empty.