盒子
盒子
文章目录
  1. Nim 中文编程早茶
    1. 初始化
    2. 测试队列状态
    3. 入队与出队
    4. 测试

Nim 编程实现环形缓冲队列

Nim 中文编程早茶

环形缓冲队列是一种高效的数据结构,具有先进先出的特征,不需要进行动态的内存分配与释放,反复使用固定大小的内存空间。

初始化

环形缓冲队列,使用固定容量的数组 data 作为存储结构。其中 N 的数值就是缓冲队列的容量。head 指向队列的第一个元素,tail 指向队列的最后一个元素之后的内存单元。

使用 newCircularQueue 函数,来构造环形缓冲队列。初始时,headtail 均为 0,插入第一个元素,head 仍为 0, 而 tail 变为 1

1
2
3
4
5
6
7
type
CircularQueue*[N: static[int], T] = object
data: array[N, T]
head, tail: int

proc newCircularQueue*[N: static[int], T](): CircularQueue[N, T] =
discard

测试队列状态

我们需要判断队列的状态,是否处于空队列或者满队列的状态。

如果队列的 |tail-head|=容量,说明队列已经满了,不能继续插入元素。head ..< tail 之间有 tail-head 个元素。

如果队列的 head 等于 tail,说明队列为空,不能继续删除元素。

1
2
3
4
5
func isFull*(q: CircularQueue): bool {.inline.} =
abs(q.tail-q.head) == q.N

func isEmpty*(q: CircularQueue): bool {.inline.} =
q.tail == q.head

入队与出队

在队列不为空的情况,我们可以从队列中弹出元素。我们通过对head 取模,来获得首元素的索引。由于,我们设置 head 的范围是 [0, 2 * N),所以,只需要将 [N, 2 * N) 范围内的 head 减去 N,即可获得对应的下标。

head 达到 2*N 的时候,我们将其归为 0

enQueue 是一样的道理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 释放对弹出元素的所有权
proc deQueue*[N: static[int], T](q:var CircularQueue[N, T]):owned T =
if q.isEmpty:
echo "队列已空"
return
if q.head < q.N:
result = move q.data[q.head]
else:
result = move q.data[q.head-q.N]
q.head += 1
if q.head == 2 * q.N:
q.head = 0

# 只提供首元素的视图
proc peekQueue*[N: static[int], T](q:var CircularQueue[N, T]):lent T =
if q.isEmpty:
echo "队列已空"
return
if q.head < q.N:
result = q.data[q.head]
else:
result = q.data[q.head-q.N]

proc enQueue*[N: static[int], T](q: var CircularQueue[N, T], v: sink T) =
if q.isFull:
echo "队列已满"
return
if q.tail < q.N:
q.data[q.tail] = v
else:
q.data[q.tail-q.N] = v
q.tail += 1
if q.tail == 2 * q.N:
q.tail = 0


proc len*(q: CircularQueue): int {.inline.} =
result = q.tail - q.head
while result < 0:
result += q.N

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var c = newCircularQueue[10, int]()
for i in 1 .. 10:
c.enQueue(i)
echo c
for i in 1 .. 10:
discard c.deQueue
echo c
for i in 1 .. 10:
c.enQueue(i)
echo c
for i in 1 .. 8:
discard c.deQueue
echo c

echo c.peekQueue
echo c.deQueue
echo c.data
echo c.len

输出

1
2
3
4
9
9
[0, 0, 0, 0, 0, 0, 0, 0, 0, 10]
1