队列(queue)，是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。是一种先进先出（FIFO）的数据结构。
一、队列的顺序存储->循环队列
1 #include <stdio.h>sj3_0
2 #include <stdlib.h>
3
4 #define OK 1
5 #define ERROR 0
6
7 #define MaxSize 20 /* 存储空间初始分配量 */
8
9 typedef int Status;
10 typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
11
12 /* 循环队列的顺序存储结构 */
13 typedef struct
14 {
15 QElemType data[MaxSize];
16 int front; /* 头指针 */
17 int rear; /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
18 }SqQueue;
19
20 Status InitQueue(SqQueue &Q);
21 Status ClearQueue(SqQueue &Q);
22 bool QueueEmpty(SqQueue Q);
23 bool QueueFull(SqQueue Q);
24 int QueueLength(SqQueue Q);
25 Status GetHead(SqQueue Q,QElemType &e);
26 Status EnQueue(SqQueue &Q,QElemType e);
27 Status DeQueue(SqQueue &Q,QElemType &e);
28 Status QueueTraverse(SqQueue Q);
29
30 Status visit(QElemType c)
31 {
32 printf("%d ",c);
33 return OK;
34 }
35
36 /* 初始化一个空队列Q */
37 Status InitQueue(SqQueue &Q)
38 {
39 Q.front = 0;
40 Q.rear = 0;
41 return OK;
42 }
43
44 /* 将Q清为空队列 */
45 Status ClearQueue(SqQueue &Q)
46 {
47 Q.front = Q.rear = 0;
48 return OK;
49 }
50
51 /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
52 bool QueueEmpty(SqQueue Q)
53 {
54 if(Q.front == Q.rear) /* 队列空的标志 */
55 return true;
56 else
57 return false;
58 }
59 /* 若队列Q满,则返回TRUE,否则返回FALSE */
60 bool QueueFull(SqQueue Q)
61 {
62 if( (Q.rear + 1) % MaxSize == Q.front)
63 return true;
64 else
65 return false;
66 }
67 /* 返回Q的元素个数，也就是队列的当前长度 */
68 int QueueLength(SqQueue Q)
69 {
70 return (Q.rear - Q.front + MaxSize) % MaxSize;
71 }
72
73 /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
74 Status GetHead(SqQueue Q,QElemType &e)
75 {
76 if(Q.front == Q.rear) /* 队列空 */
77 return ERROR;
78 e = Q.data[Q.front];
79 return OK;
80 }
81
82 /* 若队列未满，则插入元素e为Q新的队尾元素 */
83 Status EnQueue(SqQueue &Q,QElemType e)
84 {
85 if ((Q.rear+1) % MaxSize == Q.front) /* 队列满的判断 */
86 return ERROR;
87 Q.data[Q.rear] = e; /* 将元素e赋值给队尾 */
88 Q.rear = (Q.rear+1) % MaxSize;/* rear指针向后移一位置， */
89 /* 若到最后则转到数组头部 */
90 return OK;
91 }
92
93 /* 若队列不空，则删除Q中队头元素，用e返回其值 */
94 Status DeQueue(SqQueue &Q,QElemType &e)
95 {
96 if (Q.front == Q.rear) /* 队列空的判断 */
97 return ERROR;
98 e = Q.data[Q.front]; /* 将队头元素赋值给e */
99 Q.front = (Q.front+1) % MaxSize; /* front指针向后移一位置*/
100 /* 若到最后则转到数组头部 */
101 return OK;
102 }
103
104 /* 从队头到队尾依次对队列Q中每个元素输出 */
105 Status QueueTraverse(SqQueue Q)
106 {
107 int i = Q.front;
108 while( i != Q.rear)
109 {
110 visit(Q.data[i]);
111 i = (i + 1) % MaxSize;
112 }
113 printf("\n");
114 return OK;
115 }
116
117 int main()
118 {
119 QElemType d;
120 SqQueue Q;
121 int *e;
122 InitQueue(Q);
123 if( QueueEmpty(Q) )
124 printf("空\n");
125 else
126 printf("不空\n");
127 for(int i = 0; i < 5; i++) {
128 EnQueue(Q,i);
129 }
130 QueueTraverse(Q);
131 printf("QueueLength(Q) = %d\n",QueueLength(Q));
132 if( QueueEmpty(Q) )
133 printf("空\n");
134 else
135 printf("不空\n");
136
137 DeQueue(Q,*e);
138 printf("出队%d\n",*e);
139 QueueTraverse(Q);
140 printf("QueueLength(Q) = %d\n",QueueLength(Q));
141
142 GetHead(Q,*e);
143 printf("头%d\n",*e);
144 ClearQueue(Q);
145 if( QueueEmpty(Q) )
146 printf("空\n");
147 else
148 printf("不空\n");
149
150 if(QueueFull(Q))
151 printf("队列满\n");
152
153 return 0;
154 }
由于当前队列的最大分配空间为6，当再有两个元素进队列，则不可插入新的元素，即使0位置上为空或有元素出队列。易得，该结构空间利用率不高。
因此，我们改用循环队列。(代码：sj3_0)
将空队列和满队列进行比较，只凭Q.front ==Q.rear,无法判断队列是满还是空。
这里有两种解决办法： 1.增设一个标志位flag或size，来记录队列是满或者空
2.少用一个元素空间，利用Q.rear的下一位是Q.front来判断队列满
typedef struct
{
QElemType data[MaxSize];
int front; /* 头指针 */
int rear; /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue;
#define MaxSize 20 /* 存储空间初始分配量 */
循环队列的基本操作(代码：sj3_0)
Status InitQueue(SqQueue &Q);
Status ClearQueue(SqQueue &Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q)；
int QueueLength(SqQueue Q);
Status GetHead(SqQueue Q,QElemType &e);
Status EnQueue(SqQueue &Q,QElemType e);
Status DeQueue(SqQueue &Q,QElemType &e);
Status QueueTraverse(SqQueue Q);
1.判断队列是否空
由上易得: 
1 /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */View Code
2 bool QueueEmpty(SqQueue Q)
3 {
4 if(Q.front == Q.rear) /* 队列空的标志 */
5 return true;
6 else
7 return false;
8 }
2.判断队列是否满
此处我们选择，第二种解决方法。
由图可知，Q.rear+1 == Q.front队列满的标志。由于是循环队列，Q.rear在5,且Q.front在0时,特殊情况因此，我们一致使用(Q.rear+1) % MaxSize == Q.front。
1 /* 若队列Q满,则返回TRUE,否则返回FALSE */View Code
2 bool QueueFull(SqQueue Q)
3 {
4 if( (Q.rear + 1) % MaxSize == Q.front)
5 return true;
6 else
7 return false;
8 }
3.入队
1 /* 若队列未满，则插入元素e为Q新的队尾元素 */View Code
2 Status EnQueue(SqQueue &Q,QElemType e)
3 {
4 if ((Q.rear+1) % MaxSize == Q.front) /* 队列满的判断 */
5 return ERROR;
6 Q.data[Q.rear] = e; /* 将元素e赋值给队尾 */
7 Q.rear = (Q.rear+1) % MaxSize;/* rear指针向后移一位置， */
8 /* 若到最后则转到数组头部 */
9 return OK;
10 }
这里的Q.rear = (Q.rear+1) % MaxSize;依据与判断队列满不满一样。
4.出队列
1 /* 若队列不空，则删除Q中队头元素，用e返回其值 */View Code
2 Status DeQueue(SqQueue &Q,QElemType &e)
3 {
4 if (Q.front == Q.rear) /* 队列空的判断 */
5 return ERROR;
6 e = Q.data[Q.front]; /* 将队头元素赋值给e */
7 Q.front = (Q.front+1) % MaxSize; /* front指针向后移一位置*/
8 /* 若到最后则转到数组头部 */
9 return OK;
10 }
二.链队列
队列的链式表示如图。(代码：sj3_1)
1 //链队列sj3_1
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 #define OK 1
7 #define ERROR 0
8
9 #define MAXSIZE 20 /* 存储空间初始分配量 */
10
11 typedef int Status;
12
13 typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
14
15 typedef struct QNode /* 结点结构 */
16 {
17 QElemType data;
18 struct QNode *next;
19 }QNode,*QueuePtr;
20
21 typedef struct /* 队列的链表结构 */
22 {
23 QueuePtr front; /* 队头指针 */
24 QueuePtr rear; /* 队尾指针 */
25 }LinkQueue;
26
27 Status InitQueue(LinkQueue &Q);
28 Status DestroyQueue(LinkQueue &Q);
29 Status ClearQueue(LinkQueue &Q);
30 bool QueueEmpty(LinkQueue Q);
31 int QueueLength(LinkQueue Q);
32 Status GetHead(LinkQueue Q, QElemType &e);
33 Status EnQueue(LinkQueue &Q, QElemType e);
34 Status DeQueue(LinkQueue &Q,QElemType &e);
35 Status QueueTraverse(LinkQueue Q);
36
37 Status visit(QElemType c)
38 {
39 printf("%d ",c);
40 return OK;
41 }
42
43 /* 构造一个空队列Q */
44 Status InitQueue(LinkQueue &Q)
45 {
46 Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
47 if(!Q.front)
48 exit(OVERFLOW);
49 Q.front->next = NULL;
50 return OK;
51 }
52
53 /* 销毁队列Q */
54 Status DestroyQueue(LinkQueue &Q)
55 {
56 while(Q.front) {
57 Q.rear=Q.front->next;
58 free(Q.front);
59 Q.front=Q.rear;
60 }
61 return OK;
62 }
63
64 /* 将Q清为空队列 */
65 Status ClearQueue(LinkQueue &Q)
66 {
67 QueuePtr p,q;
68 Q.rear = Q.front;
69 p = Q.front->next;
70 Q.front->next = NULL;
71 while(p) {
72 q = p;
73 p = p->next;
74 free(q);
75 }
76 return OK;
77 }
78
79 /* 若Q为空队列,则返回TRUE,否则返回FALSE */
80 bool QueueEmpty(LinkQueue Q)
81 {
82 if(Q.front==Q.rear)
83 return true;
84 else
85 return false;
86 }
87
88 /* 返回Q的元素个数，即队列的长度 */
89 int QueueLength(LinkQueue Q)
90 {
91 int i = 0;
92 QueuePtr p;
93 p = Q.front;
94 while(Q.rear != p) {
95 i++;
96 p = p->next;
97 }
98 return i;
99 }
100
101 /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
102 Status GetHead(LinkQueue Q, QElemType &e)
103 {
104 QueuePtr p;
105 if(Q.front == Q.rear)
106 return ERROR;
107 p = Q.front->next;
108 e = p->data;
109 return OK;
110 }
111
112
113 /* 插入元素e为Q的新的队尾元素 */
114 Status EnQueue(LinkQueue &Q, QElemType e)
115 {
116 QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
117 if(!s) /* 存储分配失败 */
118 exit(OVERFLOW);
119 s->data = e;
120 s->next = NULL;
121 Q.rear->next = s; /* 把拥有元素e的新结点s赋值给原队尾结点的后继*/
122 Q.rear = s; /* 把当前的s设置为队尾结点，rear指向s */
123 return OK;
124 }
125
126 /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
127 Status DeQueue(LinkQueue &Q,QElemType &e)
128 {
129 QueuePtr p;
130 if(Q.front == Q.rear)
131 return ERROR;
132 p = Q.front->next; /* 将欲删除的队头结点暂存给p */
133 e = p->data; /* 将欲删除的队头结点的值赋值给e */
134 Q.front->next = p->next; /* 将原队头结点的后继p->next赋值给头结点后继*/
135 if(Q.rear == p) /* 若队头就是队尾，则删除后将rear指向头结点*/
136 Q.rear = Q.front;
137 free(p);
138 return OK;
139 }
140
141 /* 从队头到队尾依次对队列Q中每个元素输出 */
142 Status QueueTraverse(LinkQueue Q)
143 {
144 QueuePtr p;
145 p = Q.front->next;
146 while(p) {
147 visit(p->data);
148 p = p->next;
149 }
150 printf("\n");
151 return OK;
152 }
153
154 int main()
155 {
156 QElemType e;
157 LinkQueue Q;
158 InitQueue(Q);
159 if(QueueEmpty(Q))
160 printf("空\n");
161 else
162 printf("不空\n");
163 for(int i = 0; i < 5; i++)
164 EnQueue(Q,i);
165 QueueTraverse(Q);
166 printf("队列的长度为%d\n",QueueLength(Q));
167 if(QueueEmpty(Q))
168 printf("空\n");
169 else
170 printf("不空\n");
171 GetHead(Q,e);
172 printf("队头元素是：%d\n",e);
173 DeQueue(Q,e);
174 printf("删除了队头元素%d\n",e);
175 QueueTraverse(Q);
176 ClearQueue(Q);
177 if(QueueEmpty(Q))
178 printf("空\n");
179 else
180 printf("不空\n");
181 DestroyQueue(Q);
182 if(QueueEmpty(Q))
183 printf("空\n");
184 else
185 printf("不空\n");
186
187 return 0;
188 }
1.入队
1 /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */View Code
2 Status DeQueue(LinkQueue &Q,QElemType &e)
3 {
4 QueuePtr p;
5 if(Q.front == Q.rear)
6 return ERROR;
7 p = Q.front->next; /* 将欲删除的队头结点暂存给p */
8 e = p->data; /* 将欲删除的队头结点的值赋值给e */
9 Q.front->next = p->next; /* 将原队头结点的后继p->next赋值给头结点后继*/
10 if(Q.rear == p) /* 若队头就是队尾，则删除后将rear指向头结点*/
11 Q.rear = Q.front;
12 free(p);
13 return OK;
14 }
算法思路：
1.创建新结点s 其值为e
2.Q.rear->next = s ①
3.Q.rear = s ②
2.出队
1 /* 从队头到队尾依次对队列Q中每个元素输出 */View Code
2 Status QueueTraverse(LinkQueue Q)
3 {
4 QueuePtr p;
5 p = Q.front->next;
6 while(p) {
7 visit(p->data);
8 p = p->next;
9 }
10 printf("\n");
11 return OK;
12 }
算法思路：
1.若队列为空，返回ERROR
2.记录p=Q.front->next e为其值①
3.Q.front ->next = p->next ②
4.free(p)