【数据结构】带你深度理解队列

缺乏、安全感 2024-04-25 20:03 76阅读 0赞

![21f2e355e9ce7c3360f4a1091e72707b.gif][]

**目录**

一. 队列的基本概念?

二. 队列实现方法的选择?

2.1 引入

2.2 选择

三. 接口的实现✈

3.1 队列的声明

3.2 初始化和销毁

3.3 入队

3.4 出队

3.5 求队头元素

3.6 求队尾元素

3.7 判空

3.8 求队列的元素个数

3.9 总结

四. 完整代码及效果展示?

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

### 一. 队列的基本概念? ###

队列和我们之前学习的栈一样，它也是一种特殊的线性表。它只允许在一端插入数据，在另一端删除数据，不允许对中间的元素进行操作，因而也不支持随机访问。队列具有先进先出的特性FIFO（(First In First Out）。

> **入队：** 队列 的插入操作叫做入队，插入数据的一端称作队头  
> **出队：** 队列 的删除操作叫做出队，删除数据的一端称作队尾

我们结合动图来理解队列的先进先出：![8da57cfb54e744ab98a55d61619159ce.gif][]

### 二. 队列实现方法的选择? ###

#### 2.1 引入 ####

在上次栈的实现中，我们说到可以用顺序存储结构和链式存储结构来表示栈。经过之前我们的分析，我们选择了使用顺序表来实现栈，这是由于栈的插入删除操作完美适配顺序表尾插尾删效率高的特性。

> 有关两种方式的优缺点及比较，详细请参照往期文章：
> 
> [【数据结构】带你深度理解栈][Link 1]

#### 2.2 选择 ####

由于队列需要在两端进行操作，而顺序表在头部的操作效率很低，需要移动大量数据，直接pass掉。我们本期将采用单链表的形式来实现队列。特别的，为了提高单链表尾插的效率，除了必要的头指针我们又定义了一个尾指针指向链表的尾部，大幅提高了单链表尾插的效率。当然，实现队列的方式多种多样，并不是只能用单链表来实现队列。

### ![811d1628ac9a429c8c46551998b7cd41.gif][] ###

### 三. 接口的实现✈ ###

#### 3.1 队列的声明 ####

> 本文我们采用带有头尾指针的 单链表来实现队列，队列的结构体的声明如下：

//单链表的结点
    typedef int QueueDataType;
    typedef struct QueueNode
    {
    	QueueDataType data;
    	struct QueueNode* next;
    }QueueNode;
    
    //队列结构体
    typedef struct Queue
    {
    	QueueNode* first;   //队列头
    	QueueNode* tail;    //队列尾
    }Queue;

老样子，我们不直接指定数据的类型，而是将类型重定义为STDataType，这样做有利于提高代码的可维护性。

#### 3.2 初始化和销毁 ####

在我们使用队列结构进行操作之前需要对其进行初始化，当我们不再使用它是要对它进行销毁，具体代码如下：

//初始化队列
    void QueueInit(Queue* pq)
    {
    	assert(pq);
    	pq->first = pq->tail = NULL;//空队列，队头队尾指向空
    }
    
    //销毁队列
    void QueueDestroy(Queue* pq)
    {
    	assert(pq);
    	QueueNode* cur = pq->first;
    	//销毁每个结点
    	while (cur)
    	{
    		QueueNode* next = cur->next;//先把下一个结点的位置保存起来，避免销毁后找不到
    		free(cur);
    		cur = next;
    	}
    	pq->first = pq->tail = NULL;//队头队尾置空
    }

#### 3.3 入队 ####

由于队列只允许在固定的一端插入，我们又将链表尾当做队尾，因此入队就是尾插。在没有尾指针之前，我们还要先找到链表尾，但我们现在有了尾指针，一切都方便起来了。效果和代码如下：![e6c7096506844026992eaa3ff8d608bb.gif][]

//创建结点
    static QueueNode* CreatNode(QueueDataType x)
    {
    	QueueNode* ret=(QueueNode*)malloc(sizeof(QueueNode));
    	if (ret == NULL)
    	{
    		printf("%s", strerror(errno));
    		exit(-1);
    	}
    	ret->data = x;
    	ret->next = NULL;
    	return ret;
    }
    
    //入队
    void QueueInsert(Queue* pq, QueueDataType x)
    {
    	assert(pq);
    	QueueNode* newnode = CreatNode(x);
    	//为空队列
    	if (pq->tail == NULL)
    	{
    		pq->first = pq->tail = newnode;
    	}
    	else
    	{
    		//在队尾插入
    		pq->tail->next = newnode;
    		pq->tail = newnode;
    	}
    }

> 插入前我们先创建结点，封装成一个函数并用static修饰，取消其外部链接属性使得只能在本文件中使用，不允许外部调用。之前我们说过，单链表的尾插要考虑链表是不是为空的情况，避免对空指针进行解引用导致出错。这里也是，要判断队列是否为空，分情况处理。

#### 3.4 出队 ####

入队在链表尾，那么出队就是在链表头了；入队对应着链表的尾插，则出队就是头删。链表的头删很简单，只需要释放结点，将头指针指向下一个结点即可。效果如下：

![341e9dd75e5f4db29db71443f03b042f.gif][]

> 但是，如果只是这样还不够！试想一下，当队列只剩下一个元素时，如果我们再进行出队，头指针没问题指向空，那尾指针呢？由于我们没有去修改，它指向了已经释放空间，显然是不合理的。因此在这种情况下我们还需将尾指针置为NULL。

#### ![0b7d5e71b1ee4cdaa5b12232c226e308.gif][] ####

//出队
    void QueueErase(Queue* pq)
    {
    	assert(pq&&pq->first);
    	//需注意，当队列只有一个元素时，删除后除了要修改first指针，还要修改tail指针
    
    	QueueNode* next = pq->first->next;
    	//只有一个元素
    	if (next == NULL)
    	{
    		free(pq->first);
    		pq->first = pq->tail=NULL;
    	}
    	else
    	{
    		//释放结点，修改头指针指向
    		free(pq->first);
    		pq->first = next;
    	}
    
    }

#### 3.5 求队头元素 ####

很简单，我们可以直接根据头指针得到队头的元素，如下：

//求队头元素
    QueueDataType QueueFront(Queue* pq)
    {
    	assert(pq);
    	assert(pq->first);//队列不为空
    	return pq->first->data;
    }

#### 3.6 求队尾元素 ####

一样的，通过尾指针可以快速定位队尾的位置，得到队尾的元素，如下：

//求队尾元素
    QueueDataType QueueBack(Queue* pq)
    {
    	assert(pq);
    	assert(pq->tail);//队列不为空
    	return pq->tail->data;
    }

#### 3.7 判空 ####

当队列为空时，队头指针和队尾指针都为NULL，我们选其一判断即可。代码如下：

//判空
    //使用bool类型需包含stdbool.h头文件
    bool QueueEmpty(Queue* pq)
    {
    	assert(pq);
    	return pq->first == NULL;//如果为空返回true，不为空返回false
    }

#### 3.8 求队列的元素个数 ####

定义一个变量作为计数器，遍历链表并记录遍历过程中的结点个数：

//求队列元素个数
    int QueueSize(Queue* pq)
    {
    	assert(pq);
    	int count = 0;
    	QueueNode* cur = pq->first;
    	//进行遍历直到为空
    	while (cur)
    	{
    		count++;//计数器加1
    		cur = cur->next;//指向下一结点
    	}
    	return count;
    }

#### 3.9 总结 ####

*  与栈同理，队列也是一种限制型的数据结构，不支持随机访问。其只允许在固定的两端进行操作。因此也不存在查找，打印，修改等需要对其他位置进行操作的接口，否则会破坏队列的特性。
 *  数据结构的实现方式多种多样，为了在隐藏设计细节的情况下使用方依旧能够很方便的使用，尽管有一些操作仅仅只有一两行代码，我们还是封装成函数作为对外的接口供使用方调用。

### 四. 完整代码及效果展示? ###

老样子，我们采用多文件编写的形式，将上述接口的定义实现放在Queue.c文件中，然后将接口的声明和结构体的定义放于Queue.h头文件中，以达到封装的效果。这样我们如果需要使用队列，就只需要在文件中包含对应的头文件Queue.h就可以使用我们上面定义的各种接口。以下为本文实现的队列完整代码以及效果展示：

//Queue.h文件，用于声明接口函数，定义结构体
    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #include<string.h>
    #include<errno.h>
    #include<assert.h>
    
    //单链表的结点
    typedef int QueueDataType;
    typedef struct QueueNode
    {
    	QueueDataType data;
    	struct QueueNode* next;
    }QueueNode;
    
    //队列结构体
    typedef struct Queue
    {
    	QueueNode* first;   //队列头
    	QueueNode* tail;    //队列尾
    }Queue;
    
    //初始化
    void QueueInit(Queue* pq);
    
    //销毁
    void QueueDestroy(Queue* pq);
    
    //插入
    void QueueInsert(Queue* pq, QueueDataType x);
    
    //删除
    void QueueErase(Queue* pq);
    
    //求队头元素
    QueueDataType QueueFront(Queue* pq);
    
    //求队尾元素
    QueueDataType QueueBack(Queue* pq);
    
    //求队列元素个数
    int QueueSize(Queue* pq);
    
    //判空
    bool QueueEmpty(Queue* pq);

//Queue.c文件，用于定义接口函数
    #include"Queue.h"
    
    //初始化队列
    void QueueInit(Queue* pq)
    {
    	assert(pq);
    	pq->first = pq->tail = NULL;//空队列，队头队尾指向空
    }
    
    
    //销毁队列
    void QueueDestroy(Queue* pq)
    {
    	assert(pq);
    	QueueNode* cur = pq->first;
    	//销毁每个结点
    	while (cur)
    	{
    		QueueNode* next = cur->next;//先把下一个结点的位置保存起来，避免销毁后找不到
    		free(cur);
    		cur = next;
    	}
    	pq->first = pq->tail = NULL;//队头队尾置空
    }
    
    
    //创建结点
    static QueueNode* CreatNode(QueueDataType x)
    {
    	QueueNode* ret=(QueueNode*)malloc(sizeof(QueueNode));
    	if (ret == NULL)
    	{
    		printf("%s", strerror(errno));
    		exit(-1);
    	}
    	ret->data = x;
    	ret->next = NULL;
    	return ret;
    }
    
    //入队
    void QueueInsert(Queue* pq, QueueDataType x)
    {
    	assert(pq);
    	QueueNode* newnode = CreatNode(x);
    	//为空队列
    	if (pq->tail == NULL)
    	{
    		pq->first = pq->tail = newnode;
    	}
    	else
    	{
    		//在队尾插入
    		pq->tail->next = newnode;
    		pq->tail = newnode;
    	}
    
    }
    
    
    //出队
    void QueueErase(Queue* pq)
    {
    	assert(pq&&pq->first);
    	//需注意，当队列只有一个元素时，删除后除了要修改first指针，还要修改tail指针
    
    	QueueNode* next = pq->first->next;
    	//只有一个元素
    	if (next == NULL)
    	{
    		free(pq->first);
    		pq->first = pq->tail=NULL;
    	}
    	else
    	{
    		//释放结点，修改头指针指向
    		free(pq->first);
    		pq->first = next;
    	}
    
    }
    
    //求队头元素
    QueueDataType QueueFront(Queue* pq)
    {
    	assert(pq);
    	assert(pq->first);//队列不为空
    	return pq->first->data;
    }
    
    //求队尾元素
    QueueDataType QueueBack(Queue* pq)
    {
    	assert(pq);
    	assert(pq->tail);//队列不为空
    	return pq->tail->data;
    }
    
    //求队列元素个数
    int QueueSize(Queue* pq)
    {
    	assert(pq);
    	int count = 0;
    	QueueNode* cur = pq->first;
    	//进行遍历直到为空
    	while (cur)
    	{
    		count++;//计数器加1
    		cur = cur->next;//指向下一结点
    	}
    	return count;
    }
    
    //判空
    bool QueueEmpty(Queue* pq)
    {
    	assert(pq);
    	return pq->first == NULL;//如果为空返回true，不为空返回false
    }

最后， 我们在test.c文件调用队列各个接口进行测试，如下：

//test.c文件，用于测试
    #include"Queue.h"
    
    void test01()
    {
    	Queue que;
    	//初始化
    	QueueInit(&que);
    	//求元素个数
    	printf("入队前队列的元素个数为:%d\n", QueueSize(&que));
    	//入队，插入5个元素
    	for (int i = 1; i <= 5; i++)
    	{
    		QueueInsert(&que, i);
    	}
    	printf("入队后队列的元素个数为:%d\n", QueueSize(&que));
    	//由于无法遍历打印，我们就交替使用 求队头元素-出队 来显示队中元素
    	printf("队中元素:> ");
    	while (!QueueEmpty(&que))
    	{
    		//求队头元素
    		printf("%d ", QueueFront(&que));
    		//出队
    		QueueErase(&que);
    	}
    	//全部出队
    	printf("\n全部出队后队列的元素个数为:%d\n", QueueSize(&que));
    	//销毁
    	QueueDestroy(&que);
    }
    
    int main()
    {
    	test01();
    	return 0;
    }

以下是测试的最终效果：

![8dc9e3e23deb47df91fc129454a73783.png][]

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

***以上，就是本期的全部内容啦*****?**

***制作不易，能否点个赞再走呢*****?**

[21f2e355e9ce7c3360f4a1091e72707b.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/11b7230359c646e29b0b68aeccd2e644.gif
[8da57cfb54e744ab98a55d61619159ce.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/c8b65fa1e2294e3292415603be57d1b9.gif
[Link 1]: http://t.csdn.cn/c6B5P
[811d1628ac9a429c8c46551998b7cd41.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/12bb4fb13c3c4db5b1e2e37d6bebd081.gif
[e6c7096506844026992eaa3ff8d608bb.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/a34af53e7d074acfa1e870f9a467cfa6.gif
[341e9dd75e5f4db29db71443f03b042f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/2389e3e5b3fd4f539169ded816305ca2.gif
[0b7d5e71b1ee4cdaa5b12232c226e308.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/2d3c8e298a614b6d9a9125c03091ca50.gif
[8dc9e3e23deb47df91fc129454a73783.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/c64d4555655843b28c4eb32d47111e5c.png