Skip to content

Commit 0ce1f51

Browse files
committed
Update 0622. 设计循环队列.md
1 parent e51d642 commit 0ce1f51

File tree

1 file changed

+54
-4
lines changed

1 file changed

+54
-4
lines changed

Solutions/0622. 设计循环队列.md

Lines changed: 54 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55

66
## 题目大意
77

8-
要求:设计实现一个循环队列,支持一下操作
8+
**要求**:设计实现一个循环队列,支持以下操作
99

1010
- `MyCircularQueue(k)`: 构造器,设置队列长度为 `k`
1111
- `Front`: 从队首获取元素。如果队列为空,返回 `-1`
@@ -15,18 +15,63 @@
1515
- `isEmpty()`: 检查循环队列是否为空。
1616
- `isFull()`: 检查循环队列是否已满。
1717

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+
1839
## 解题思路
1940

20-
这道题可以使用数组,也可以使用链表来实现循环队列。以数组为例,建立一个容量为 `k + 1` 的数组 `queue`。并保存队头指针 `front`、队尾指针 `rear`,队列容量 `capacity``k + 1`。这里之所以用了 `k + 1` 的容量,是为了判断空和满,需要空出一个。
41+
这道题可以使用数组,也可以使用链表来实现循环队列。
2142

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:代码
2368

2469
```Python
2570
class MyCircularQueue:
2671

2772
def __init__(self, k: int):
2873
self.capacity = k + 1
29-
self.queue = [0 for _ in range(k+1)]
74+
self.queue = [0 for _ in range(k + 1)]
3075
self.front = 0
3176
self.rear = 0
3277

@@ -60,3 +105,8 @@ class MyCircularQueue:
60105
return (self.rear + 1) % self.capacity == self.front
61106
```
62107

108+
### 思路 1:复杂度分析
109+
110+
- **时间复杂度**:$O(1)$。初始化和每项操作的时间复杂度均为 $O(1)$。
111+
- **空间复杂度**:$O(k)$。其中 $k$ 为给定队列的元素数目。
112+

0 commit comments

Comments
 (0)