直到海角天涯
0%

C队列实现

发表于 分类于

下述代码已在deepin验证。

gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1) 

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
83
84
85
86
87
#include <stdio.h>
#include <stdlib.h>

#define Q_SIZE 8

struct queue
{
    int *buf;
    int read;
    int write;
};

#if 1 方式1
char queue_insert(struct queue *q,int data)
{
    if(q->write-q->read== Q_SIZE)
        return 1;

    q->buf[q->write & (Q_SIZE-1)] = data;
    q->write++;
    return 0;
}

char queue_get(struct queue *q,int * data)
{
    if(q->write == q->read)
        return 1;

    *data = q->buf[q->read & (Q_SIZE-1)];
    q->read++;

    return 0;
}
#else //方式2
char queue_insert(struct queue *q,int data)
{
    if((q->write+1)%Q_SIZE==q->read)
        return 1;

    q->buf[q->write & (Q_SIZE-1)] = data;
    q->write=(q->write+1)%Q_SIZE;
    return 0;
}

char queue_get(struct queue *q,int * data)
{
    if(q->write == q->read)
        return 1;

    *data = q->buf[q->read & (Q_SIZE-1)];
    q->read=(q->read+1)%Q_SIZE;

    return 0;
}
#endif

int main(void)
{
    int i;
    struct queue q;

    q.buf=(int*)malloc(sizeof(int)*Q_SIZE);
    q.read=0;
    q.write=0;

    for(i=0;i<Q_SIZE+2;i++)
    {
        if(queue_insert(&q,i))
        {
            printf("queue is full\n");
            break;
        }
    }

    int data;
    for(i=0;i<Q_SIZE+2;i++)
    {
        if(queue_get(&q,&data))
        {
            printf("queue is empty\n");
            break;
        }
        printf("%d:%d\n",i,data);
    }
    
    return 0;
}

方式1结果

26dtbT.png

方式结果2

26dyKx.png

也就是说，相比于方式2，方式1不会存在浪费空间的问题。

一个需要注意的就是Q_SIZE，方式1中如下方式处理也是为了提高速度，但是有一点需要注意，即Q_SIZE的大小需要是2的幂。

q->read & (Q_SIZE-1)

q->write & (Q_SIZE-1)

另一个需要注意的问题，即

char queue_insert(struct queue q,int data)函数中的***if(q->write-q->read== Q_SIZE)**，因为Q_SIZE远小于int类型可表示的最大数，所以不会因为溢出而产生错误。一个验证函数如下。

1
2
3
4
5
6
7
8
9
10
11
12
#include "stdio.h"

int main()
{
    unsigned int a=0xfffffff4;//-12
    unsigned int b=15;

    unsigned int c=b-a;
    printf("0x%x-0x%x=0x%x\n",b,a,c);

    return 0;
}

运行结果如下

26DrFO.png