3.5.队列的次序实现

---

一.队列的次序实现，初始化使用以及判断队列是否为空：

1.图解：

2.代码：

2. #include<stdio.h>
3. #define MaxSize 10 //定义一个队列最多存储的元素个数
4. ​
5. typedef struct
6. {
7.     int data[MaxSize]; //用静态数组存放队列元素
8.     int front; //队头指针,队头删除元素
9.     int rear; //队尾指针,队尾插入元素
10. }SqQueue;
11. ​
12. //初始化队列
13. void InitQueue(SqQueue &Q)
14. {
15.     //初始时，队头和队尾指针都指向0
16.     Q.front=0;//对头一开始就为0即第一个位置
17.     Q.rear=0;//队尾指针指向下一个插入元素的位置，一开始没元素，下一个当然插在第一个位置即0索引处
18. }
19. ​
20. //判断队列是否为空
21. bool QueueEmpty(SqQueue Q)
22. {
23.     if( Q.rear==Q.front ) //Q.rear==Q.front为队空条件
24.     {
25.         return true; //代表队列为空
26.     }
27.     else
28.     {
29.         return false; //代表队列不为空
30.     }
31. }
32. ​
33. int main()
34. {
35.     SqQueue Q; //声明一个队列(顺序存储)
36.     InitQueue(Q);
37.     //后续操作。。。
38.     return 0;
39. }

复制代码

---

二.队尾元素入队使用(添加数据元素)：

1.图解：解读"队列已满即(Q.rear+1)%MaxSize==Q.front"的由来

a.入队使用起首要判断队列是否已满：

b.举例：

如下图，假设队尾指针指向9，但队头指针指向的不是0，因此Q.rear==MaxSize不能作为判断队列是否已满的条件->

c.如上图，添加一个元素：

d.对于队尾指针，元素入队后必要队尾指针举行Q.rear = (Q.rear+1)%MaxSize使用：

对于Q.rear = (Q.rear+1)%MaxSize，该使用在插入一个元素后举行，此时队头指针加1即Q.rear+1，再对队列最大存储空间MaxSize取模->这是为了克制假溢出

e.由于对队尾指针举行的使用是取余运算，会不停地从上到下的循环(比如除以3，余数只会是0,1,2)，因此形成了一个闭环：

比如：4%10=4，10%10=0。

f.上述就是一个循环队列，循环队列还可以办理如下的队列假溢出的环境：

g.继承刚才的例子，此时另有空闲的空间，因此可以继承插入新的数据元素：

h.同时必要队尾指针不停的后移：

i.当队列只剩末了一个存储空间时，就以为此时队列已经满了：

大概会问，此时不是还剩一个存储空间吗，为什么以为满了呢，但必要注意的是，初始化队列时，队头指针和队尾指针是指向了同一个位置，如果再添加一个元素到末了一个存储空间，就会导致队头指针便是队尾指针，与空队列条件划一，出现抵牾，
因此判断是否队列已经满了，也必要看队头指针和队尾指针是否指向了同一个位置
(注：队尾指针指向下一个插入元素的位置)

j.总结：

2.代码：

2. #include<stdio.h>
3. #define MaxSize 10 //定义一个队列最多存储的元素个数
4. ​
5. typedef struct
6. {
7.     int data[MaxSize]; //用静态数组存放队列元素
8.     int front; //队头指针,队头删除元素
9.     int rear; //队尾指针,队尾插入元素
10. }SqQueue;
11. ​
12. //初始化队列
13. void InitQueue(SqQueue &Q)
14. {
15.     //初始时，队头和队尾指针都指向0
16.     Q.front=0;//对头一开始就为0即第一个位置
17.     Q.rear=0;//队尾指向下一个插入元素的位置，一开始没元素，下一个当然插在第一个位置即0索引处
18. }
19. ​
20. //判断队列是否为空
21. bool QueueEmpty(SqQueue Q)
22. {
23.     if( Q.rear==Q.front ) //Q.rear==Q.front为队空条件
24.     {
25.         return true; //代表队列为空
26.     }
27.     else
28.     {
29.         return false; //代表队列不为空
30.     }
31. }
32. ​
33. //入队
34. bool EnQueue(SqQueue &Q,int x)
35. {
36.     if( (Q.rear+1)%MaxSize==Q.front )
37.     {
38.         return false;//此时队满,返回false
39.     }
40.     //此时队没满
41.     Q.data[ Q.rear ] = x;
42.     /*新元素插入队尾,应该插在Q.rear处,
43.     因为Q.rear队尾指针指向下一个插入元素的位置,而新插入的x刚好就要在
44.     下一个插入元素的位置*/
45.     Q.rear = (Q.rear+1)%MaxSize; //队尾指针加一取模
46.     return true;
47. }
48. ​
49. int main()
50. {
51.     SqQueue Q; //声明一个队列(顺序存储)
52.     InitQueue(Q);
53.     //后续操作。。。
54.     return 0;
55. }

