622. 设计循环队列

Medium

题目描述

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

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

实现 MyCircularQueue 类:

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

注意：不要使用内置的队列库。

示例 1：

输入：
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出：
[null, true, true, true, false, 3, true, true, true, 4]

解释：
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // 返回 True
myCircularQueue.enQueue(2); // 返回 True  
myCircularQueue.enQueue(3); // 返回 True
myCircularQueue.enQueue(4); // 返回 False
myCircularQueue.Rear();     // 返回 3
myCircularQueue.isFull();   // 返回 True
myCircularQueue.deQueue();  // 返回 True
myCircularQueue.enQueue(4); // 返回 True
myCircularQueue.Rear();     // 返回 4

提示：

1 <= k <= 1000
0 <= value <= 1000
enQueue, deQueue, Front, Rear, isEmpty, isFull 这些函数最多被调用 3000 次。

解题思路

循环队列的实现有两种常见方案：

方案一：使用数组 + 双指针 使用固定大小的数组，通过 front 和 rear 两个指针来维护队列的头尾位置。关键在于如何区分队列为空和队列为满的状态。

方案二：使用数组 + 计数器 同样使用数组和指针，但额外维护一个 count 变量记录当前元素个数，这样可以更直观地判断队列状态。

推荐方案二，因为逻辑更清晰，不需要"浪费"一个存储位置。

核心思想：

使用大小为 k 的数组存储数据
front 指向队首元素，rear 指向队尾元素的下一个位置
使用 count 记录当前元素个数
所有指针移动都使用取模运算实现循环效果

操作实现：

入队：检查是否已满，在 rear 位置插入元素，rear 向后移动，count++
出队：检查是否为空，front 向后移动，count--
获取队首/队尾：直接访问对应位置
判空/判满：通过 count 与 0 和 k 比较

时间复杂度：所有操作均为 O(1) 空间复杂度：O(k)，需要 k 大小的数组存储数据

代码实现

class MyCircularQueue {
private:
    vector<int> data;
    int front;
    int rear;
    int count;
    int capacity;
    
public:
    MyCircularQueue(int k) {
        data.resize(k);
        front = 0;
        rear = 0;
        count = 0;
        capacity = k;
    }
    
    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        data[rear] = value;
        rear = (rear + 1) % capacity;
        count++;
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        count--;
        return true;
    }
    
    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[front];
    }
    
    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return data[(rear - 1 + capacity) % capacity];
    }
    
    bool isEmpty() {
        return count == 0;
    }
    
    bool isFull() {
        return count == capacity;
    }
};

class MyCircularQueue:

    def __init__(self, k: int):
        self.data = [0] * k
        self.front = 0
        self.rear = 0
        self.count = 0
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.count -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[self.front]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[(self.rear - 1 + self.capacity) % self.capacity]

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.capacity

public class MyCircularQueue {
    private int[] data;
    private int front;
    private int rear;
    private int count;
    private int capacity;

    public MyCircularQueue(int k) {
        data = new int[k];
        front = 0;
        rear = 0;
        count = 0;
        capacity = k;
    }
    
    public bool EnQueue(int value) {
        if (IsFull()) {
            return false;
        }
        data[rear] = value;
        rear = (rear + 1) % capacity;
        count++;
        return true;
    }
    
    public bool DeQueue() {
        if (IsEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        count--;
        return true;
    }
    
    public int Front() {
        if (IsEmpty()) {
            return -1;
        }
        return data[front];
    }
    
    public int Rear() {
        if (IsEmpty()) {
            return -1;
        }
        return data[(rear - 1 + capacity) % capacity];
    }
    
    public bool IsEmpty() {
        return count == 0;
    }
    
    public bool IsFull() {
        return count == capacity;
    }
}

var MyCircularQueue = function(k) {
    this.queue = new Array(k);
    this.head = -1;
    this.tail = -1;
    this.size = k;
};

MyCircularQueue.prototype.enQueue = function(value) {
    if (this.isFull()) {
        return false;
    }
    if (this.isEmpty()) {
        this.head = 0;
    }
    this.tail = (this.tail + 1) % this.size;
    this.queue[this.tail] = value;
    return true;
};

MyCircularQueue.prototype.deQueue = function() {
    if (this.isEmpty()) {
        return false;
    }
    if (this.head === this.tail) {
        this.head = -1;
        this.tail = -1;
    } else {
        this.head = (this.head + 1) % this.size;
    }
    return true;
};

MyCircularQueue.prototype.Front = function() {
    if (this.isEmpty()) {
        return -1;
    }
    return this.queue[this.head];
};

MyCircularQueue.prototype.Rear = function() {
    if (this.isEmpty()) {
        return -1;
    }
    return this.queue[this.tail];
};

MyCircularQueue.prototype.isEmpty = function() {
    return this.head === -1;
};

MyCircularQueue.prototype.isFull = function() {
    return !this.isEmpty() && (this.tail + 1) % this.size === this.head;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构造函数	O(1)	O(k)
enQueue	O(1)	O(1)
deQueue	O(1)	O(1)
Front	O(1)	O(1)
Rear	O(1)	O(1)
isEmpty	O(1)	O(1)
isFull	O(1)	O(1)

总体复杂度：

时间复杂度： 所有操作均为 O(1)
空间复杂度： O(k)，需要大小为 k 的数组存储数据

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

解题思路

代码实现

复杂度分析

相关题目