循环队列

Ring_Buffer

今天讲一种数据结构——循环队列，起初是我在想如何解决Stm32单片机串口粘包/拆包的时候想到的，首先讲一下实现的原理

同余

循环队列的空间排序基于模运算。我们首先来认识一些同于的定义和基本性质

定义：同余：给定整数$m\geq 0$，若对整数$a,b$满足$m\mid (a-b)$，则称$a,b$模$m$同余，记作

$$ a\equiv b \mod m $$

例子：$a\equiv b\mod 10$当且仅当存在相同的余数，例如$13$和$23$，有$13-23 = 10$可以整除10.它们的余数是$3$. 当然，我们也把同余叫模运算。接着给出一些性质

命题1：

  • 若$a = qm+r$，则$a\equiv r \mod m$
  • 若$0 \leq r’ < r <m$，则$r \not\equiv r’ \mod m$
  • $a\equiv b\mod m$当且仅当$a,b$具备相同的余数

证明： $a-r = qm$，$m\mid qm$由定义可知$a \equiv r \mod m$

对命题2，$r\equiv r’ \mod m$当且仅当$(r-r’) = qm$，$q\in\mathbb{Z}$。此时$r-r’ > m$，和命题矛盾。

对命题3，设$a = qm+r$ 和 $b = q’m+r’$，其中$0\leq r < m$和$ 0\leq r’ < m$。则$a-b = (q-q’)m+(r-r’)$。那么 $a-b \equiv r- r’\mod m$，若$a\equiv b\mod m$，则$a-b\equiv 0 \mod m \Rightarrow r - r’ = 0 \Rightarrow r = r’$。反之易得。$a\equiv b \mod m \Rightarrow a-b\equiv 0\mod m \Rightarrow r = r’\mod m$

推论1： 给定$m \geq 2$，则每个整数$a \mod m$和$0,1,\cdots,m-1$中的一个数同余。

证明： 利用长除法，则$a \equiv r \mod m$，其中$ 0\leq r < m$，即$r\in \{0,1,\cdots,m-1\}$。中的某个。并且由命题1的2，$r$是唯一存在的。

利用推论1，可知所有$\mod m$余数为1的都有$x\equiv 1 \mod m$。因此只需要根据余数就可以判断数据应该放在哪个位中。

前期所需要的理论知识到这就足够了。

我们讲讲循环队列

循环队列

循环队列一般称为Circular Queue，它将一个队列的首位相连，克服假溢出的情况。循环队列将储存空间的最后一个元素的地址指向第一个元素的地址。形成逻辑上的闭环。和一般的队列不同，当头指针== 尾指针的时候，无法判断是满的还是空的。因为这种情况下，空和满都满足头指针==尾指针的情况。

1
2
3
4
5

1->2->3->4->1 //
和
1->1

所以，第一件事就是让尾指针和头指针之间一定间隔了一个字节，为此我们可以将头字节=尾字节的情况等价于列表为空的状态。那么存在3种情况，一种是空，空队列直接返回即可。若数据的长度小于缓冲区剩余空间的长度，则直接写入数据，如果发生了数据长度 > 剩余空间长度，则我们抛弃最开始的数据，并用现数据长度 - 剩余空间长度的数据去覆盖。

代码如下：首先我们定义节点结构体，它包含3个参数，数据、头字节，还有尾字节，头字节用来标记数据地址的起点，而尾字节用来告诉程序数据在哪里结束。

1
2
3
4
5
6
7
#define MAXSIZE 5 //缓冲区长度，可以随便更改缓冲区大小

typedef struct Node { //创建一个循环队列节点
    int data[MAXSIZE]; //数据长度
    int front; //头节点位置
    int rear; //尾节点位置
} Node;

我们用数组来定义队列。front表示第一个数据在哪，rear表示最后一个数据在哪。而data是一个预设好的用来储存数据的数组。

接着是队列的初始化，一开始说了。空的节点中头节点位置==尾节点位置，他的代码如下：

1
2
3
4
5
6
7

Node* InitQueue(){
    Node* P = (Node*)malloc(sizeof(Node)); //初始化头节点
    P->front = P->rear = 0;
    return P;
}

接着我们需要一些函数，它们用来帮助我们判断队列是否满了，还是说是空的数组，然后是操作数组的函数，入队还有出队。最后是打印整个队列的函数。

首先是判断队列是空/满的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int isEmpty(Node* P){
    if(P-> front == P->rear){

        return 1;
    }
    else{
        return 0;
    }

}


int isFull(Node* P){
    if((P->rear + 1) % MAXSIZE == P->front){
        return 1;
    }else{
        return 0;
    }
}

在isFull函数里面出现了 模运算（符号%）。该符号的出现等价于 x \equiv (P->rear + 1) \mod MAXSIZE。其中 x 待求和(P->rear + 1)模MAXSIZE同余的变量。通过x和推论1即可得到数据应该储存在哪个位中，例如，现在队列已经满了，但是想入队一个新元素，假设缓冲区长度为5，那么我们只能覆盖之前的数据，这个被覆盖的数据位置就是$ 6 = 1 \times 5+1 $，余数为1，也就是第一个数据将被覆盖。其中6是满队列的位置加上新元素的位置。

