数据结构-C语言实现队列进队、出队等基本操作（内含图解）

一、队列结构

二、代码实现

1，队列的结构

先实现存储结构，就是红色框起来的部分。
这个结构是由多个结点组成的，每个结点里有数据data和next指针。

//这是一个结构体，里面包括数据和一个结构体指针
 10	//（就是一个指针，这个指针可以指向结构体）
 11	typedef struct QueueNode
 12	{
 13		QDataType data;
 14		struct QueueNode* next;
 15	}QueueNode;

再实现外面的两条黑色线，这就是队列。
观察到，队列有两个指针，我们实现它就行

//这也是一个结构体，里面包括两个结构体指针
 18	typedef struct Queue
 19	{
 20		//注意，这里这两个指针的类型是【QueueNode】
 21		//目的是可以通过head找到data和next
 22		//head的成员是data next
 23		QueueNode* head;
 24		QueueNode* tail;
 25	}Queue;
 26	
 27	//为什么要叫pq？
 28	// 外面定义了一个结构体q（意为queue，队列之意）
 29	// 函数用指针来接收他，取一个p（pointer）
 30	// 合在一起就是pq，也能和外面的区分开
 31	

2、函数实现

1）初始化函数

先看一下我们要做成什么样子。

我们的目的是初始化队列，就是外面两条黑色的线，刚开始队列里没有元素，让他们都指向空就行。

//初始化
 5	void QInit(Queue* pq)
 6	{
 7		//为什么不初始化data和next
 8		//pq是Queue类型，这个类型里只有head和tail，所以只需要初始化这两个
 9		assert(pq);
 10		pq->head = pq->tail = NULL;
 11	}

2）入队一个数

先看一下我们要做成什么样子。

`

void QPush(Queue* pq, QDataType x)
 29	{
 30		assert(pq);
 31		QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
 32		newnode->data = x;
 33		newnode->next = NULL;
 34		//特殊情况，没有结点
 35		if(pq->head==NULL)
 36		{
 37			pq->head = newnode;
 38			pq->tail = newnode;
 39		}
 40		//正常情况
 41		/*开辟一个节点，把数据放进去
 42		再和原来的连接上*/
 43		else
 44		{ 
 45			//
 46			pq->tail->next=newnode;
 47			pq->tail = newnode;
 48		}
 49	
 50	}
 51	

3）出队一个数

出队之前的样子

//删除
 54	void QPop(Queue* pq)
 55	{
 56		//数据是从队头出去的，
 57		//出去一个数，队头就更新一次
 58		assert(pq);
 59		
 60		//不能删空
 61		assert(!QEmpty(pq));
 62	
 63		QueueNode* next = pq->head->next;
 		free(pq->head);
 65		pq->head = next;
 66		if (pq->head == NULL)
 67		{
 68			pq->tail = NULL;
 69		}
 70	
 71		
 72	}
 73	

4）判断是否为空

这个函数的返回值是bool类型，如果为空就返回true，不为空返回false。
为什么要写这个函数，
举个🌰
队列只有【1，2，3】3个元素，而有人想出队5次，可是第四次出队的时候队列已经为空了，我没有元素给你出了，你不能硬出吧？所以出队的时候调用这个函数，如果队列是空，就不再出队了。

//判断是否为空
 14	bool QEmpty(Queue* pq)
 15	{
 16		assert(pq);
 17		if (pq->head == NULL)
 18		{
 19			return true;
 20		}
 21		else
 22		{
 23			return false;
 24		}
 25	}

5）取出队头（队尾）元素

取出队头和取出队尾的思想是一样的，这里我就放在一起了。

//取出队头
 77	QDataType QFront(Queue* pq)
 78	{
 79		assert(pq);
 80		assert(!QEmpty(pq));
 81		return pq->head->data;
 82	}
 83	
 84	//取出队尾
 85	QDataType QBack(Queue* pq)
 86	{
 87		assert(pq);
 88		assert(!QEmpty(pq));
 		return pq->tail->data;
 90	}
 91	

6）释放空间

因为结点都是malloc出来的，当程序结束的时候，我们要把空间还给操作系统。
有同学可能会问，为什么要还给他？
因为如果你不还的话，程序结束了，但是开辟的空间还在，你不用了也不能让别人用，这不就造成了资源浪费吗？
操作系统可用的空间就会越来越少。

//释放空间
 109	void QDestroy(Queue* pq)
 110	{
 111		QueueNode* cur = pq->head;
 112		//头不能乱动
 113		while (cur != NULL)
 114		{
 115			QueueNode* next = cur->next;
 116			free(cur);
 117			cur = next;
 118		}
 119		//最后把头和尾置成null
 120		pq->head=pq->tail = NULL;
 121	
 122	}

三、总结

插入：先开辟新的结点，把数据放进去，并且让新的结点的next指向null，再让原来的tail指向新的结点。
删除：先定义一个指针，指向原来的head的next，再删除head，然后更新head，让新的head指向刚刚定义的指针。
注意：
每次删除都要判断队列是否为空
每次调用函数的时候都要断言传进来的结构体不为空。