队列的概念与结构

队列是一种特殊的线性结构，数据只能在一端插入，数据也只能在另一端进行删除。插入数据的那一端称之为队尾，插入数据的动作称之为入队。删除数据的那一端称之为队头，删除数据的动作称之为出列。队列遵守的是FIFO原则（Frist In First Out），即先进先出原则。

队列具体实现结构比较灵活，只要遵循FIFO原则即可。顺序表的方式实现，虽然尾插数据方便，头删的代价较大，故不推荐。单链表的方式实现，头删数据方便，只需要添加一个记录尾结点的指针，进行尾插数据的效率也还可以。所以本篇文章将以单链表的方式来实现队列。

队列的实现

队列的定义

首先，我们需要定义的是链式结构的队列，即单链表为底层实现的。所以需要定义单链表结构来存储数据。然后，定义队列，队列里需要定义两个指向单链表的指针，一个是指向单链表头结点的指针，另一个则用来保存尾结点地址的指针。最后，还需定义一个记录当前队列元素个数的变量，用于遍历队列和判空。

typedef int QueueDataType;typedef struct QueueNode
{struct QueueNode* next;QueueDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;int size;
}Queue;

初始化队列

首先，断言判断一下指针合法性。然后，需要将队列内两个指针变量初始化。最后，将记录队列有效元素个数的变量初始化一下。

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

队列销毁

首先，断言一下指针有效性。然后，依次释放每个结点。最后释放最后一个结点时，把tail和head置空，size置零。

// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);//释放结点while (q->head){QueueNode* next = q->head->next;if (q->tail != q->head){free(q->head);q->head = next;}else{//避免野指针free(q->head);q->head=q->tail = NULL;}}//手动置零q->size = 0;
}

队列判空

由于在定义队列时，增加了额外的记录当前有效数据个数的变量，所以这里直接返回该变量与0比较的值即可。

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q)
{return q->size == 0;
}

数据入队

首先，依旧断言判断指针有效性。其次，就是动态开辟结点，并对新节点初始化。然后，进行头插操作，记得第一次插入时，需要单独判断两个指针同时指向新结点。最后，记得让tail指针指向最后一个结点和size++。

// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{//断言判断指针有效性assert(q);//开辟结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newnode){perror("malloc fail\\n");return;}newnode->next = NULL;newnode->data = data;//插入数据//空队列插入数据if (q->head == NULL){q->head = q->tail = newnode;}//非空队列插入数据else{q->tail->next = newnode;q->tail = newnode;}q->size++;
}

数据出列

首先，当队列为空时，不能进行删除操作，所以断言判断一下是否为空队列。然后，就是头删链表的操作，需要注意的是当只剩一个结点时，对tail进行特殊处理避免野指针。最后，就是让记录有效元素的size–一下。

// 队头出队列
void QueuePop(Queue* q)
{assert(q);//空队列无法删除数据assert(!QueueEmpty(q));//只有一个数据if (q->head == q->tail){free(q->head);q->head = q->tail = NULL;}else{//先保存下一个结点QueueNode* next = q->head->next;free(q->head);q->head = next;}//记录当前数据个数q->size--;}

获取有效数据个数

由于在定义队列时，定义了一个记录当前有效元素个数的变量，所以这里直接返回该变量当前的值即可。

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);return q->size;
}

获取队头数据

直接返回第一个结点的data即可。

// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->head->data;
}

获取队尾数据

直接返回tail指针指向的链表存放的数据即可。

// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->tail->data;}

队列的特点

由于队列是FIFO的原则，这就类似于去食堂排队打饭，先排队的就一定先吃上饭。而队尾的就得等先排队的打完饭了，才有机会吃饭。所以队列无论是变入列变出列，还是全部入列后再出列，结果是一样的。这和栈的LIFO原则有些许不同。