所以isFull里面的语句if((P->rear + 1) % MAXSIZE == P->front)是一样的说法，若头节点位置在5，缓冲区长度为5，尾节点在1，则我们可以通过mod MAXSIZE立马知道有5+1 /5 余1.也就有头节点==尾节点。可知该队列满了。

接下来，我们写一个入队的函数，它满足两个要求，一是在队列没满的时候，也就是说头指针位置 < 尾指针位置，这时候正常入队，若队满，就可以通过模运算来覆盖旧数据。

1
2
3
4
5
6
7
8
9
10
11
int enQueue(Node* P, int data){
   if(isFull(P)){
        P->data[P->rear ] = data; 
        P->front = (P->front +1) % MAXSIZE;
        P->rear = (P->rear + 1 ) % MAXSIZE;
    } else {
        P->data[P->rear] = data;
        P->rear = (P->rear + 1) % MAXSIZE;

    }
}

若队没满，至少存在2种情况，即

1
2
3
4
5
6

1: |1|2|3|4|...|n|
 *front       *rear

2: |n-1|n|   1|2|...|n-2|
     *rear   *front

也就是发生了间隔和正常入队的情况，很好解决，都只需要 % MAXSIZE即可得到当前指针的位置在哪。

若队满，则将下一个指针的数据填充为新的。接着，将超过缓冲区长度front指针和rear指针通过模运算重新循环到开头。若不加 % MAXSIZE会导致溢出的事情发生。

最后是出队

1
2
3
4
5
6
7
8
9
10
int deQueue(Node* P){
    if(isEmpty(P)){
        return -1;
    }else{
        int data = P->data[P->front];
        P->front = (P->front + 1) % MAXSIZE;
        return data;
    }
}

出队处理比较简单，只需要删除元素即可。

最后是打印函数

1
2
3
4
5
6
7
8
9
10
void printQueue(Node* P){
    int length =  (P->rear + MAXSIZE - P->front) % MAXSIZE;
    int index = P->front;
    for(int i = 1; i< length; i++){
            printf("%d ->",P->data[index]);
            index = (index+1) % MAXSIZE ;
    }    
    printf("Null\r\n");

}

length是打印队列的长度，可以往上再加来实现打印循环的队列。

测试样例：

1
2
3
4
5
6
7
8
9
int main(){
    Node* P = InitQueue();
    for(int i = 0; i < 10; i++){
        enQueue(P,i);
    }
    printQueue(P);
    return 0;
}

正常输出：

1
6 ->7 ->8 ->Null

多打印2个元素的输出和代码：

1
2
3
4
5
6
7
8
9
10
11
void printQueue(Node* P){
    int length =  (P->rear + MAXSIZE - P->front) % MAXSIZE;
    int index = P->front;
    for(int i = 1; i< length + 2; i++){
            printf("%d ->",P->data[index]);
            index = (index+1) % MAXSIZE ;
    }    
    printf("Null\r\n");

}

1
2
6 ->7 ->8 ->9 ->5 ->Null

完整代码：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include <stdio.h>
#include <stdlib.h>


#define MAXSIZE 5
typedef struct Node { //创建一个循环队列节点
    int data[MAXSIZE];                
    int front;
    int rear;
} Node;

Node* InitQueue(){
    Node* P = (Node*)malloc(sizeof(Node)); //初始化头节点
    P->front = P->rear = 0;
    return P;
}   

int isFull(Node* P){
    if((P->rear + 1) % MAXSIZE == P->front){
        return 1;
    }else{
        return 0;
    }
}

int enQueue(Node* P, int dat){
   if(isFull(P)){
        P->data[P->rear ] = dat;
        P->front = (P->front +1) % MAXSIZE;
        P->rear = (P->rear + 1 ) % MAXSIZE;
    } else {
        P->data[P->rear] = dat;
        P->rear = (P->rear + 1) % MAXSIZE;

    }
    
}

int isEmpty(Node* P){
    if(P-> front == P->rear){

        return 1;
    }
    else{
        return 0;
    }

}

int deQueue(Node* P){
    if(isEmpty(P)){
        return -1;
    }else{
        int data = P->data[P->front];
        P->front = (P->front + 1) % MAXSIZE;
        return data;
    }
}

void printQueue(Node* P){
    int length =  (P->rear + MAXSIZE - P->front) % MAXSIZE;
    int index = P->front;
    for(int i = 1; i< length; i++){
            printf("%d ->",P->data[index]);
            index = (index+1) % MAXSIZE ;
    }    
    printf("Null\r\n");

}

int main(){
    Node* P = InitQueue();
    for(int i = 0; i < 10; i++){
        enQueue(P,i);
    }
    printQueue(P);

//    printQueue(P);
    return 0;
}