队列

顺序队列

顺序队列存在假溢出的现象：
假溢出‌是指在使用顺序存储队列时，队列作为存储区还没有满，但由于队列的操作规则（队首删除、队尾插入），导致队尾指针已经占满了所有空间，而队首仍有空闲单元的现象。

假溢出的原因：
假溢出的原因在于顺序存储队列的操作规则。
队列允许在队首进行删除操作，在队尾进行插入操作。当队尾指针达到数组的最大容量时，如果队首指针不指向数组的起始位置，队列中仍然有空闲单元，但再进行入队操作会导致假溢出。

解决：
可采用循环队列

循环队列

将队列看成首尾相连的循环队列，通过牺牲一个单元来判断队列是否满。
具体实现可以通过以下方式：
‌牺牲一个单元：当队尾指针加一等于队首指针时，判断为队列满，即 (tail + 1) % QUEUE_SIZE == head

注意：

  1. 使用循环队列时，其队列长度一般都要比要存入的数据长度大
  2. 队列的最后一个元素永远不会被使用，这就是第一点的原因

代码实现

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
#define QUEUE_U8_SIZE (128)

typedef struct
{
    volatile uint16_t head;
    volatile uint16_t tail;
    uint8_t*          data;
} queue_u8_t;

void queue_u8_init(queue_u8_t* p, uint8_t* data)
{
    p->head = 0;
    p->tail = 0;
    p->data = data;
}

uint8_t queue_u8_is_full(volatile queue_u8_t* p)
{
    return (p->head == ((p->tail + 1) % QUEUE_U8_SIZE)) ? 1 : 0;
}

uint8_t queue_u8_is_empty(volatile queue_u8_t* p)
{
    return (p->head == p->tail) ? 1 : 0;
}

uint8_t queue_u8_push(volatile queue_u8_t* p, uint8_t data)
{
    if (queue_u8_is_full(p))
    {
        return 0;
    }
    p->data[p->tail] = data;
    p->tail          = (uint8_t)(p->tail + 1) % QUEUE_U8_SIZE;
    return 1;
}

uint8_t queue_u8_pop(volatile queue_u8_t* p, uint8_t* data)
{
    if (queue_u8_is_empty(p))
    {
        return 0;
    }
    *data   = p->data[p->head];
    p->head = (uint8_t)(p->head + 1) % QUEUE_U8_SIZE;
    return 1;
}


// 使用
static u8    uart_tx_buf[QUEUE_U8_SIZE] = {0};
static u8    uart_rx_buf[QUEUE_U8_SIZE] = {0};
static queue_u8_t uart_tx_queue         = {0, 0, uart_tx_buf};
static queue_u8_t uart_rx_queue         = {0, 0, uart_rx_buf};

queue_u8_init(&uart_tx_queue, uart_tx_buf);
queue_u8_init(&uart_rx_queue, uart_rx_buf);