数据结构（四）
这是数据结构的第4篇文章
我们上次了解到了单链表，双向链表，循环链表的特点和他们的代码表达。
那么再简单地回顾一下，链表是一种数据的存储方式，保存数据在内存中不连续，用指针进行访问。
那么今天讲的队列和链表又有什么关系呢？
队列是一种数据结构，它也是一种线性表，也因此可以用链表进行存储。
队列
队列并不难，在我们生活中也十分常见，就是简单的排队打饭。
排在队伍第一位的学生（表头）最先开始打饭，当他打完饭，就会从队伍中离开（出队），而第二个人也就往前走成为了第一个人。来的比较晚的同学就会排在队伍的最后面（表尾），这个过程也成为入队。
不难发现队列的特性：先进先出。
并且，队列的操作只能对队头和队尾进行操作。
结构定义
在这里就使用链表来完成队列这个数据结构好了。那么该怎么定义这个结构呢？
首先我们要能对队头和队尾进行操作，因此必然存在队头节点和队尾节点。然后考虑到我们需要统计到队列的长度，也就是节点的个数。
typedef struct node
{
void* data; //数据域指针
struct node *next; //指向当前结点的下一结点
} Node;
typedef struct Lqueue
{
Node *front; //队头
Node *rear; //队尾
size_t data_size; //数据域内存大小
} LQueue
初始化队列
初始化队列并不难，初始化一个队列，要确定：头节点、尾节点和队列长度。
先把头尾节点的数据设置为0（也就是暂无赋值），并且指定好存储在队列中的元素类型。
初始化时，rear = front=0，当队列不为空时，front指向队列中的第一个元素，rear指向队列中最后一个元素的下一个位置，当队列满时 rear=front，但不一定是位置0。
void InitAQueue(AQueue *Q,size_t data_size) //初始化循环队列
{
Q->data[MAXQUEUE];
Q->front = 0;
Q->rear = 0;
Q->data_size = data_size;
printf("队列创建成功！\n");
}判断队列
插入后rear+1，删除后front+1，但是，无论是删除还是插入，一旦rear或front加一超过了所分配的空间，则让指针指向这片空间的起始位置；设所分配的空间为Maxsize，一旦rear+1，或front+1 =Maxsize, 则rear或front指向起始位置；如上图，当front和rear都在位置3事，此时如果想要插入，则判断3+1=4 与Maxsize 4的关系，相等，则rear=0，这个可以通过取余实现rear=（rear+1）%Maxsize；
因此，循环序列判空的方法是rear = front； 判满的方法是 （rear+1）%Maxsize ==front；
因此，循环序列判空的方法是rear = front； 判满的方法是 （rear+1）%Maxsize ==front；
Status IsEmptyAQueue(AQueue *Q) //判断循环队列是否为空
{
if(Q->front == Q->rear)
{
printf("队列为空！\n");
return TRUE;
}
else
{
printf("队列不为空！\n");
return FLASE;
}
}
入队
进队列步骤：
1.判断队列是否满，即，rear+1是否等于front，若等于则队列已满，不允许进入；
2. 若不满，则将值保存至rear+1的位置 ， 若front =0， rear =3，这是位置3为空，但是判断的3+1 =4，则rear=（rear+1）%4 =0，则rear = front，显示队列已满，所以不能再插入，而其实还有一个空位。
Status EnAQueue(AQueue *Q, void *data) //入循环队列
{
fflush(stdin);
if((Q->rear+1) % MAXQUEUE == Q->front)
{
printf("队列已经满了！\n");
return FLASE;
}
void *addTarget = (Q->data) + (Q->rear)%MAXQUEUE * (Q->data_size);
memcpy(addTarget,data,Q->data_size);
++(Q->rear);
++(Q->len);
printf("(数字也是字符的一种)插入成功！\n");
return TRUE;
}出队
判断队列是否为空，若为空，则出队失败，否则只需将首节点移向下一个位置。
Status DeAQueue(AQueue *Q) //出循环队列
{
if(Q->front == Q->rear)
{
printf("队列为空！\n");
return FLASE;
}
else
{
Q->front = (Q->front + 1) % MAXQUEUE;
printf("队列头元素出队列成功！\n");
return TRUE;
}
}清空队列
使用一个临时指针首先指向头节点，然后遍历整个队列，一边遍历一边free掉节点即可，就像清空链表地操作一样。
void ClearQueue(PQueue queue) {
PNODE P = queue->Front->Next; // 临时指针
PNODE Q = NULL; // 临时指针
queue->Rear = queue->Front; // 使队尾指针指向头节点
queue->Front->Next = NULL;
// 从首节点开始清空
while (P != NULL) {
Q = P;
P = P->Next;
free(Q);
}
printf("清空队列成功...\n");