什么是队列，如何实现？

news/2024/4/27 8:42:51/文章来源:https://blog.csdn.net/Claffic/article/details/129689055

欢迎来到 Claffic 的博客 💞💞💞

“海色温柔，波浪缓慢，似乎在静静期待着新的一天。”

前言：
上期我们讲了栈，它的特点是“后入先出”。这次我们再来学习一个新的数据结构：队列，它的特点是“先入先出，后入后出”，准备好了吗？开始！

Part1: 何为队列

1.队列的概念

队列队列，顾名思义，就像排队买饭，排在前面的人买到饭先走，排到后面的人需要等待... ...

下面是队列的正经概念：

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出原则(First In First Out) 。

进行插入操作的一端称为队尾，

进行删除操作的一端称为队头。

嗯，还是蛮好理解的。

2.队列的结构

它的结构也很清晰了：

我是图示

Part2: 队列的实现

1.前期准备

1.1创建项

不解释：

Queue.h：头文件，声明所有函数；

Queue.c：源文件，实现各函数；

Test.c： 源文件，主函数所在项，可调用各函数。

1.2队列结构

仍然是那个问题：用什么结构来实现队列较好？

数组：？删除元素要整体移动，时间复杂度高，且动态扩容比较麻烦，不推荐；

链表：插入删除数据后无需修改中间部分的元素，方便在队头和队尾操作，推荐。

那么选双链表还是单链表呢？

若选择双链表，的却方便找尾，但是仅仅为了找尾方便而选择它，未免会显得臃肿；

选择单链表呢，轻巧简洁，只需解决找到尾部的问题即可，有一个巧妙的方法就是：

在队列的结构中定义尾指针。

我们捋一遍：

就队列的整体来说：需要首尾指针和大小（长度）；

就队列中的一个结点来说：需要下一个结点的指针和要存储的数据。

欸？相比栈来说，是不是结构更加复杂了？

是的，这意味着要多定义一个结构体，两个结构体之间是包含关系：

我是图示

上代码：

typedef int QDataType;
//队列中的结点
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;
//队列整体
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;

1.3队列初始化

要从整体上把握，把首尾指针初始化为空，大小初始化为 0 即可：

// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}

2.功能实现

2.1队头出队列

队头出队列，队列中是一定至少有一个结点的，但其实还是要分两种情况考虑的：

一是只有一个结点，直接把这个结点释放掉，再将首尾置空即可；

二是有两个及以上个结点，除了释放头部的结点，还需要把队头指针指向下一个结点；

最后莫忘大小减一。

// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);//pq->head = NULL;pq->head = next;}pq->size--;
}

2.2队尾入队列

要入队列，首先要先申请一个新的结点（注意是结点，不是队列）；

再申请完并初始化后，就需要插入了：

也是两种情况：

一是链表为空，此时只要将首尾指针修改为新结点指针即可；

二是链表不为空，就要用到尾指针，将尾结点的下一个结点修改为新结点，并且更新尾结点指针；

最后莫忘大小加一。

// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* tailNode = (QNode*)malloc(sizeof(QNode));if (tailNode == NULL){perror("malloc fail");return;}tailNode->next = NULL;tailNode->data = x;if (pq->head == NULL){pq->head = pq->tail = tailNode;}else{pq->tail->next = tailNode;pq->tail = tailNode;//掉}pq->size++;
}

2.3获取队列头部元素

进行了插入操作，当然要看看数据怎么样啦

这个比较简单，直接返回头部数组即可

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head && pq->tail);return pq->head->data;//NULL
}

2.4获取队列尾部元素

同上：

// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head && pq->tail);return pq->tail->data;
}

2.5获取队列中有效元素个数

还记得之前定义的 size 吗？
在这里它就展现出重要作用了：

// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2.6判断队列是否为空

为空返回非 0 ，不是空就返回 0；

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* pq)
{return pq->size == 0;
}

2.7销毁队列

思路就是把整个队列遍历一遍，释放每个结点，再把首尾指针置空，大小归 0 即可：

// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){free(cur);cur = cur->next;}pq->head = pq->tail = NULL;pq->size = 0;
}

代码已上传至我的gitee

拿走不谢~