数据结构（队列）

什么是队列？

• 队列和栈类似，也是一类特殊的线性表。特殊之处也是在于操作上。
• 队列：只允许在一端进行插入数据操作（入队），在另一端进行删除数据操作（出队）的特殊的线性表。
• 具有先进先出，后进后出的特点。
• 进行插入操作（入队）的一端称为队尾。进行删除操作（出队）的一端称为队头。

队列的意义（作用）

• 

队列的实现

• 和栈类似，也有两种实现方式。一种是数组，也就是顺序表，一种是链表。

• 两种方式都是可以的，不过相比之下，链表更优一些。

• 因为队列是在队头出数据，也就是头部删除数据，那么顺序表要删除头部数据需要一个个的移动数据进行覆盖。所以我们优先选择链表实现。

• 链表类型的选择

• 

实现代码

• 头文件.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int QDateType;
typedef struct QueueNode
{struct QueueNode* next;QDateType date;
}QNode;typedef struct Queue
{QNode * head;QNode * tail;int size;
}Que;//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);//入队（尾部插入数据）
void QueuePush(Que* pq,QDateType x);
//出队（头部删除数据）
void QueuePop(Que* pq);//获得队头节点的值
QDateType QueueFront(Que* pq);
//获得队尾节点的值
QDateType QueueBack(Que* pq);//判断队列是否为空
bool QueueEmpty(Que* pq);
//获得队列的长度（有效元素个数）
int QueueSize(Que* pq);

• 函数实现文件.c

#include "Queue.h"//队列初始化
void QueueInit(Que* pq)
{assert(pq);pq->head=pq->tail=NULL;pq->size=0;
}
//队列销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur=pq->head;while(cur){QNode *next=cur->next;free(cur);cur=next;}pq->head=pq->tail=NULL;pq->size=0;
}//入队（尾部插入数据）
void QueuePush(Que* pq,QDateType x)
{assert(pq);QNode *newnode=(QNode*) malloc(sizeof (QNode));if(newnode==NULL){perror("malloc failed");exit(-1);}newnode->next=NULL;newnode->date=x;if(pq->tail==NULL){pq->head=pq->tail=newnode;}else{pq->tail->next=newnode;pq->tail=newnode;}pq->size++;
}
//出队（头部删除数据）
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if(pq->head->next==NULL){free(pq->head);pq->head=pq->tail=NULL;}else{QNode *next=pq->head->next;free(pq->head);pq->head=next;}pq->size--;}//获得队头节点的值
QDateType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->date;
}
//获得队尾节点的值
QDateType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->date;
}//判断队列是否为空
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head==NULL;
}
//获得队列的长度（有效元素个数）
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}

函数解析

• 队列结构

typedef int QDateType;
typedef struct QueueNode
{struct QueueNode* next;QDateType date;
}QNode;typedef struct Queue
{QNode * head;QNode * tail;int size;
}Que;

• 队列初始化

//队列初始化
void QueueInit(Que* pq)
{assert(pq);pq->head=pq->tail=NULL;pq->size=0;
}

• 队列销毁

//队列销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur=pq->head;while(cur){QNode *next=cur->next;free(cur);cur=next;}pq->head=pq->tail=NULL;pq->size=0;
}

• 入队（尾部插入数据）

//入队（尾部插入数据）
void QueuePush(Que* pq,QDateType x)
{assert(pq);QNode *newnode=(QNode*) malloc(sizeof (QNode));if(newnode==NULL){perror("malloc failed");exit(-1);}newnode->next=NULL;newnode->date=x;if(pq->tail==NULL){pq->head=pq->tail=newnode;}else{pq->tail->next=newnode;pq->tail=newnode;}pq->size++;
}

• 出队（头部删除数据）

//出队（头部删除数据）
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if(pq->head->next==NULL){free(pq->head);pq->head=pq->tail=NULL;}else{QNode *next=pq->head->next;free(pq->head);pq->head=next;}pq->size--;}

• 获得队头节点的值

//获得队头节点的值
QDateType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->date;
}

• 这个不多说。

• 获得队尾节点的值

//获得队尾节点的值
QDateType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->date;
}

• 不多说了。

• 判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head==NULL;
}

• 连头都没有，那是不是空的？或者pq->tail==NULL。也可以判空。

• 获得队列的长度（有效元素的个数）

//获得队列的长度（有效元素个数）
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}

• 不多说，每次插入删除数据，都会带上它变化的。它就是用来记录元素个数的。

• 那么队列的基本知识就基本完成了。