数据结构漫游记：队列的动态模拟实现(C语言)

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！

我的博客：yuanManGan

我的专栏：C++入门小馆 C言雅韵集数据结构漫游记闲言碎语小记坊题山采玉

队列的理解：

基础数据结构的选取：

队列的模拟实现

队列的结构的定义

队列的初始化

入队

判空

出队

获取队头元素

获取队尾元素

获取元素个数

销毁队列

测试代码

总结：

队列的理解：

队列就跟排队吃饭一样，先排到的人先走，后来的人只能在队尾慢慢排。

我们类比于栈，发现我们的队列它只能从一端入数据，一端出数据。

它依然是一个顺序表，在逻辑结构上是顺序存储，而在物理结构就不一定了。

基础数据结构的选取：

还是和栈一样的问题，我们该使用数组还是链表来模拟实现这个数据结构呢？

先来看看数组：

如果我们在数组一端当作队尾一端当作队头。但是我们了解到数组在头部进行操作的时间复杂度都是O(n)，不复合我们对时间复杂度的预期，那我们将队尾和队头互换呢，还不是要对数组的头部进行操作，这样看来数组用来实现队列不是一个好选择。

那我们来试试链表：

同样的我们将头结点视作队头，尾结点视为队尾，发现无论我们以那个结点为头，那个结点为尾，我们始终逃不掉要对尾结点进行操作，要么尾插要么尾删。有没有什么办法能够让尾部进行操作的时间复杂度降到O(1)呢？

你别说还真有如果我们定义一个指针一直指向尾结点呢，之前我们实现链表时都有这个想法，但因为尾部进行删除时指向尾结点的指针不能找到他的前一个结点，但我们如果实现队列，根本不需要对尾部进行删除操作，所以我们定义一个始终指向尾结点的指针，然后进行尾插操作很显然时间复杂度就降到了O(1)了。

队列的模拟实现

队列的结构的定义

因为队列里面有两个指针，一个指向头结点，一个指向尾结点，我们得先定义结点的结构体，然后两个指针在队列的结构体之中。

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode

这里定义了一个结点类型是重命名为QNode

然后定义队列的结构

// 队列的结构 
typedef struct Queue
{QNode* front;QNode* rear;
}Queue;

队列的初始化

我们得将队列里面的两个指针先置为空。还得判断不能传入空指针。

// 初始化队列 
void QueueInit(Queue* q)
{assert(q);q->rear = q->front = NULL;
}

入队

入队就是向尾结点加入数据，那如果链表为空呢，我们得特判，让首尾结点都指向新结点

void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* tmp = (QNode*)malloc(sizeof(QNode));if(tmp ==NULL) {	perror("malloc失败\n");exit(1);}tmp->data = data;tmp->next = NULL;if (q->front == NULL) q->front = q->rear = tmp;else{q->rear->next = tmp;q->rear = q->rear->next;}
}

最后要让尾结点等于新的尾结点，不然会死循环

判空

判空这个操作也很简单，当头结点或者是尾结点指向空的时候队列就是空的

bool QueueEmpty(Queue* q)
{assert(q);return q->front == NULL;
}

出队

出队就是删除头结点，如果只有一个结点的时候，就得让头指针和尾指针指向NULL，如果没有结点，就不能进行这个操作就assert一下就好了。

void QueuePop(Queue* q)
{assert(!QueueEmpty(q));if (q->front == q->rear){free(q->front);q->front = q->rear = NULL;}else {QNode* tmp = q->front;q->front = q->front->next;free(tmp);}}

注意删除的时候要用一个变量来暂时接收一下头结点的下一个结点的地址，不然释放了头结点就找不到下一个结点了，对释放了的指针解引用是野指针的行为。

获取队头元素

获取队头和队尾很简单，但要记得assert一下。

QDataType QueueFront(Queue* q)
{assert(!QueueEmpty(q));return q->front->data;
}

获取队尾元素

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(!QueueEmpty(q));return q->rear->data;
}

获取元素个数

我们如果用遍历来实现获取元素个数，那么时间复杂度就又成了O(n)呢，如果这个操作执行的次数少到也无妨，但如果执行的次数多我还是建议定义结构的时候多定义一个变量size，然后初始化，入队，出队时多进行一下操作即可。

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

销毁队列

最后一个销毁队列，这个没办法，只能遍历链表呢

void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur){QNode* next = cur->next;free(cur);cur = next;}q->rear = q->front = NULL;q->size = 0;
}

测试代码

#include"queue.h"void test01()
{Queue pq;QueueInit(&pq);for (int i = 1; i <= 10; i++){QueuePush(&pq, i);}while (QueueSize(&pq))//!QueueEmpty(&pq){printf("队头：%d   队尾：%d\n", QueueFront(&pq), QueueBack(&pq));QueuePop(&pq);}QueueDestroy(&pq);
}
int main()
{test01();return 0;
}

结果