622. 设计循环队列.md

622. 设计循环队列

题目传送门

点击这里

解题思路

要明确循环队列的定义，这里用百度百科的话来说明，循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。在循环队列中，当队列为空时，有front = rear，而当所有队列空间全占满时，也有front = rear。为了区别这两种情况，规定循环队列最多只能有capacity-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front = rear，而队列判满的条件是front = (rear+1) % capacity。对于一个固定大小的数组，只要知道队尾和队首，就可以计算出队列当前的长度(rear−front+capacity) % capacity。这里要注意一点，虽然我们表达式说明的front = rear，但其实二者表达的意义并不一样，front表达的是队列首元素对应的数组索引，rear表达的是队列尾元素对应的索引的下一个索引。

代码

type MyCircularQueue struct {
    front, rear int // 首尾
	elements  []int // 保存循环队列内元素
}


func Constructor(k int) MyCircularQueue {
    return MyCircularQueue{elements: make([]int, k+1)}
}


func (this *MyCircularQueue) EnQueue(value int) bool {
    if this.IsFull() {
        return false
    }
    this.elements[this.rear] = value
    this.rear = (this.rear + 1) % len(this.elements) // 向后移动一格
    return true
}


func (this *MyCircularQueue) DeQueue() bool {
    if this.IsEmpty() {
        return false
    }
    this.front = (this.front + 1) % len(this.elements) // 同理，向后移动一格
    return true
}


func (this *MyCircularQueue) Front() int {
    if this.IsEmpty() {
        return -1
    }
    return this.elements[this.front]
}


func (this *MyCircularQueue) Rear() int {
    if this.IsEmpty() {
        return -1
    }
    return this.elements[(this.rear-1+len(this.elements))%len(this.elements)] 
}


func (this *MyCircularQueue) IsEmpty() bool {
    return this.rear == this.front
}


func (this *MyCircularQueue) IsFull() bool {
    return (this.rear+1)%len(this.elements) == this.front
}


/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.EnQueue(value);
 * param_2 := obj.DeQueue();
 * param_3 := obj.Front();
 * param_4 := obj.Rear();
 * param_5 := obj.IsEmpty();
 * param_6 := obj.IsFull();
 */