目录

0.前言

1.什么是队列

 2.选择什么结构实现队列

3.用C语言实现队列

3.1用什么可以封装代表一个队列

3.2队列接口的设计

3.3 队列的初始化

3.4 队列的销毁

3.5* 队列的状态分析

3.6 队列的插入

3.7 队列的删除

3.8 队列的大小（有效元素的数目）

3.9判断队列是否为空

3.10 获取队头数据

3.11 获取队尾数据

4.测试实现的队列

---

0.前言

4队列的实现 · onlookerzy123456qwq/data_structure_practice_primer - 码云 - 开源中国 (gitee.com)https://gitee.com/onlookerzy123456qwq/data_structure_practice_primer/tree/master/4%E9%98%9F%E5%88%97%E7%9A%84%E5%AE%9E%E7%8E%B0本文所有代码都已上传至gitee，可以自取。

1.什么是队列

我们想象一个管道，在这个管道运行的时候，比如我们现在要输送石油从新疆到上海，那么这个管道当中，石油是从新疆端 入的，石油是从上海端 出的，并且石油只允许从新疆输入，石油只允许从上海端输出。同时在管道里的石油，肯定是先输入的石油更快到达上海，后面输入的石油是在先输入的石油到达之后，才到达上海（因为先输入的石油是堵在管道前面的，必须先进的先出之后，后进的才能出）。

这个管道就是一个队列。先后输入的石油就是队列里面的元素。

栈是只允许在一端进行插入/删除，而我们的队列与之相反，队列是只允许在一端进行插入，只能在相反的另一端进行删除。

同时队列也是只能先进先出的，后进后出的，先入队列的元素肯定是堵在后入队列的元素的前面，必须先入队列的数据先出队列之后，相对后入的队列才能出队列。

负责插入（入队列）的一端称为队尾，负责删除（出队列）的一端称之为队头。

 2.选择什么结构实现队列

实现队列我们可供选择的有两种结构，一种是顺序表结构，一种是链式结构，在这个效率至上的时代，我们肯定是选择链式结构实现队列！因为队列是只允许在一端插入，另一端删除的，所以我们就需要 头插配尾删（此时顺序表/链表的头部是队尾，尾部是队头） 或者是  头删配尾插（此时此时顺序表/链表的头部是队头，尾部是队尾），而我们的顺序表天然在头部进行插入删除的效率是极低的，效率为O（N），因为需要挪动数据。所以链表结构便成为了不二选择。

我们以单链表的头head 作为队列的队头（出数据），以单链表的尾tail 作为队列的队尾（入数据）：

单链表头删的效率是O（1），但是单链表尾插由于需要找尾，效率会降为O（N），这是这并没有太大的关系，因为我们在用链式结构实现队列的时候，可以一直记录tail尾的位置，即我们在封装Queue的时候，除了记录头节点head的位置，也记录住尾节点tail的位置，每次删除/插入操作的时候，适当更新tail，就不用找尾，此时我们对tail尾部的插入的效率就也是O（1）了。

3.用C语言实现队列

3.1用什么可以封装代表一个队列

我们选择的是一个链式结构作为基础实现队列，所以我们要保存一个单链表，如何代表一个单链表，其实我们只需要记录一个单链表的头head即可。同时为了方便我们进行尾插，我们还需要维护一个单链表的tail指针。

所以队列通过一个链表节点head和tail指针就可代表了。

所以我们定义一个存储队列数据的节点struct Node类，然后对封装的Queue类当中，封装两个节点指针head，tail即可。

//范式类型
typedef int QDataType;//节点
typedef struct QueueNode
{QDataType _data;struct QueueNode* _next;
}QueueNode;//队列
typedef struct Queue
{QueueNode* _head;//队头QueueNode* _tail;//队尾
}Queue;

3.2队列接口的设计

我们要修改的是一个队列Queue q对象，我们就不能做对Queue q的直接传值传参，因为这样的话，就是在调用的函数栈帧当中，拷贝一个相同的Queue tmp_q，并不是这个我们的q。

 所以我们应该传入的是main函数当中Queue q对象的指针，即Queue* pq，你传入的是q对象的指针，这样pq指向的就是我main函数中的q实体了，在Func函数当中指针找到的也是main函数当中的q实体。

