循环队列Queue

2024-01-03 13:42:10

一、定义Queue_t 的数据类型

#define QUEUESIZE   1000
typedef struct Queue {
    u8 queue[QUEUESIZE];
    int queue_read;
    int queue_write;
    enum {
        no_read = 0,    //未执行读操作
        reading,        //正在执行读操作
        reread,         //读指针已被重写
    } queue_mark; 
} Queue_t;

queue为存放循环队列的数组，QUEUESIZE为存放循环队列的数组大小，queue_read为队头，queue_write为队尾，枚举类型所定义的元素表示出队时候的状态。

二、宏定义判断循环队列是否为满

//判断循环队列是否为满
#define is_queue_full(queue) ((((queue)->queue_write + 1) % QUEUESIZE == (queue)->queue_read) ? 1 : 0)

当队头的指针往前移动一步的时候等于队尾的指针，即为队满。

补充知识点：%运算符。取模运算符，整除后的余数。例如：3%5 结果就是2。%前后的数字可以对调。

三、宏定义判断循环队列是否为空

//判断循环队列是否为空
#define is_queue_empty(queue) (((queue)->queue_read == (queue)->queue_write) ? 1 : 0)

当队头的指针等于队尾的指针的时候，即为对空。

四、宏定义使数组下标在循环队列中进行移动

//使数组下标在循环队列中进行移动
#define queue_skip(p, n) do {(p) = ((p) + (n)); (p) = (p) <  QUEUESIZE ? (p) : (p) - QUEUESIZE;} while(0)

当指针p的下标超过了数组的长度。将返回p - QUEUESIZE，这样就实现了循环队列。例如QUEUESIZE = 50，p当前指向的是49，n = 2。则返回 p = 51 - 50 = 1 。

补充知识点：#define宏定义。宏定义只是用宏名来表示一个字符串，在宏展开时又以该字符串取代宏名，这只是一种简单的代换。由于预处理程序对宏不做任何检查处理，所以如果宏定义和使用出错的话在编译前我们是很难发现的，只有在编译已经被宏展开后的源程序时才能发现。在此，简单的举例说明一下C语言中用宏定义表示数据类型和用typedef定义数据说明符的区别。宏定义只是简单的字符串代换，是在预处理完成的，而typedef是在编译时处理的，它不是作简单的代换，而是对类型说明符重新命名。请看下面的例子：

 #define P1 int *
 typedef (int *) P2;

从形式上看这两者相似，但在实际使用中却不相同。下面用P1，P2说明变量时就可以看出它们的区别：

P1 a,b;在宏代换后变成:
 int *a,b;
//表示a是指向整型的指针变量，而b是整型变量。

P2 a,b;宏代换后变成：
int *a,*b;
//表示a,b都是指向整型的指针变量。

五、宏定义计算循环队列中的已存数据的数量

//计算循环队列中的已存数据的数量
#define queue_count(queue)  (((queue)->queue_write - (queue)->queue_read >= 0) ? ((queue)->queue_write - (queue)->queue_read) : ((queue)->queue_write - (queue)->queue_read + QUEUESIZE))

如果尾指针减去头指针大于0的话，循环队列中已存数据的数量就是尾指针（queue_write）减去头指针（queue_read）。否则就是尾指针（queue_write）减去头指针（queue_read）加上QUEUESIZE。

六、函数实现循环队列的初始化

/**
 * 循环队列初始化
 * 
 * 主要对读写指针的初始化
 */
static int queue_init(Queue_t *queue)
{
    //queue->queue[QUEUESIZE] = {0};
    queue->queue_read = 0;
    queue->queue_write = 0;

    queue->queue_mark = no_read;

    return 0;
}

初始化头指针和尾指针。以及循环队列的读取状态为no_read。

七、函数实现入队操作

//入队操作
/**
 * 将val加入循环队列g_queue中
 *
 * 返回值：0： 成功 
 *         1： 失败
 */
static inline int en_queue(Queue_t *queue, uint8_t val)
{   
    if(is_queue_full(queue))
    {
        if (queue->queue_mark == reading) //判断是否有在读取
        {
            queue->queue_mark = reread;
        }

        queue_skip(queue->queue_read, 1);
    }

    queue->queue[queue->queue_write] = val;
    queue_skip(queue->queue_write, 1);

    return 0;
}

首先判断循环队列是否为满，如果为满判断是否有数据在读，如果有数据在读，读指针将被重写。

队头向前移动一步。将数据存到队尾，队尾指针向前移动一步。

如果循环队列没有满，则直接将数据存到队尾，队尾指针向前移动一步。

八、函数实现出队操作

//循环队列的出队操作
static inline int out_queue(Queue_t *queue, uint8_t *pVal)
{
    if(is_queue_empty(queue))
    {
        return 0;
    }
    else
    {
        *pVal = queue->queue[queue->queue_read];
        queue_skip(queue->queue_read, 1);

        return 1;
    }
}

*pVal为出队后的元素将要存放的地址。如果循环队列为空，返回0 。否则将数组中下标为queue_read的元素取出，然后queue_read指针向前移动一步。返回 1。

补充知识点：inline关键字。运用inline关键字修饰的函数，被调用的过程中会与普通的函数调用不同。普通的函数调用通常要经过“保存指令位置、程序流程跳转到子函数、执行子函数、返回之前的指令位置”这个过程。但是这样对于经常被调用的小程序来说，这样的调用过程会影响程序的执行效率。inline函数的调用过程会告诉编译器把这些小函数编译后的机器码放到调用函数的地方，这样就节省了函数调用的时间。inline关键字并非强制性的，它只是“暗示”编译器可以把函数当做inline函数来处理，但是编译器很有可能会对此置之不理。

九、函数实现出队把数据保存在消息队列

static inline int queue_get_all(Queue_t *queue, uint8_t *msg, int maxsize)
{
    int len = 0;
    uint8_t ret = 0;

    do {
        ret = out_queue(queue, &msg[len]);
        len += ret;
        if (len > maxsize)
            break;
    } while(ret != 0);

    return len;
}

*msg为要保存的消息队列，当出队的元素等于想要的数据长度时就跳出循环，返回存储在消息队列里的数据长度。

十、函数实现数据计算校验和

/************************************************************************
Function:       Total
Description:    计算校验和
Calls:          无
Data Accessed:  无
Data Updated:   无
Input:          point：带计算的数据缓存区首地址
length：需要计算的个数
Output:         无
Return:         计算后的校验和
Others:         无
 *************************************************************************/
static inline uint8_t queue_total(Queue_t *queue, int start, int count)
{
    uint8_t total = 0;
    int left = count;
    int p = start;

    if (count < 0)
        return 0;

    while(left-- > 0)
    {       
        total += queue->queue[p];
        queue_skip(p, 1);         
    }

    total = (uint8_t)(0x100 - total);

    return total;
}

码农公寓