队列

顺序队列

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

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

解决：
可采用循环队列

循环队列

将队列看成首尾相连的循环队列，通过牺牲一个单元来判断队列是否满。
具体实现可以通过以下方式：
‌牺牲一个单元：当队尾指针加一等于队首指针时，判断为队列满，即 (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
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <stdlib.h>

#define QUEUE_SIZE 50

int queue[QUEUE_SIZE] = {0};
int head = 0; // 队头出
int tail = 0; // 队尾进

void init_queue(void)
{
    head = 0;
    tail = 0;
}

// 入队操作
void enqueue(int value)
{
    if ((tail + 1) % QUEUE_SIZE == head)
    {
        printf("QUEUE IS FULL!\n"); // 队满
        init_queue(); // 队头、队尾清零；重新开始，即循环队列
        return;
    }
    queue[tail] = value;
    tail = (tail + 1) % QUEUE_SIZE;
}

// 出队操作
int dequeue(void)
{
    if (head == tail)
    {
        printf("QUEUE IS EMPTY!\n"); // 队空
        return -1;
    }
    int result = queue[head];
    queue[head] = 0;
    head = (head + 1) % QUEUE_SIZE;
    return result;
}

// 打印队列
void printQueue(void)
{
    int i = head;
    while (i != tail)
    {
        printf("%d ", queue[i]);
        i = (i + 1) % QUEUE_SIZE;
    }
    printf("\n");
}

int main(void)
{
    for (int i = 0; i < 50; i++)
    {
        enqueue(i);
    }
    printQueue(); // QUEUE IS FULL!

    for (int i = 49; i < 98; i++)
    {
        enqueue(i);
    }
    printQueue(); // 49 ~ 98
}