复制代码

---

三.队头元素出队使用(删除数据元素)：

1.图解：

注：这里x有&，调用完函数后x也就跟着改变了 ，x就是被删除的谁人元素，队头指针后移就相当于删除了一个元素：

a.Q.front = (Q.front+1)%MaxSize，也必要对MaxSize取模,如许才气让front循环移动：

b.每次出队的都是front指针所指向的元素即x = Q.data[Q.front]，而且队头指针会向后移一位：

c.当队头指针和队尾指针再次指向同一个位置时，此时队列已经被取空，此时不能再举行出队使用：

2.代码：

2. #include<stdio.h>
3. #define MaxSize 10 //定义一个队列最多存储的元素个数
4. ​
5. typedef struct
6. {
7.     int data[MaxSize]; //用静态数组存放队列元素
8.     int front; //队头指针,队头删除元素
9.     int rear; //队尾指针,队尾插入元素
10. }SqQueue;
11. ​
12. //出队(删除一个队头元素,并用x返回)
13. bool DeQueue(SqQueue &Q,int &x) //这里x有&，调用完函数后x也就跟着改变了
14. {
15.     if( Q.rear==Q.front ) //首先要判断队列是否为空，因为空队列无法删除元素
16.     {
17.         return false; //此时队列为空
18.     }
19.     //此时队列不为空
20.     x = Q.data[Q.front];//把队头指针指向的元素赋值给变量x
21.     Q.front = (Q.front+1)%MaxSize;//队头指针后移一位,也需要对MaxSize取模,这样才能让front循环移动
22.     return true;
23. }
24. ​
25. int main()
26. {
27.     return 0;
28. }

复制代码

---

四.查找队列中的元素：

1.图解：

通常只必要查询大概只必要读取队列中队头的元素：

得到队头元素的值即查找元素，用x返回。这里x有&，调用完函数后x也就跟着改变了,变为队头元素； x就是队头元素，获取到队头元素后可以与要查找的元素比力。
2.代码：

2. #include<stdio.h>
3. #define MaxSize 10 //定义一个队列最多存储的元素个数
4. ​
5. typedef struct
6. {
7.     int data[MaxSize]; //用静态数组存放队列元素
8.     int front; //队头指针,队头删除元素
9.     int rear; //队尾指针,队尾插入元素
10. }SqQueue;
11. ​
12. //获得队头元素的值即查找元素，用x返回
13. /*这里x有&，调用完函数后x也就跟着改变了,变为队头元素；
14.  x就是队头元素，获取到队头元素后可以与要查找的元素比较*/
15.  //相比出队操作，就少了一个Q.front = (Q.front+1)%MaxSize，就不让队头指针后移
16. bool GetHead(SqQueue Q,int &x)
17. {
18.     if( Q.rear==Q.front )//需要判断队列是否为空，空队列无法查找元素
19.     {
20.         return false;//队空返回false
21.     }
22.     //此时队列不为空
23.     x = Q.data[Q.front];
24.     return true;
25. }
26. ​
27. int main()
28. {
29.     return 0;
30. }

复制代码

---

五.判断队列已满，已空：

1.队列此时已有的元素个数盘算公式：

(队尾指针+队列最多存储个数-队头指针)%队列最多存储个数
2.方案一：断送一个存储空间来判断队列已满，已空

3.方案二：无需断送一个存储空间即可判断队列已满，已空

思绪：在界说布局体队列时界说一个变量size，用来记载队列当前长度，size初始值为0，由于一开始没元素，
只要有元素入队，size自增；只要有元素出队，size自减

4.方案三：无需断送一个存储空间即可判断队列已满，已空

思绪：在界说布局体队列时界说一个变量tag，初始化时tag为0，由于一开始没元素，可以以为是删除后才没元素
当tag为0时表现迩来一次实行了一次删除使用，
当tag为1时表现迩来一次实行了一次插入使用，

---

六.其他出题方式：

1.如果队尾指针指向末了一个元素而不是下一个元素要插入的位置，那么入队时就必要先让队尾指针后移一个位置，
腾出位置来添加元素，末了再添加元素
2.如果队尾指针指向末了一个元素而不是下一个元素要插入的位置，那么在初始化时，队头指针指向第一个位置，
队尾指针指向末了一个位置->如许的话在元素入队时就会先队尾指针后移一个位置，再取余就可以了

---

七.总结：

注：静态数组巨细已经确定，因此要用模运算(取余运算)来重复地使用静态数组中各个空闲的存储空间。

---