设计循环队列（leetcode 622）

1.问题描述

设计一个循环队列。

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为环形缓冲器（Ringr Buffer）。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(n)：构造器，设置队列长度为 k 。
Front：从队首获取元素。如果队列为空，返回 -1 。
Rear：获取队尾元素。如果队列为空，返回 -1 。
enQueue(value)：向循环队列插入一个元素。如果成功插入则返回真。
deQueue()：从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty()：检查循环队列是否为空。
isFull()：检查循环队列是否已满。

2.难度等级

medium。

3.热门指数

★★★★☆

出题公司：腾讯、微派网络。

4.解题思路

我们可以通过一个数组进行模拟，通过操作数组的索引构建一个虚拟的首尾相连的环。在循环队列结构中，设置一个队尾 rear 与队首 front，且大小固定，结构如下图所示：

当队列满时，rear 与 front 相邻，即 (rear + 1) % k = front。

当队列空时，rear 等于 front，但是当只有一个元素时，rear 也等于 front。为了区分这种情况，所以我们引入一个长度属性来记录队列中的元素数量。

循环队列的属性如下:

elements：一个固定大小的数组，用于保存循环队列的元素。
front：队列首元素对应的数组索引。
rear：队列尾元素对应的数组索引。
len：队列长度，即队列中的元素个数。
capacity：队列容量，即队列中最多可以容纳的元素数量。

循环队列的方法如下：

• MyCircularQueue(int k) 初始化队列，同时数组的空间初始化为 k。front、rear、len 全部初始化为 0，capacity 初始化为 k。
• enQueue(int value) 将队尾的索引 rear 更新为 (rear+1) mod capacity，然后在队列的尾部插入一个元素。注意当队列为空时 rear 不需要移动。
• deQueue()：从队首取出一个元素，并同时将队首的索引 front 更新为 (front + 1) mod capacity。注意当队列长度为 1 时 front 不需要移动。
• Front()：返回队首的元素，需要检测队列是否为空。
• Rear()：返回队尾的元素，需要检测队列是否为空。
• isEmpty()：队列长度 len 为 0 表示空。
• isFull()：队列长度 len 等于队列容量 capacity 表示队列已满。也可以根据 (rear + 1) mod capacity 等于 front 来判断。

当然也可以使用链表来实现，过程类似。

5.实现示例

5.1 C++

class MyCircularQueue {
    int front, rear;
    vector<int> elements;
    int len, capacity;
public:
    MyCircularQueue(int k) {
        front = rear = 0;
        len = 0;
        capacity = k;
        elements = vector<int>(k);
    }
    
    bool enQueue(int value) {
        if (len==capacity) {
            return false;
        }
        // 如果队列为空，rear 等于 front 且 rear 不需要移动。
        if (len > 0) {
            rear = (rear+1) % capacity;
        }
        elements[rear] = value;
        len++;
        return true;
    }
    
    bool deQueue() {
        if (len==0) {
            return false;
        }
        elements[front] = 0;
        // 如果队列长度为 1，front 等于 rear 且 front 不需要移动。
        if (len > 1) {
            front = (front+1) % capacity;
        }
        len--;
        return true;
    }
    
    int Front() {
        if (len > 0) {
            return elements[front];
        }
        return -1;
    }
    
    int Rear() {
        if (len > 0) {
            return elements[rear];
        }
        return -1;
    }
    
    bool isEmpty() {
        return len == 0;
    }
    
    bool isFull() {
        return len == capacity;
    }
};

5.2 Golang

type MyCircularQueue struct {
    front, rear int
    elements    []int
    len, capacity int
}

func Constructor(k int) MyCircularQueue {
    return MyCircularQueue{
        front:0,
        rear:0,
        elements: make([]int, k),
        len:0,
        capacity:k,
    }
}

func (q *MyCircularQueue) EnQueue(value int) bool {
    if q.len == q.capacity {
        return false
    }
    // 如果队列为空，rear 等于 front 且 rear 不需要移动。
    if q.len > 0 { 
        q.rear = (q.rear + 1) % q.capacity
    }
    q.elements[q.rear] = value
    q.len++
    return true
}

func (q *MyCircularQueue) DeQueue() bool {
    if q.len == 0 {
        return false
    }
    q.elements[q.front] = 0
    // 如果队列长度为 1，front 等于 rear 且 front 不需要移动。
    if q.len > 1 {
        q.front = (q.front + 1) % q.capacity
    }
    q.len--
    return true
}

func (q *MyCircularQueue) Front() int {
    if q.len > 0 {
        return q.elements[q.front]
    }
    return -1
}

func (q *MyCircularQueue) Rear() int {
    if q.len > 0 {
    	q.elements[q.rear]
    }
    return -1
}

func (q *MyCircularQueue) IsEmpty() bool {
    return q.len == 0
}

func (q *MyCircularQueue) IsFull() bool {
    return q.len == q.capacity
}

---

参考文献

622. 设计循环队列 - leetcode