所以接口我们这样设计：

//队列相关接口
/*传入一级指针即可：传入(指向[Queue两个指针实体]的指针，可以修改Queue *head *tail实体)*/
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
bool QueueEmpty(Queue* pq);
int  QueueSize(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

3.3 队列的初始化

我们定义出来一个队列类的对象，那这个对象里面的_head和_tail一定是随机值野指针，如果不对之进行初始化，那后续我们对这个队列进行插入删除等操作的时候，灾难性的野指针问题就会暴露出来（非法访问）。

所以每次定义一个队列，我们都要对这个队列对象进行初始化：

void QueueInit(Queue* pq)
{//须传入队列实体assert(pq);pq->_head = NULL;pq->_tail = NULL;
}

3.4 队列的销毁

每次使用完队列，我们不能就不管了，因为堆区申请的空间，需要我们主动释放，在这个队列的实现当中，我们是在堆区里申请了一个一个的节点组成了一个链表，如果不释放的话，那么就会造成内存泄漏，这些堆区空间就会一直被“霸占”着，无法被再使用。

所以每次使用完一个队列，我们都要对之释放清理资源：

void QueueDestroy(Queue* pq)
{//须传入队列实体assert(pq);//依次释放所有的节点QueueNode* cur = pq->_head;while(cur){QueueNode* next = cur->_next;free(cur);cur = next;}//置空,防止野指针pq->_head = NULL;pq->_tail = NULL;
}

3.5* 队列的状态分析

我们分析一下队列在各个状态下，_head _tail成员的实际情况：

队列空的时候，head和tail都是NULL。
在通常情况下，队列_head指向队头的数据节点 ，负责删除更新（头删），_tail指向队尾的数据节点，负责插入更新（尾插）。

再紧接着分析一下队列的插入删除，对_head_tail成员的影响：

对队列插入就是在_tail的后面进行链接新创建的节点，并记录更新_tail为新节点。对队列的删除就是对_head所在位置的节点释放删除，并记录更新_head为原来_head的下一个节点的位置。

但是这样真的就行了吗？入队列，即尾插，真的只更新_tail就行了吗？出队列，即头删，真的只更新_head就行了吗？当然不行！！！

万一现在是空队列，_head和_tail都是NULL空，那你入队列，插入一个数据，此时_head和_tail都需要更新为新节点，不能只顾_tail。万一现在队列只有一个节点，那你删除之后，此时_head和_tail也都想需更新为NULL，不能只顾_head。

3.6 队列的插入

大致思路就是，创建新节点，然后链接到tail后面，并更新tail。

检查队列是合法的（用户传入的是一个有效队列指针）；提前判断一开始队列就是空的特殊情况，此时除了_tail需要更新为新节点，_head也需要更新。

void QueuePush(Queue* pq,QDataType x)
{//须传入队列实体assert(pq);//创建新节点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->_next = NULL;newnode->_data = x;/*插入分两种情况情况一：直接在tail后面链接新节点然后更新tail即可情况二：队列为空，head==tail==NULL，此时需要更新head+tail为新节点指针*/if (pq->_head == NULL)//QueueEmpty(pq){pq->_head = newnode;pq->_tail = newnode;}else {pq->_tail->_next = newnode;pq->_tail = newnode;}
}

3.7 队列的删除

大致思路就是，把_head指向的队头的节点进行释放删除，然后更新_head为下一个节点的位置。

检查队列是合法的（用户传入的是一个有效队列指针）；检查此时队列不为空，为空，即没有有效数据不能进行删除，需要报错；提前判断一开始队列就是只有一个节点的特殊情况，此时除了_tail需要更新为NULL，_head也需要更新，且更新为NULL。

void QueuePop(Queue* pq)
{//传入有效队列assert(pq);//有有效数据，即队列非空才可以删assert(!QueueEmpty(pq));//pq->_head != NULL/*分两种情况情况一：直接删除head节点,然后更新head到next第二个节点的指针情况二：现在只有一个节点,删除该节点后head变成next空节点NULL,此时tail也需更新为NULL,因为现在tail还指向着刚刚删除的节点的空间,出现野指针问题*/QueueNode* next = pq->_head->_next;free(pq->_head);pq->_head = next;if (pq->_head == NULL)//删除到空{pq->_tail = NULL;}
}

3.8 队列的大小（有效元素的数目）

获取当前队列里面一共有多少个有效数据，其实就是看从_head到_tail，这两个节点之间有多少个有效节点数据。思路就是依次从_head往后直至遍历到NULL，统计数量。

int QueueSize(Queue* pq)
{//须传入队列实体assert(pq);//链式结构通常不存节点数目//所以通常进行遍历统计int size = 0;QueueNode* cur = pq->_head;while (cur){cur = cur->_next;++size;}return size;
}

3.9判断队列是否为空

队列为空的时候_head为NULL。

bool QueueEmpty(Queue* pq)
{	//须传入队列实体assert(pq);//队头是空即可return pq->_head == NULL;
}

3.10 获取队头数据

获取队头的数据，即下一个要出队列的队头QueueFront，但是需要判断队列不为空，如果队列为空即没有有效数据的话，那就是需要报错的。

QDataType QueueFront(Queue* pq)
{//传入有效队列实体assert(pq);//必须有数据（队列非空）才能取assert(!QueueEmpty(pq));//Front就是队头head的元素数据return pq->_head->_data;
}

3.11 获取队尾数据

获取队尾的数据，即最近一次插入的队列的队尾QueueBack，但是需要判断队列不为空，如果队列为空即没有有效数据的话，那就是需要报错的。

QDataType QueueBack(Queue* pq)
{//传入有效队列实体assert(pq);//必须有数据（队列非空）才能取assert(!QueueEmpty(pq));//Back就是队尾tail的元素数据return pq->_tail->_data;
}

4.测试实现的队列

任何实现都离不开测试，这里笔者建议大家，不要写一堆之后再测试，应该最好是写一点测一点，写一个接口测试一下，这样可以帮助我们快速的定位问题bug的所在处。这并不是在浪费时间，而是在节省时间。

void QueueTest1()
{Queue q;QueueInit(&q);printf("Queue Size:%d\n", QueueSize(&q));printf("Queue Empty:%d\n", QueueEmpty(&q));QueueDestroy(&q);
}
void QueueTest2()
{Queue q;QueueInit(&q);QueuePush(&q,5);QueuePush(&q, 9);QueuePush(&q, 7);printf("Queue Size:%d\n", QueueSize(&q));printf("Queue Empty:%d\n", QueueEmpty(&q));QueueDestroy(&q);
}
void QueueTest3()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 0);QueuePush(&q, 0);QueuePush(&q, 8);QueuePush(&q, 6);printf("Queue Size:%d\n", QueueSize(&q));printf("Queue Empty:%d\n", QueueEmpty(&q));QueuePop(&q);printf("Queue Size:%d\n", QueueSize(&q));QueueDestroy(&q);
}
void QueueTest4()
{Queue q;QueueInit(&q);QueuePush(&q, 1);printf("Queue Back:%d ", QueueBack(&q));QueuePush(&q, 0);printf("Queue Back:%d ", QueueBack(&q));QueuePush(&q, 0);printf("Queue Back:%d ", QueueBack(&q));QueuePush(&q, 8);printf("Queue Back:%d ", QueueBack(&q));QueuePush(&q, 6);printf("Queue Back:%d ", QueueBack(&q));printf("\n");printf("Queue Size:%d\n", QueueSize(&q));printf("Queue Empty:%d\n", QueueEmpty(&q));//测试具体的遍历栈的过程//数据是先进先出while (!QueueEmpty(&q)){printf("Queue Front:%d Pop\n", QueueFront(&q));QueuePop(&q);}
}
int main()
{//QueueTest1();//QueueTest2();//QueueTest3();QueueTest4();return 0;
}