目录
后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！
《数据结构(C语言版)》实战项目之队列（链式）的功能实现
——By 作者：新晓·故知
一、完整源码：
完整源码如下，欢迎复制测试指正！
队列（链式）的功能实现测试示例：
编辑
完整源码：
Test.c:
#include "Queue.h" //队列（链式）的功能实现 //初始化队列测试 void TestQueue1() { Queue q; QueueInit(&q); ////1.一个一个创建数据 //QueuePush(&q, 1); //QueuePush(&q, 2); //QueuePush(&q, 3); //QueuePush(&q, 4); //2.使用循环创建数据 for (int i = 1; i < 6; ++i) { QueuePush(&q, i); } while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); } //判断队列大小测试 void TestQueue2() { Queue q; QueueInit(&q); //2.使用循环创建数据 for (int i = 1; i < 6; ++i) { QueuePush(&q, i); printf("%d ", QueueFront(&q)); QueuePop(&q); } //2.使用循环创建数据 for (int i = 1; i < 6; ++i) { QueuePush(&q, i); /*printf("%d ", QueueFront(&q)); QueuePop(&q);*/ } printf("\n"); //判断队列大小 size_t size=QueueSize(&q); printf("队列的大小为：%u", size); } //队头查找打印测试 void TestQueue3() { Queue q; QueueInit(&q); //2.使用循环创建数据 for (int i = 1; i < 6; ++i) { QueuePush(&q, i); printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); for (int i = 1; i < 6; ++i) { QueuePush(&q, i); /*printf("%d ", QueueFront(&q)); QueuePop(&q);*/ } printf("%d ", QueueFront(&q)); } //队尾查找打印测试 void TestQueue4() { Queue q; QueueInit(&q); //2.使用循环创建数据 for (int i = 1; i < 6; ++i) { QueuePush(&q, i); printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); for (int i = 1; i < 6; ++i) { QueuePush(&q, i); /*printf("%d ", QueueFront(&q)); QueuePop(&q);*/ } printf("%d ", QueueBack(&q)); } //入队+出队测试 void TestQueue5() { Queue q; QueueInit(&q); //2.使用循环创建数据 for (int i = 1; i < 6; ++i) { //入队 QueuePush(&q, i); printf("%d ", QueueFront(&q)); //出队 QueuePop(&q); } printf("\n"); } //销毁队列测试 void TestQueue6() { Queue q; QueueInit(&q); //2.使用循环创建数据 for (int i = 1; i < 6; ++i) { QueuePush(&q, i); printf("%d ", QueueFront(&q)); //删除队头 QueuePop(&q); } printf("\n"); QueueEmpty(&q); QueueDestroy(&q); printf("%d ", QueueFront(&q)); } int main() { TestQueue1(); TestQueue2(); TestQueue3(); TestQueue4(); TestQueue5(); //TestQueue6(); return 0; }
Queue.c:
#include "Queue.h" //队列（链式）的功能实现 //队列的功能函数 //初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } //销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } //插入（进队） void QueuePush(Queue* pq, QDataType x) { assert(pq); //开辟新结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { assert(pq->head == NULL); pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } //删除（出队） void QueuePop(Queue* pq) { assert(pq); assert(pq->head && pq->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; } } //判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); //return pq->head == NULL && pq->tail == NULL; return pq->head == NULL; } //队列大小 //size_t即unsigned int，包含在头文件 size_t QueueSize(Queue* pq) { assert(pq); QNode* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; //如果经常使用size，可以在结构体中定义size， //然后初始化为0，就不用在使用while计算 //这样就不用遍历，降低时间复杂度 } //队头 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; } //队尾 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->tail); return pq->tail->data; }
Queue.h:
#pragma once //队列（链式）的功能实现 #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; //定义第二个结构体的原因是因为要方便队尾的插入，删除的管理 typedef struct Queue { QNode* head; QNode* tail; //size_t size; //若经常使用，可在此增加一个计数 }Queue; //初始化队列 void QueueInit(Queue* pq); //销毁 void QueueDestroy(Queue* pq); //插入（进队） void QueuePush(Queue* pq, QDataType x); //删除（出队） void QueuePop(Queue* pq); //判断队列是否为空 bool QueueEmpty(Queue* pq); //队列大小 size_t QueueSize(Queue* pq); //size_t即unsigned int，包含在头文件 //队头 QDataType QueueFront(Queue* pq); //队尾 QDataType QueueBack(Queue* pq);
二、队列（链式）的功能实现分析：
1.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
编辑
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
编辑
2.队列的实现功能函数：
链式结构：表示队列
（1）初始化队列
//初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; }
（2）销毁队列
//销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; }
（3）插入（进队）
//插入（进队） void QueuePush(Queue* pq, QDataType x) { assert(pq); //开辟新结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { assert(pq->head == NULL); pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } }
（4）删除（出队）
//删除（出队） void QueuePop(Queue* pq) { assert(pq); assert(pq->head && pq->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; } }
（5）判断队列是否为空
//判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); //return pq->head == NULL && pq->tail == NULL; return pq->head == NULL; }
（6）判断队列大小
//队列大小 //size_t即unsigned int，包含在头文件 size_t QueueSize(Queue* pq) { assert(pq); QNode* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; //如果经常使用size，可以在结构体中定义size， //然后初始化为0，就不用在使用while计算 //这样就不用遍历，降低时间复杂度 }
（7）队头
//队头 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; }
（8）队尾
//队尾 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->tail); return pq->tail->data; }
销毁队列测试：
编辑
扩展了解：
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
编辑
编辑
