数据结构篇五：队列

待我称王封你为后i 2023-10-09 21:00 101阅读 0赞

#### 文章目录 ####

*  前言
 *  1.队列
 *   *  1.1 队列的概念及结构
     *  1.2 队列的实现
 *  2. 各功能的解析及实现
 *   *  2.1 队列的创建
     *  2.2 初始化队列
     *  2.3 队尾入队列
     *  2.4 队头出队列
     *  2.5 获取队头元素
     *  2.6 获取队尾元素
     *  2.7 队列中有效元素个数
     *  2.8 检查队列是否为空
     *  2.9 销毁队列
 *  3.代码实现
 *   *  3.1 Queue.h
     *  3.2 Queue.c
     *  3.3 test.c
 *  4.总结

## 前言 ##

前面学习了栈，特点是后进先出，今天讲解的队列与其恰恰相反，是先进先出，先进来的数据先出去。

## 1.队列 ##

### 1.1 队列的概念及结构 ###

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)  
  入队列：进行插入操作的一端称为队尾 。  
  出队列：进行删除操作的一端称为队头。  
![在这里插入图片描述][838ad8b1e99a46c880906343751f72d4.png]

### 1.2 队列的实现 ###

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。  
![在这里插入图片描述][81dcc8f4d26b4b3bb3222e83480f4c48.png]

1.  front == NULL，tail = = NULL说明队列为空。
2.  当插入第一个元素时front与tail同时指向第一个元素。
3.  当入队列时，就是单链表的尾插。
4.  当出队列时，就是单链表的头删。

## 2. 各功能的解析及实现 ##

### 2.1 队列的创建 ###

我们采用链表的方式进行实现，因为如果用数组的话，在进行出队列操作时，需要将全部元素都往前移一位，实际上就是将第一个元素覆盖了，比较繁琐，效率没有链表高，所以此处采用链表的方式进行实现。

typedef int Datatype;
    //链式结构表示队列
    typedef struct QListNode
    {
        
    	Datatype data;
    	struct Queue* next;
    }QNode;
    
    typedef struct Queue
    {
        
    	QNode* front;
    	QNode* tail;
    }Queue;

我们定义了两个结构体，一个就是每个元素的内容，一个数据域以及一个指针域。另一个是指向元素的指针，因为在队列里需要用到两个，所以直接封装起来用比较好一些。同时封装到一个结构体内，我们就可以指针传递结构体的指针就可以了，就不需要传递单个（单独的front或者tail）的二级指针。（如果不太理解的话，可以将后续的代码与[单链表][Link 1]这篇博客里面的代码进行比较观看，可以更好的理解为什么这里是传递一级指针，而单链表中传递的是二级指针。

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

将指针置空即可，防止出现野指针问题。

void QueueInit(Queue* pq)
    {
        
    	assert(pq);
    	pq->front = NULL;
    	pq->tail = NULL;
    }

### 2.3 队尾入队列 ###

每次入队列都开辟一个新空间存放元素，然后再进行尾插就完成了。需要注意的是当插入第一个元素的时候是将新结点的地址给了front与tail，而不是进行尾插。因此此时的front与tail是空指针，是不能对他们进行解引用的。

void QueuePush(Queue* pq, Datatype x)
    {
        
    	assert(pq);	
    	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    	if (newnode == NULL)
    	{
        
    		printf("开辟失败！！");
    		return;
    	}
    	newnode->next = NULL;
    	newnode->data = x;
    	
    	if (pq->front == NULL)
    	{
        
    		pq->tail = newnode;
    		pq->front = newnode;
    	}
    	else
    	{
        
    		pq->tail->next = newnode;
    		pq->tail = pq->tail->next;
    	}
    }

### 2.4 队头出队列 ###

删除队头元素，我们只需要保存第二个元素的地址，然后将队头元素的空间进行释放即可，然后再将front移到第二个元素的位置。需要注意的是，当队列中仅剩一个结点时，front与tail指向的是同一块空间，当对front进行释放时，tail也会被释放，如图：  
![在这里插入图片描述][537866284c00422d967e6952e5ac3d00.png]  此时tail就是一个野指针，指向一块已经被释放的空间，因此我们需要加一个判断，也就是当front == NULL时，tail也要被置为NULL。

void QueuePop(Queue* pq)
    {
        
    	assert(pq);
    	assert(!QueueEmpty(pq));
    
    	QNode* next = pq->front->next;
    	free(pq->front);
    	pq->front = next;
    	if (pq->front == NULL)
    	{
        
    		pq->tail = NULL;
    	}
    }

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

唯一需要注意的就是需要判断一下队列是否为空即可。

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

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

唯一需要注意的就是需要判断一下队列是否为空即可。

Datatype QueueBack(Queue* pq)
    {
        
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	return pq->tail->data;
    }

### 2.7 队列中有效元素个数 ###

从头遍历依次计算即可。

int QueueSize(Queue* pq)
    {
        
    	assert(pq);
    	int count = 0;
    	QNode* cur = pq->front;
    	while (cur)
    	{
        
    		count++;
    		cur = cur->next;
    	}
    	return count;
    }

### 2.8 检查队列是否为空 ###

队列为空的状态就是front是空指针，没有指向元素。

bool QueueEmpty(Queue* pq)
    {
        
    	assert(pq);
    	if (pq->front == NULL)
    	{
        
    		return true;
    	}
    	return false;
    }

### 2.9 销毁队列 ###

只需要提前保存准备释放结点的下一个结点地址，然后不断循环进行释放就可以了。

