队列的概念

队列是一种特殊的线性结构
只允许在一端进行插入操作，在另一端进行删除操作，队列具有先进先出FIFO(First In First Out)
入队：进行插入操作，进行插入的一端称为队尾
出队：进行删除操作，进行删除的一端称为队头

队列的实现

因为队列在尾进在头出，如果用顺序表实现，那么出队就需要挪动顺序表的数据，效率低
所以队列用链表实现更好

我们先写一个链表的结构体：

typedef int QueueDataType;
typedef struct QueueNode
{struct QueueNode* next;QueueDataType data;
}QNode;

在主函数中，为了方便，我们定义一个头指针head指向队头和尾指针tail指向队尾

QNode* head = NULL;
QNode* tail = NULL;

如果这么写的话,在设计函数时，就要至少传2个指针，并且为二级指针，这是否的麻烦

所以我们可以再定义一个结构体，将head和tail都放到这个结构体中，那么设计函数时只需要传一个指针就可以了

typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;

这样设计的话，函数中传这个结构体的参数，通过结构体指针就可以改变结构体了，所以也不用传二级指针了

这里在结构体内还定义了一个int size，这是表示队列的长度，这个设计并非多余，在后面的实现中就会发现这个size能提高效率

这里的队列实现需要定义2个结构体，这是在之前的数据结构中没有出现的

初始化

void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}

将head和tail都初始化为空，size为0

销毁

void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* nex = cur->next;free(cur);cur = nex;}pq->head = NULL;pq->tail = NULL;pq->size = 0;
}

入队

入队，首先就是开辟一个新节点

QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;

然后就是入队了，在队尾入队
这里如果head==NULL，就说明当前队列还没有元素head和tail都为空
所以让head指向这个第一个节点，同时这个节点也是自己的尾，tail也应指向这个节点

pq->head = pq->tail = newnode;

如果head不为空，就说明当前队列中有元素，直接在tail后面插入新节点即可

void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}pq->size++;}

出队

出队，首先应用断言判断一下队列是否为空

assert(!QueueEmpty(pq));

在队头出队

首先用next指针保存head->next，然后就可以free掉head了，然后再将head指向新的头next

QNode* next = pq->head->next;
free(pq->head);
pq->head = next;

在这里会发现，如果队列只要一个节点，next为空，然后虽然能够让head为空，但tail不会被改变，所以我们需要改一下：

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;}

所以最终代码：

void QueuePop(Queue* 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--;
}

判空

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

队列长度

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

这里就最能看出在结构体中定义size的好处了
如果不去定义，那么在这里求长度就会遍历一遍队列，导致效率低

而之前定义了size，这里直接返回size即可，效率高

返回队头元素

QueueDataType QueueFront(Queue* pq)
{assert(pq);return pq->head->data;
}

一般通过QueueFront和QueuePop2个函数来得到队列中的数据

打印队列中数据：

	while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}

返回队尾元素

QueueDataType QueueBack(Queue* pq)
{assert(pq);return pq->tail->data;
}