队列的定义及基本操作实现（链式）

左手的ㄟ右手 2024-04-11 13:23 158阅读 0赞

> 个人主页：[【?个人主页】][Link 1]  
> 系列专栏：[【❤️数据结构与算法】][Link 2]  
> 学习名言：天子重英豪，文章教儿曹。万般皆下品，惟有读书高

## 系列文章目录 ##

第一章 ❤️ [学前知识][Link 3]  
第二章 ❤️ [单向链表][Link 4]  
第三章 ❤️ [递归][Link 5]

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

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

*  系列文章目录
 *  前言
 *  一.队列是什么？???
 *  二、队列与线性表的关系???
 *  三、队列的基本操作???
 *   *  1.队列的储存结构结构?
     *  2.队列的初始化✨
     *  3. 入队?
     *  4.出队?
     *  5.清空与销毁?
 *  总结???

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

## 前言 ##

![在这里插入图片描述][db50c409b85f4edeb017bb02cb2e1610.jpeg_pic_center]

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

## 一.队列是什么？??? ##

和栈相反，队列( queue)是一种先进先出( First In First Out, FIFO) 的线性表。**它只允许在表的一端进行插人，而在另一端删除元素**。这和日常生活中的排队是一致的， 最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾( rear)，允许删除的一端则称为队 头( front) 。假设队列为q=(a1,a2, .,an)，那么，a就是队头元素， a,则是队尾元素。队列中的元素是按照a, a, … a,的顺序进人的，退出队列也只能按照这个次序依次退出，也就是说，只有在a,a., an，都离开队列之后，a,才能退出队列。

![请添加图片描述][207a6d14876b4048b0fe6d111bf40e25.jpeg]

## 二、队列与线性表的关系??? ##

与栈一样队列也是一种重要的线性结构。从数据结构角度看，**队列也是线性表**，其特殊性在于队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为具有限定性的数据结构。但从数据类型角度看，它是和线性表不相同的两类重要的抽象数据类型。

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

## 三、队列的基本操作??? ##

### 1.队列的储存结构结构? ###

typedef struct Qnode
    {
        
    	Elemtype data;
    	struct Qnode* next;
    }QNode, * QueuePrt;//建立链表
    typedef struct
    {
        
    	QueuePrt front;
    	QueuePrt rear;//指向头和尾的两个指针
    	
    }LinkQueue;//建立队列

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

### 2.队列的初始化✨ ###

InitQueue(LinkQueue* q)
    {
        
    	q->front = q->rear = (QueuePrt)malloc(sizeof(QNode));//创建头结点
    	if (!q->front)
    		exit(0);
    	q->front->next = NULL;
    }//初始队列

> 其实就是链表中的创建头结点

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

### 3. 入队? ###

InsertQueue(LinkQueue *q, Elemtype e)
    {
        
    	QueuePrt p;
    	p = (QueuePrt)malloc(sizeof(QNode));//创建结点
    	if (p == NULL)
    		exit(0);
    	p->data = e;//赋值
    	p->next = NULL;//
    	q->rear->next = p;//头指针指向下一个结点
    	q->rear = p;
    }

![在这里插入图片描述][d6a2bbc18d5f4cab8bfe131c1f6021f7.jpeg_pic_center]

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

### 4.出队? ###

DeletQueue(LinkQueue* q, Elemtype* e)
    {
        
    	QueuePrt p;
    	if (q->front == q->rear)
    		return 0;
    	*e = p->data;
    	q->front->next = p->next;
    	if (q->rear == p)
    		q->rear = q->front;
    	free(p);
    }

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

### 5.清空与销毁? ###

DesteoyQueue(LinkQueue* q)
    {
        
    	while (q->rear = q->front->next)
    	{
        
    		free(q->front);
    		q->front = q->rear;
    	}
    }

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

## 总结??? ##

队列是一种先进先出的线性表。它只允许在表的一端进行插人， 而在另一端进行删除。队列也有两种存储表示，顺序表示(循环队列)和链式表示( 链队)。队列的主要操作是进队和出队，对于顺序表示的循环队列的进队和出队操作要注意判断队满或队空。凡是涉及队头或队尾指针的修改都要将其对MAXQSIZE求模。

#include<stdio.h>
    #include<stdlib.h>
    typedef int Elemtype;//定义类型
    typedef struct Qnode
    {
        
    	Elemtype data;
    	struct Qnode* next;
    }QNode, * QueuePrt;//建立链表
    typedef struct
    {
        
    	QueuePrt front;
    	QueuePrt rear;//指向头和尾的两个指针
    	
    }LinkQueue;//建立队列
    InitQueue(LinkQueue* q)
    {
        
    	q->front = q->rear = (QueuePrt)malloc(sizeof(QNode));//创建头结点
    	if (!q->front)
    		exit(0);
    	q->front->next = NULL;
    }//初始队列
    InsertQueue(LinkQueue *q, Elemtype e)
    {
        
    	QueuePrt p;
    	p = (QueuePrt)malloc(sizeof(QNode));//创建结点
    	if (p == NULL)
    		exit(0);
    	p->data = e;//赋值
    	p->next = NULL;//
    	q->rear->next = p;//头指针指向下一个结点
    	q->rear = p;
    }
    DeletQueue(LinkQueue* q, Elemtype* e)
    {
        
    	QueuePrt p;
    	if (q->front == q->rear)
    		return 0;
    	*e = p->data;
    	q->front->next = p->next;
    	if (q->rear == p)
    		q->rear = q->front;
    	free(p);
    }
    DesteoyQueue(LinkQueue* q)
    {
        
    	while (q->rear = q->front->next)
    	{
        
    		free(q->front);
    		q->front = q->rear;
    	}
    }

（文章中图片与部分内容来源与网络，如有侵权请联系删除)  
![在这里插入图片描述][7b8b1cbe7d3a476198039f6bb7e35f55.gif_pic_center]

[Link 1]: https://blog.csdn.net/weixin_73602725?type=blog
[Link 2]: https://blog.csdn.net/weixin_73602725/category_12226568.html?spm=1001.2014.3001.5482
[Link 3]: https://blog.csdn.net/weixin_73602725/article/details/129406349
[Link 4]: https://blog.csdn.net/weixin_73602725/article/details/129270463
[Link 5]: https://blog.csdn.net/weixin_73602725/article/details/129450203
[db50c409b85f4edeb017bb02cb2e1610.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/a6d7d293d08642258da761482592bee8.jpeg
[207a6d14876b4048b0fe6d111bf40e25.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/10d6f31636ac434db26a80dcda989a63.jpeg
[d6a2bbc18d5f4cab8bfe131c1f6021f7.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/572a479edb414ca29d4d9f34f119ad87.jpeg
[7b8b1cbe7d3a476198039f6bb7e35f55.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/fe01d2181ff14ca785d6efb7750f6d8e.gif