前言以及队列全部代码（CV工程师点这里）
前言：前面我们学习了链表以及栈的知识，他们都是数据结构中的重要知识点，接下来我们来学习一下队列有关的知识。还是老套路二话不说，先上代码
#include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail\n"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->phead->next ==NULL) { QNode* head = pq->phead; free(head); pq->phead = pq->ptail = NULL; pq->size = 0; } else { QNode* head = pq->phead; pq->phead = pq->phead->next; free(head); pq->size--; } } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return(pq->phead->data); } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; }
一、队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
二、队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
三、代码实现以及详细解释
1. 初步介绍
1. 初始化队列 void QueueInit(Queue* pq);
2. 队列的销毁 void QueueDestroy(Queue* pq);
3. 队列插入元素（尾插） void QueuePush(Queue* pq, QDataType x);
4. 删除队头元素 void QueuePop(Queue* pq);
5. 返回队头元素 QDataType QueueFront(Queue* pq);
6. 返回队尾元素 QDataType QueueBack(Queue* pq);
7. 求队列的长度 int QueueSize(Queue* pq);
8. 判断是否为空 bool QueueEmpty(Queue* pq);
2. 定义结构体，以及栈内数据类型
代码：
#include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue;
3. 初始化队列
代码：
void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; }
4.队列的销毁
代码：
void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }
5. 队列插入元素（尾插）
代码：
void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail\n"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; }
6.删除队头元素
代码：
void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->phead->next ==NULL) { QNode* head = pq->phead; free(head); pq->phead = pq->ptail = NULL; pq->size = 0; } else { QNode* head = pq->phead; pq->phead = pq->phead->next; free(head); pq->size--; } }
7.返回队头元素
代码：
QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return(pq->phead->data); }
8. 返回队尾元素
代码：
QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; }
9.求队列的长度
代码：
int QueueSize(Queue* pq) { assert(pq); return pq->size; }
10. 判断是否为空
代码：
bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; }
