撰写
大家好，经过前三篇数据结构文章的学习。对于数组和链表以及线性结构的应用——栈有了初步的认识，这篇文章趁热打铁学习线性结构的另外一种应用——队列
队列(Queue)是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。综上，只要能满足“先进先出”条件的线性表，称之为队列。
概念看完了我们接着来。首先看队列有几种形式，第一种静态队列和第二种动态队列。类似于栈的两种形式，静态队列是用数组实现的，而动态队列的核心是链表。
我们知道队列有几个专有名词：前端(front)、后端(rear)、队尾、队头、入队。那如何创建一个队列呢？
类似排队买票，有队头队尾买完票走掉，和新来的人排在队伍的后方。在这里，我用一个数组来模拟人们排队买票的情景，首先指定一个元素指向队伍最前面的那个人，自然就有另一个元素代表队尾。当队伍后方有人来排队的时候，需要将队尾元素指向这个人，有人离开队伍时，应该将队头变量指向离开的人的后一个人。
在前面的三篇笔记中，无论是链表还是栈都预留了一个“无意义”的结点，来充当头结点或尾结点。这里我们也保留这个优良传统，我们定义，队尾变量永远指向最后一个有效元素的后一个元素。
现在我们有一个长度为6的数组，它的下标自然为0、1、2、3、4、5
front保存了队头的下标值，rear保存了队尾最后一个有效元素的下一个元素的下标值。
第一种情况，front为0，rear为5指向数组的最后一个元素，当再进行入队操作时，首先把值存入当前r保存的下标值对应的元素中，然后把rear加一，但是，如果再加一，数组就会越界。然而此时又不宜如栈那样，进行存储再分配扩大数组空间，因为队列的实际可用空间并未占满。
第二种情况，f指向队头，r指向最后一个有效元素的下一个元素，每次入队r都会加一，假如现在r增加到了4，想进行出队操作(此时队列中有4个元素)，需要将f增加，f增加到了2，此时相当于只剩2个元素，删除了前两个元素，这样就会造成我们被删除的位置永远无法再被利用，就会造成空间的浪费。所以，一般的数组就达不到要求了，所以静态队列需要用循环队列。
在正式学习循环队列之前，先要弄清楚几个问题：
根据前面的描述，创建循环队列需要2个参数来确定front，rear。
1.两个参数代表的含义始终是一样的吗？
在这里两个参数在不同的场合下有不同的含义：
(1)初始化队列时：front和rear都是0
(2)队列非空时：front代表队列的第一个元素，rear则代表的是最后一个有效元素的下一个元素
(3)队列为空时，front和rear的值相等，但不一定是0
2.如何判断队列为空?
这个问题简单，front的值和rear相等即可
3.如何判断队列已满
再循环队列中，如果每个结点都放上元素，front和rear就会重合，这样无法判断队列的当前状态了，所以一个长度为N的队列存放N-1个元素，对应代码(rear + 1) % len == f 判断这个表达式的布尔值即可。
老规矩，先定义队列的基本结构
typedef struct Queue {
int * pBase;
int front;
int rear;
}QUEUE;类似于上文的创建空队列的方法，将front和rear的值都等于0，分配的空间赋给pBase
// 初始化队列
void init(QUEUE * pQ) {
pQ->pBase = (int *)malloc(sizeof(int) * 6); // 分配空间
pQ->front = 0;
pQ->rear = 0;
}定义一些循环队列基本的函数
void init(QUEUE *); // 初始化队列
bool en(QUEUE *, int val); // 入队
bool full(QUEUE * );
void trasevel(QUEUE *); // 遍历队列
bool out(QUEUE *, int * ); // 出队
bool empty(QUEUE * ); // 是否为空其中，入队的写法要注意先判断当前队列是否已满。队列不是满的状态下，
把值放在rear下标对应的元素里。而后，将rear的值通过rear+1和长度取余的方式，让rear往后走一个
// 判断队列是否为满
bool full(QUEUE * pQ) {
if( (pQ->rear + 1) % 6 == pQ->front) {
return true;
}else {
return false;
}
}
// 入队
bool en(QUEUE * pQ, int val) {
if(full(pQ)) {
// 队列满了，不能入队
return false;
}else {
pQ->pBase[pQ->rear] = val; //把值放在r下标对应的元素里
pQ->rear = (pQ->rear + 1) % 6; //r往后走一个
return true;
}
}#include <stdio.h>
#include <malloc.h>
typedef struct Queue {
int * pBase;
int front;
int rear;
}QUEUE;
void init(QUEUE *); // 初始化队列
bool en(QUEUE *, int val); // 入队
bool full(QUEUE * );
void trasevel(QUEUE *); // 遍历队列
bool out(QUEUE *, int * ); // 出队
bool empty(QUEUE * ); // 是否为空
int main() {
int val;
QUEUE Q;
init(&Q);
en(&Q, 1);
en(&Q, 2);
en(&Q, 3);
en(&Q, 4);
en(&Q, 5);
en(&Q, 6);
trasevel(&Q);
if(out(&Q, &val)) {
trasevel(&Q);
}else {
printf("出队失败n");
}
return 0;
}
// 初始化队列
void init(QUEUE * pQ) {
pQ->pBase = (int *)malloc(sizeof(int) * 6); // 分配空间
pQ->front = 0;
pQ->rear = 0;
}
// 判断队列是否为满
bool full(QUEUE * pQ) {
if( (pQ->rear + 1) % 6 == pQ->front) {
return true;
}else {
return false;
}
}
// 入队
bool en(QUEUE * pQ, int val) {
if(full(pQ)) {
// 队列满了，不能入队
return false;
}else {
pQ->pBase[pQ->rear] = val; //把值放在r下标对应的元素里
pQ->rear = (pQ->rear + 1) % 6; //r往后走一个
return true;
}
}
// 遍历队列
void trasevel(QUEUE * pQ) {
int i = pQ->front; // i存储了f的值
while (i != pQ->rear) {
printf("%d ",pQ->pBase[i]);
i = (i + 1)%6;
}
printf("n");
}
// 是否为空
bool empty(QUEUE * pQ) {
if(pQ->front == pQ->rear) {
return true;
}else {
return false;
}
}
// 出队
bool out(QUEUE * pQ, int * pVal ) {
if(empty(pQ)) {
return false;
}else {
* pVal = pQ->pBase[pQ->front];
pQ->front = (pQ->front + 1)%6; // 变更F的值
return true;
}
}原文始发于微信公众号（代码墙）：数据结构学习笔记(四)队列