【数据结构】C语言实现队列

ゝ一世哀愁。 2024-04-22 04:39 78阅读 0赞

**目录**

前言

1. 队列

1.1 队列的概念

1.2 队列的结构

2. 队列的实现

2.1 队列的定义

2.2 队列的初始化

2.3 入队

2.4 出队

2.5 获取队头元素

2.6 获取队尾元素

2.7 判断空队列

2.8 队列的销毁

3. 队列完整源码

Queue.h

Queue.c

--------------------

>  *  ?个人主页：[库库的里昂][Link 1]
>  *  ?C/C++领域新星创作者
>  *  ?欢迎 ?点赞✍评论⭐收藏
>  *  ✨收录专栏：[数据结构与算法][Link 2]
>  *  ?希望作者的文章能对你有所帮助，有不足的地方请在评论区留言指正，大家一起学习交流！?

#### 前言 ####

> 在前几期的学习中，我们认识了[顺序表][Link 3]、链表和栈这三种线性表，而在本期学习中，我们将会认识别的线性表。跟随我们的脚本，看看队列有怎样的特点。

#### 1. 队列 ####

##### 1.1 队列的概念 #####

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

*  入队列：进行插入操作的一端称为队尾
 *  出队列：进行删除操作的一端称为队头

##### 1.2 队列的结构 #####

![120889b9386b4b22be61b7392719eaf1.png][]

#### 2. 队列的实现 ####

![3c0b52007a144c45aa9acca26d28412e.png][]

##### 2.1 队列的定义 #####

> 在入队时相当于尾插，我们可以定义一个尾指针来记录尾的位置。这就使我们传指针时，要传递两个指针，我们可以把指针放到结构体中，这样在插入第一个时也可以解决要传递二级指针的问题。
> 
> 定义尾指针可以避免每次尾插时要遍历一遍链表。

typedef int QDateType;
    
    typedef struct QueueNode
    {
    	QDateType val;
    	struct QueueType* next;
    }QNode;
    
    typedef struct Queue
    {
    	QNode* phead;
    	QNode* ptail;
    	int size;
    }Queue;

##### 2.2 队列的初始化 #####

这里的 size 用来记录队列中数据的个数。

void QueueInit(Queue* pq)
    {
    	assert(pq);
    
    	pq->phead = pq->ptail = NULL;
    	pq->size = 0;
    }

##### 2.3 入队 #####

入队相当于尾插，在入队时我们要考虑链表是否为空。

void QueuePush(Queue* pq, QDateType x)
    {
    	assert(pq);
    
    	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    	if (newnode == NULL)
    	{
    		perror("malloc fail");
    		return;
    	}
    	newnode->next = NULL;
    	newnode->val = x;
    
    	if (pq->ptail == NULL)
    	{
    		pq->phead = pq->ptail = newnode;
    	}
    	else
    	{
    		pq->ptail->next = newnode;
    		pq->ptail = newnode;
    	}
    	pq->size++;
    }

##### 2.4 出队 #####

出队相当于头删,与之前不同的是，当我们删除最后一个节点，还要记得处理尾指针。

void QueuePop(Queue* pq)
    {
    	assert(pq);
    	assert(pq->phead);
    
    	QNode* del = pq->phead;
    	pq->phead = pq->phead->next;
    	free(del);
    	del = NULL;
    	if (pq->phead == NULL)
    	{
    		pq->ptail = NULL;
    	}
    	pq->size--;
    }

##### 2.5 获取队头元素 #####

队头元素就是头指针指向的节点的数据域。

QDateType QueueFront(Queue* pq)
    {
    	assert(pq);
    	assert(pq->phead);
    
    	return pq->phead->val;
    }

##### 2.6 获取队尾元素 #####

我们通过尾指针可以直接找到队尾，不用遍历链表。

QDateType QueueBack(Queue* pq)
    {
    	assert(pq);
    	assert(pq->phead);
    
    	return pq->ptail->val;
    }

##### 2.7 判断空队列 #####

利用bool的函数判断队列是否为空，当尾指针为空时，返回true；当尾指针不为空时，返回false。

bool QueueEmpty(Queue* pq)
    {
    	assert(pq);
    
    	return pq->phead == NULL;
    }

##### 2.8 队列的销毁 #####

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

#### 3. 队列完整源码 ####

##### Queue.h #####

#include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    typedef int QDateType;
    
    typedef struct QueueNode
    {
    	QDateType val;
    	struct QueueType* next;
    }QNode;
    
    typedef struct Queue
    {
    	QNode* phead;
    	QNode* ptail;
    	int size;
    }Queue;
    
    void QueueInit(Queue* pq);
    
    void QueueDstroy(Queue* pq);
    
    void QueuePush(Queue* pq, QDateType x);
    
    void QueuePop(Queue* pq);
    
    QDateType QueueFront(Queue* pq);
    
    QDateType QueueBack(Queue* pq);
    
    bool QueueEmpty(Queue* pq);
    
    int QueueSize(Queue* pq);

##### Queue.c #####

#include"Queue.h"
    
    void QueueInit(Queue* pq)
    {
    	assert(pq);
    
    	pq->phead = pq->ptail = NULL;
    	pq->size = 0;
    }
    
    void QueueDstroy(Queue* pq)
    {
    	assert(pq);
    
    	QNode* cur = pq->phead;
    	while (cur)
    	{
    		QNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	pq->phead = pq->ptail = NULL;
    	pq->size = 0;
    }
    
    void QueuePush(Queue* pq, QDateType x)
    {
    	assert(pq);
    
    	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    	if (newnode == NULL)
    	{
    		perror("malloc fail");
    		return;
    	}
    	newnode->next = NULL;
    	newnode->val = x;
    
    	if (pq->ptail == NULL)
    	{
    		pq->phead = pq->ptail = newnode;
    	}
    	else
    	{
    		pq->ptail->next = newnode;
    		pq->ptail = newnode;
    	}
    	pq->size++;
    }
    
    void QueuePop(Queue* pq)
    {
    	assert(pq);
    	assert(pq->phead);
    
    	QNode* del = pq->phead;
    	pq->phead = pq->phead->next;
    	free(del);
    	del = NULL;
    	if (pq->phead == NULL)
    	{
    		pq->ptail = NULL;
    	}
    	pq->size--;
    }
    
    QDateType QueueFront(Queue* pq)
    {
    	assert(pq);
    	assert(pq->phead);
    
    	return pq->phead->val;
    }
    
    QDateType QueueBack(Queue* pq)
    {
    	assert(pq);
    	assert(pq->phead);
    
    	return pq->ptail->val;
    }
    
    bool QueueEmpty(Queue* pq)
    {
    	assert(pq);
    
    	return pq->phead == NULL;
    }
    
    int QueueSize(Queue* pq)
    {
    	assert(pq);
    
    	return pq->size;
    }

> 本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。

![ce88b0d0b33641dd8000eb7fef9b3bcd.png][]

[Link 1]: https://blog.csdn.net/m0_68662723
[Link 2]: http://t.csdnimg.cn/wUE8D
[Link 3]: https://so.csdn.net/so/search?q=%E9%A1%BA%E5%BA%8F%E8%A1%A8&spm=1001.2101.3001.7020
[120889b9386b4b22be61b7392719eaf1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/a7fa78e7b87943868b9acf5601da74a4.png
[3c0b52007a144c45aa9acca26d28412e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/44432109748c4fb484497b67f7dda00e.png
[ce88b0d0b33641dd8000eb7fef9b3bcd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/32c1d671bb514965be34ed8d30e64430.png