void QueueDestroy(Queue* pq)
    {
        
    	assert(pq);
    	QNode* cur = pq->front;
    	while (cur != NULL)
    	{
        
    		QNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	pq->front = NULL;
    	pq->tail = NULL;
    }

## 3.代码实现 ##

### 3.1 Queue.h ###

包含队列的创建以及各个功能函数的声明。

#pragma once
    #include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    typedef int Datatype;
    
    //链式结构表示队列
    typedef struct QListNode
    {
        
    	Datatype data;
    	struct Queue* next;
    }QNode;
    
    typedef struct Queue
    {
        
    	QNode* front;
    	QNode* tail;
    }Queue;
    
    // 初始化队列
    void QueueInit(Queue* pq);
    
    // 队尾入队列
    void QueuePush(Queue* pq, Datatype data);
    
    // 队头出队列
    void QueuePop(Queue* pq);
    
    // 获取队列头部元素
    Datatype QueueFront(Queue* pq);
    
    // 获取队列队尾元素
    Datatype QueueBack(Queue* pq);
    
    // 获取队列中有效元素个数
    int QueueSize(Queue* pq);
    
    // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
    bool QueueEmpty(Queue* pq);
    
    // 销毁队列
    void QueueDestroy(Queue* pq);

### 3.2 Queue.c ###

各个功能函数的实现。

#include"Queue.h"
    
    void QueueInit(Queue* pq)
    {
        
    	assert(pq);
    	
    	pq->front = NULL;
    	pq->tail = NULL;
    }
    
    void QueueDestroy(Queue* pq)
    {
        
    	assert(pq);
    	QNode* cur = pq->front;
    	while (cur != NULL)
    	{
        
    		QNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	pq->front = NULL;
    	pq->tail = NULL;
    }
    
    void QueuePush(Queue* pq, Datatype x)
    {
        
    	assert(pq);	
    	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    	if (newnode == NULL)
    	{
        
    		printf("开辟失败！！");
    		return;
    	}
    	newnode->next = NULL;
    	newnode->data = x;
    	
    	if (pq->front == NULL)
    	{
        
    		pq->tail = newnode;
    		pq->front = newnode;
    	}
    	else
    	{
        
    		pq->tail->next = newnode;
    		pq->tail = pq->tail->next;
    	}
    }
    
    void QueuePop(Queue* pq)
    {
        
    	assert(pq);
    	assert(!QueueEmpty(pq));
    
    	QNode* next = pq->front->next;
    	free(pq->front);
    	pq->front = next;
    	if (pq->front == NULL)
    	{
        
    		pq->tail = NULL;
    	}
    }
    
    
    Datatype QueueFront(Queue* pq)
    {
        
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	return pq->front->data;
    }
    
    Datatype QueueBack(Queue* pq)
    {
        
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	return pq->tail->data;
    }
    
    int QueueSize(Queue* pq)
    {
        
    	assert(pq);
    	int count = 0;
    	QNode* cur = pq->front;
    	while (cur)
    	{
        
    		count++;
    		cur = cur->next;
    	}
    	return count;
    }
    
    bool QueueEmpty(Queue* pq)
    {
        
    	assert(pq);
    	if (pq->front == NULL)
    	{
        
    		return true;
    	}
    	return false;
    }

### 3.3 test.c ###

对队列功能的测试。

#include"Queue.h"
    
    void test()
    {
        
    	Queue q;
    	QueueInit(&q);
    
    	QueuePush(&q, 1);//测试:入队列
    	QueuePush(&q, 2);
    	QueuePush(&q, 3);
    	QueuePush(&q, 4);
    
    	printf("%d\n",QueueFront(&q));//测试:获取队头元素
    
    	printf("%d\n", QueueSize(&q));//测试:统计元素个数
    
    	QueueDestroy(&q);
    }
    
    void test1()
    {
        
    	Queue q;
    	QueueInit(&q);
    
    	QueuePush(&q, 1);//测试:入队列
    	QueuePush(&q, 2);
    	QueuePush(&q, 3);
    	QueuePush(&q, 4);
    
    	while (!QueueEmpty(&q))
    	{
        
    		Datatype x = QueueFront(&q);
    		printf("%d ", x);
    		QueuePop(&q);   //测试:出队列
    	}
    	printf("\n");
    
    	QueueDestroy(&q);
    }
    int main()
    {
        
    	test();
    	//test1();
    	return 0;
    }

## 4.总结 ##

与栈差不多，一个是用数组实现的，一个是用链表实现的，一个是后进先出，一个先进先出。难度差距不大，重点依旧是放在做题方面感觉较好。  
  那么队列的讲解就先告一段落了，如果发现文章哪里有问题可以在评论区提出来或者私信我嗷。接下来我会继续深入学习数据结构的其他知识，开启新的篇章，那么本期就到此结束，让我们下期再见！！觉得不错可以点个赞以示鼓励喔！！

[838ad8b1e99a46c880906343751f72d4.png]: https://img-blog.csdnimg.cn/838ad8b1e99a46c880906343751f72d4.png
[81dcc8f4d26b4b3bb3222e83480f4c48.png]: https://img-blog.csdnimg.cn/81dcc8f4d26b4b3bb3222e83480f4c48.png
[Link 1]: https://blog.csdn.net/qq_62321047/article/details/129450265?spm=1001.2014.3001.5502
[537866284c00422d967e6952e5ac3d00.png]: https://img-blog.csdnimg.cn/537866284c00422d967e6952e5ac3d00.png