C语言 环形队列

队列 ：队列是一种先进先出的数据结构。

比如说

排队买票，

有一个售票口，最多能排30人，那么最大存储空间就是30人，

每当有1个新人过来排队，就会站在队尾，这就叫入队，

每当有1个人买到票了，就会离开，就叫出队。

生活中，最前面1个人买完票后，队伍中剩下的每1个人都会向前走1位，

对于计算机来说，每个人动一下意味着要执行更多的代码，

如果卖票的人卖完第1个 ，第一个人就离开，

售票员就走向第2个，再走向第3个，

直到1队队伍尾走完，再进1队。售票员就重头开始走就会更方便。

========================================================

环形队列是这样的，不用每个人都向前移动1位，

在一个排满的队列中，当售票员卖了第1张票时，不要每个人向前移动。

因为1号位空出来了，下一个排队的人就站在1号位置上，队尾+1变成2，

售票员向前走了一步，再卖1张，

2号位置空出来了，下一个排队的人就到2号位置上，

队尾+1变成3，依次类推，

售票员卖到队伍尾部后又会重头开始来，依旧是按照1 2 3 的顺序，

就不需要执行更多的代码。

环形队列需要考虑以下内容：
1. 创建队列
（最大存储量，队列长度，队头下标，队尾下标，数组记录队伍每个下标的内容）
2. 删除队列，不需要的时候从内存中清除。
3. 队列为空判断，不能出队操作了。
4. 队列为满判断，不能入队操作了。
5. 遍历队列元素，验证队列内容是否按照要求来。

取余数就是为了，队伍再次从头开始排队。

代码就按照以上的需求进行建立

#define  MAXSIZE  5
#include <iostream>

// 队列包含的信息
typedef struct queue
{
    int *qu;      //用来存储全部的队列中的元素
    int head;     //队列头
    int tail;     //队尾
    int qlength;  //队列长度
    int maxsize;  //用来记录队列的最大容量

}QUEUE;

//  初始化队列
QUEUE  *CreateQueue ( int maxsize)
{
    printf("[%lu]",sizeof(QUEUE));
     QUEUE *q= (QUEUE *)malloc(sizeof(QUEUE));

    if (q == NULL) {
        printf("Memory alloc failure\n");
        exit(-1);
    }


    q->qu=(int *)malloc(sizeof(int)*maxsize);
    if(NULL==q->qu)
    {
        printf("Memory allocation failure");
        exit(-1);        //退出程序
    }
    //分配完空间后，1开始队头队尾都在一起，因为没人，都为0长度也为0，
    q->head = 0;
    q->tail = 0;
    q->qlength = 0;
    q->maxsize = maxsize;


    return q;
}

// 判断空队列，长度为0则为空
bool Empty (QUEUE *q)
{
   return  q->qlength == 0 ? true : false;
}

// 判断满队列，长度=最大容量为满
bool Full (QUEUE *q)
{
    return q->qlength == q->maxsize ? true : false;
}

//入队
bool Enqueue (QUEUE *q , int num)
{
    // 队列不满才插入
    if (Full(q)) {
        printf("队列满了，插入失败\n");
        return false;

    }else{
        //给队伍最尾添加赋值。
        q->qu[q->tail] = num;
        //队尾向后移动一位，如果超过最大值，则从0开始，变成队尾
        q->tail = (q->tail +1)%q->maxsize;
        //队伍长度+1
        q->qlength ++;
        return true;
    }

}
// 出队
bool Dequeue (QUEUE *q)
{
    // 队列有元素才能够删除
    if (Empty(q)) {
        printf("队列为空，删除失败\n");
        return false;
    }else{
        //队头向后移动一位 超过最大值又重新 从0 开始计算
        q->head = (q->head +1)%q->maxsize;
        // 队伍长度-1
        q->qlength -- ;

        return true;
    }
}

// 遍历队列元素
void Traverse(QUEUE *q)
{
    // 在队列长度范围内 打印队列从队列头 到队列尾的元素
    for (int i=0 ; i<q->qlength; i++) {
      printf("%d ",  q->qu[(q->head+i)%q->maxsize]);
    }
    printf("\n");
}



int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";


    QUEUE Q =*CreateQueue(MAXSIZE);
    if ( Empty(&Q)) {
        printf("空队列\n");
    };

    Enqueue(&Q, 10);

    Enqueue(&Q, 12);

    Enqueue(&Q, 14);
    if ( Empty(&Q)) {
        printf("空队列\n");
    };
    Enqueue(&Q, 16);

    Enqueue(&Q, 18);

    Dequeue(&Q);

    Enqueue(&Q, 20);

    if (Full(&Q)) {
        printf("满队列\n");
    }

    Traverse(&Q);


    return 0;
}
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

运行结果

Hello, World!
[24]空队列
满队列
12 14 16 18 20 
Program ended with exit code: 0
1
2
3
4
5