顺序队列的实现
使用顺序表实现的队列称作顺序队列。顺序队列的实现和顺序表的实现相似，只是在顺序队列中只允许在一端进行插入，在另一端进行删除。定义两个变量front与rear分别标识队头与队尾，当删除队头元素时，front后移到下一个位置；当插入新元素时，在rear指示的位置插入，插入后，rear向后移动指向下一个存储位置。假设向图1中的队列插入新元素100：
图1 新元素100入队
首先将100插入到rear指示的位置，然后将rear向后移动。插入完成后的队列如图2所示。
图2 插入新元素100后
如图2所示，在rear位置插入新的元素后，rear向后移动；当再有新的元素入队时，还是插入到rear指示的位置，直到队列已满。假如顺序队列的大小为MAXSIZE，则当队尾指针指向MAXSIZE-1位置时（rear=MAXSIZE-1），队列就满了。
同样，当有元素出队时，front指针要向后移动，指向新的队头元素，其过程如图3所示。
图3 元素出队
当队列中元素全部出队时，front与rear指向同一块内存，即front=rear，这也是判断队列是否为空的条件。下面我们来实现一个具备以下功能的简单顺序队列：
● 创建一个空队列。
● 获取队列大小。
● 判断队列是否为空。
● 入队、出队。
● 获取队头元素。
● 清空、销毁队列。
并且完成此队列的测试，具体代码如例1所示。
例1
SeqQueue.h //头文件
1 #ifndef _SQQUEUE_H
2 #define _SQQUEUE_H
3
4 #define MAXSIZE 50
5 typedef struct Queue* SeqQueue;
6 struct Queue
7 {
8 int front; // 队头
9 int rear; // 队尾
10 int data[MAXSIZE]; // 数据
11 };
12
13 SeqQueue Create(); // 初始化操作，建立一个空队列Sq
14 int getLength(SeqQueue Sq); // 返回队列Sq的元素个数(长度）
15 int IsEmpty(SeqQueue Sq); // 判断队列是否为空
16 void Insert(SeqQueue Sq, int val); // 入队
17 int Del(SeqQueue Sq); // 出队
18 int GetHead(SeqQueue Sq); // 获取队头元素
19 void Clear(SeqQueue Sq); // 将队列Sq清空
20 void Destory(SeqQueue Sq); //销毁队列
21
22 #endif //_SQQUEUE_HSeqQueue.c //函数实现文件
23 #include "SeqQueue.h"
24 #include <string.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27
28 SeqQueue Create()
29 {
30 SeqQueue Sq = (SeqQueue)malloc(sizeof(struct Queue)); //分配空间
31 Sq->front = Sq->rear = -1;
32 memset(Sq->data, 0, MAXSIZE*sizeof(int));
33 return Sq;
34 }
35
36 int getLength(SeqQueue Sq)
37 {
38 return Sq->rear - Sq->front; //队列长度是队头队尾之差
39 }
40
41 int IsEmpty(SeqQueue Sq)
42 {
43 if (Sq->front = Sq->rear) //判断队列是否为空的条件
44 {
45 return 1;
46 }
47 return 0;
48 }
49
50 // 数组前边是队头, 后边是队尾
51 void Insert(SeqQueue Sq, int val)
52 {
53 // 队列是否已满
54 if (Sq->rear == MAXSIZE - 1)
55 {
56 printf("队列已满，无法再插入元素！\n");
57 return;
58 }
59 //如果是空队列
60 if (Sq->front == Sq->rear)
61 {
62 Sq->front = Sq->rear = 0;
63 Sq->data[Sq->rear] = val;
64 Sq->rear++;
65 }
66 else
67 {
68 Sq->data[Sq->rear] = val; //保存数据
69 Sq->rear++;
70 }
71 }
72
73 int Del(SeqQueue Sq)
74 {
75 // 空队列
76 if (Sq->front == Sq->rear) //队列为空的条件
77 {
78 printf("队列为空，无元素可弹！\n");
79 return 10000; //返回错误标志
80 }
81 int temp = Sq->data[Sq->front];
82 Sq->front++; //删除队头元素后，front向后移动
83 return temp;
84 }
85
86 int GetHead(SeqQueue Sq)
87 {
88 // 空队列
89 if (Sq->front == Sq->rear)
90 {
91 printf("队列为空，无元素可取！\n");
92 return 10000;
93 }
94 // 获取元素
95 return Sq->data[Sq->front];
96 }
97
98 void Clear(SeqQueue Sq)
99 {
100
101 Sq->front = Sq->rear = -1;
102 printf("队列已清空！\n");
103 }
104
105 void Destory(SeqQueue Sq)
106 {
107 free(Sq);
108 printf("队列已销毁!\n");
109 }main.c //测试文件
110 #include <stdio.h>
111 #include <stdlib.h>
112 #include "SeqQueue.h"
113
114 int main()
115 {
116 SeqQueue Sq = Create(); //创建队列
117 srand((unsigned)time(0));
118 for (int i = 0; i < 10; ++i)
119 {
120 Insert(Sq, rand() % 100); //入队列，随机产生的数
121 }
122 printf("队列长度：%d\n", getLength(Sq));
123 printf("队头元素 出队元素\n");
124 while (Sq->front != Sq->rear) //出队列，循环条件是队列不为空
125 {
126 int ret = GetHead(Sq); //获取队头元素
127 printf(" %d ", ret);
128 ret = Del(Sq); //出队列
129 printf("%d\n", ret);
130 }
131 printf("队列长度：%d\n", getLength(Sq));
132 Clear(Sq);
133 Destory(Sq);
134
135 system("pause");
136 return 0;
137 }运行结果如图4所示。
图4 例1运行结果
在例1中，代码6-11行定义了一个struct，其中定义了队头队尾标志front与rear，与一个int类型数组data，表明此队列用来存放int类型数据。之后的代码中一共实现了队列的创建、获取长度、判空、入队、出队、获取队头元素、清空和销毁这八个基本操作。顺序队列的实现与顺序表相似，但有几点需要注意：获取长度时，队列的长度是队列中实际存储数据的个数；在判断是否为空时，其条件是“front == rear”是否成立；在有新元素入队时，rear要向后移动；在有元素出队时，front要向后移动。
脚下留心：队列的“溢出”
在顺序队列的存储过程中，可能出现“溢出”现象，队列的“溢出”有两种情况，一种为真“溢出”，一种为假“溢出”。
所谓真“溢出”是指当队列分配的空间已满，此时再往里存储元素则会出现“溢出”，这种“溢出”是真的再无空间来存储元素，是真“溢出”。
而假“溢出”是指队列尚有空间而出现的“溢出”情况。当front端有元素出队时，front向后移动；当rear端有元素入队时，rear向后移动，若rear已指到队列中下标最大的位置，此时虽然front前面有空间，但再有元素入队也会出现“溢出”，这种“溢出”叫作“假溢出”。
隐藏目录
