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

一、队列结构

队列是先进先出的结构，如果依次存储【1，2，3】。那么最后输出的是【1，2，3】这里我用链式结构存储数据，
这里我们要实现链式存储的队列。队列就相当于外面的两条黑色的线，红色框起来的是链式结构。

二、代码实现

1，队列的结构

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

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

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

//这也是一个结构体，里面包括两个结构体指针
 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	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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	}
1
2
3
4
5
6
7
8

2）入队一个数

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

这种情况（特殊情况）是原队列没有结点，插入一个数字1，因为只有一个元素，让head和tail都指向1。

这种情况（正常情况）原本队列里有一个9，我们再插入一个1。

`

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	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3）出队一个数

出队之前的样子

把9出队之后

目的是删除9所在的结点，先定义一个next（里面存放新的头），删除9之后，更新结点，让head指向新的头。

//删除
 54	void QPop(Queue* pq)
 55	{
 56		//数据是从队头出去的，
 57		//出去一个数，队头就更新一次
 58		assert(pq);
 59		
 60		//不能删空
 61		assert(!QEmpty(pq));
 62	
 63		QueueNode* next = pq->head->next;
 64		free(pq->head);
 65		pq->head = next;
 66		if (pq->head == NULL)
 67		{
 68			pq->tail = NULL;
 69		}
 70	
 71		
 72	}
 73	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4）判断是否为空

这个函数的返回值是bool类型，如果为空就返回true，不为空返回false。
为什么要写这个函数，
举个