一、队列的概念及结构
1、概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
2、结构
（1）队列的顺序存储结构
- 入队，不需要移动任何元素，时间复杂度为 O(1) 。
- 出队，所有元素需要往前移动，时间复杂度为 O(N) 。
（2）队列的链表存储结构
首先我们定义两个指针，队头指针指向第一个节点，队尾指针指向尾节点。
- 入队（尾插），时间复杂度为 O(1) 。
- 出队（头删），时间复杂度为 O(1) 。
二、队列的实现
如果使用数组删除队头数据，再挪动数据效率为 O(N)，不适合。 选择用单向链表来完成队列的实现更好，可以发现头删和尾插效率都很高，而双向链表在这里发挥不出很大的作用。
1、创建文件
- test.c（主函数、测试队列各个接口功能）
- Queue.c（队列接口函数的实现）
- Queue.h（队列的类型定义、接口函数声明、引用的头文件）
2、Queue.h 头文件代码
// Queue.h // 链式结构：表示队列 #pragma once #include<stdio.h> #include<stdbool.h> //bool #include<assert.h> // assert #include<stdlib.h> // malloc typedef int QDataType; typedef struct QueueNode // 队列节点结构 { struct QueueNode* next; // 节点指针 QDataType data; // 节点数据 }QueueNode; typedef struct Queue // 队列的链式结构 { QueueNode* head; //队头指针 QueueNode* tail; //队尾指针 }Queue; // 初始化队列 void QueueInit(Queue* pq); // 销毁队列 void QueueDestroy(Queue* pq); // 队尾入队列 void QueuePush(Queue* pq, QDataType data); // 队头出队列 void QueuePop(Queue* pq); // 获取队列头部元素 QDataType QueueFront(Queue* pq); // 获取队列队尾元素 QDataType QueueBack(Queue* pq); // 获取队列中有效元素个数 int QueueSize(Queue* pq); // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 bool QueueEmpty(Queue* pq);
三、Queue.c 中各个接口函数的实现
1、初始化队列
// 初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; }
2、队列的销毁
// 销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur) { QueueNode* next = cur->next; free(cur); cur = next; } cur = NULL; pq->head = pq->tail = NULL; }
3、队尾入队列（尾插）
// 队尾入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); // 动态申请一个节点 newnode->data = x; newnode->next = NULL; // 尾节点next指针置空 if (pq->head == NULL) // 队列为空 { pq->head = pq->tail = newnode; } else // 队列不为空 { pq->tail->next = newnode; pq->tail = newnode; // 更新队尾指针 } }
4、队头出队列（头删）
// 队头出队列 // 写法一： void QueuePop(Queue* pq) { assert(pq); //温柔处理方式： /* if(pq->head == NULL) return; */ //暴力处理方式： assert(!QueueEmpty(pq)); QueueNode* next = pq->head->next; // 记录头节点的直接后继 free(pq->head); // 释放头节点 pq->head = next; // 更新队头指针 if (pq->head == NULL) // 队列中只有一个节点 { pq->tail = NULL; } } // 写法二： void QueuePop(Queue* pq) { assert(pq); //暴力处理方式： assert(!QueueEmpty(pq)); if(pq->head->next == NULL) // 一个节点 { free(pq->head); pq->head = pq->tail = NULL; } else // 多个节点 { QueueNode* next = pq->head->next; // 记录头节点的直接后继 free(pq->head); // 释放头节点 pq->head = next; // 更新队头指针 } }
注意：链表只有一个节点时，要单独处理，否则可能会造成 pq->tail 野指针的情况。
5、获取队列头部元素
// 获取队列头部元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; }
6、获取队列队尾元素
// 获取队列队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
7、获取队列中有效元素个数
// 获取队列中有效元素个数 int QueueSize(Queue* pq) { assert(pq); int n = 0; QueueNode* cur = pq->head; while (cur) { n++; cur = cur->next; } return n; }
如果频繁调用这个接口函数，可以在 QueuePtr 中加一个 size 来记录数据的个数。
8、检查队列是否为空
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 bool QueueEmpty(Queue* pq); { assert(pq); return pq->head == NULL && pq->tail == NULL; }
四、整合代码
// Queue.c #include "Queue.h" // 初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } // 销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur) { QueueNode* next = cur->next; free(cur); cur = next; } cur = NULL; pq->head = pq->tail = NULL; } // 队尾入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); // 动态申请一个节点 newnode->data = x; newnode->next = NULL; // 尾节点next指针置空 if (pq->head == NULL) // 队列为空 { pq->head = pq->tail = newnode; } else // 队列不为空 { pq->tail->next = newnode; pq->tail = newnode; // 更新队尾指针 } } // 队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); QueueNode* next = pq->head->next; // 记录头节点的直接后继 free(pq->head); // 释放头节点 pq->head = next; // 更新队头指针 if (pq->head == NULL) // 队列中只有一个节点 { pq->tail = NULL; } } // 获取队列头部元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } // 获取队列队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } // 获取队列中有效元素个数 int QueueSize(Queue* pq) { assert(pq); int n = 0; QueueNode* cur = pq->head; while (cur) { n++; cur = cur->next; } return n; } // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 bool QueueEmpty(Queue* pq); { assert(pq); return pq->head == NULL && pq->tail == NULL; }
五、测试队列的功能
六、拓展
实际中我们有时还会使用一种队列叫循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
1、空的循环队列
2、满的循环队列
