|
5 | 5 |
|
6 | 6 | ## 题目大意
|
7 | 7 |
|
8 |
| -要求:设计实现一个循环队列,支持一下操作: |
| 8 | +**要求**:设计实现一个循环队列,支持以下操作: |
9 | 9 |
|
10 | 10 | - `MyCircularQueue(k)`: 构造器,设置队列长度为 `k`。
|
11 | 11 | - `Front`: 从队首获取元素。如果队列为空,返回 `-1`。
|
|
15 | 15 | - `isEmpty()`: 检查循环队列是否为空。
|
16 | 16 | - `isFull()`: 检查循环队列是否已满。
|
17 | 17 |
|
| 18 | +**说明**: |
| 19 | + |
| 20 | +- 所有的值都在 `0` 至 `1000` 的范围内。 |
| 21 | +- 操作数将在 `1` 至 `1000` 的范围内。 |
| 22 | +- 请不要使用内置的队列库。 |
| 23 | + |
| 24 | +**示例**: |
| 25 | + |
| 26 | +```Python |
| 27 | +MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 |
| 28 | +circularQueue.enQueue(1); // 返回 true |
| 29 | +circularQueue.enQueue(2); // 返回 true |
| 30 | +circularQueue.enQueue(3); // 返回 true |
| 31 | +circularQueue.enQueue(4); // 返回 false,队列已满 |
| 32 | +circularQueue.Rear(); // 返回 3 |
| 33 | +circularQueue.isFull(); // 返回 true |
| 34 | +circularQueue.deQueue(); // 返回 true |
| 35 | +circularQueue.enQueue(4); // 返回 true |
| 36 | +circularQueue.Rear(); // 返回 4 |
| 37 | +``` |
| 38 | + |
18 | 39 | ## 解题思路
|
19 | 40 |
|
20 |
| -这道题可以使用数组,也可以使用链表来实现循环队列。以数组为例,建立一个容量为 `k + 1` 的数组 `queue`。并保存队头指针 `front`、队尾指针 `rear`,队列容量 `capacity` 为 `k + 1`。这里之所以用了 `k + 1` 的容量,是为了判断空和满,需要空出一个。 |
| 41 | +这道题可以使用数组,也可以使用链表来实现循环队列。 |
21 | 42 |
|
22 |
| -## 代码 |
| 43 | +### 思路 1:使用数组模拟 |
| 44 | + |
| 45 | +建立一个容量为 `k + 1` 的数组 `queue`。并保存队头指针 `front`、队尾指针 `rear`,队列容量 `capacity` 为 `k + 1`(这里之所以用了 `k + 1` 的容量,是为了判断空和满,需要空出一个)。 |
| 46 | + |
| 47 | +然后实现循环队列的各个接口: |
| 48 | + |
| 49 | +1. `MyCircularQueue(k)`: |
| 50 | + 1. 将数组 `queue` 初始化大小为 `k + 1` 的数组。 |
| 51 | + 2. `front`、`rear` 初始化为 `0`。 |
| 52 | +2. `Front`: |
| 53 | + 1. 先检测队列是否为空。如果队列为空,返回 `-1`。 |
| 54 | + 2. 如果不为空,则返回队头元素。 |
| 55 | +3. `Rear`: |
| 56 | + 1. 先检测队列是否为空。如果队列为空,返回 `-1`。 |
| 57 | + 2. 如果不为空,则返回队尾元素。 |
| 58 | +4. `enQueue(value)`: |
| 59 | + 1. 如果队列已满,则无法插入,返回 `False`。 |
| 60 | + 2. 如果队列未满,则将队尾指针 `rear` 向右循环移动一位,并进行插入操作。然后返回 `True`。 |
| 61 | +5. `deQueue()`: |
| 62 | + 1. 如果队列为空,则无法删除,返回 `False`。 |
| 63 | + 2. 如果队列不空,则将队头指针 `front` 指向元素赋值为 `None`,并将 `front` 向右循环移动一位。然后返回 `True`。 |
| 64 | +6. `isEmpty()`: 如果 `rear` 等于 `front`,则说明队列为空,返回 `True`。否则,队列不为空,返回 `False`。 |
| 65 | +7. `isFull()`: 如果 `(rear + 1) % capacity` 等于 `front`,则说明队列已满,返回 `True`。否则,队列未满,返回 `False`。 |
| 66 | + |
| 67 | +### 思路 1:代码 |
23 | 68 |
|
24 | 69 | ```Python
|
25 | 70 | class MyCircularQueue:
|
26 | 71 |
|
27 | 72 | def __init__(self, k: int):
|
28 | 73 | self.capacity = k + 1
|
29 |
| - self.queue = [0 for _ in range(k+1)] |
| 74 | + self.queue = [0 for _ in range(k + 1)] |
30 | 75 | self.front = 0
|
31 | 76 | self.rear = 0
|
32 | 77 |
|
@@ -60,3 +105,8 @@ class MyCircularQueue:
|
60 | 105 | return (self.rear + 1) % self.capacity == self.front
|
61 | 106 | ```
|
62 | 107 |
|
| 108 | +### 思路 1:复杂度分析 |
| 109 | + |
| 110 | +- **时间复杂度**:$O(1)$。初始化和每项操作的时间复杂度均为 $O(1)$。 |
| 111 | +- **空间复杂度**:$O(k)$。其中 $k$ 为给定队列的元素数目。 |
| 112 | + |
0 commit comments