【数据结构】基础：队列（C语言）

【数据结构】基础：队列（C语言）

摘要：本文对队列进行简单的介绍，并对其分析与实现

---

一、概述

队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

• 入队列：进行插入操作的一端称为队尾
• 出队列：进行删除操作的一端称为队头

示意图如下：

二、分析

队列作为一种线性表，可以使用顺序表或者链表的形式实现。如果通过顺序实现，由于出队列后空间浪费问题严重，因此使用链表进行实现。使用链表实现，需要考虑到头结点，是否循环与单向或是双向。对于头结点影响并不大，对于单向与双向，虽然双向是简化代码，但是结构复杂，而单向也是可以通过设计结构达到代码简化的目的，最后是循环，同样是不必要的，只需通过对队列的设计即可优化。

队列结构体的结构体，对于每一个节点，是与普通链表节点一致的，而队列结构体需要头尾两个节点指针，方便进行入队出队，再设计一个size减少求大小时对数据的遍历。

结构体定义如下：

typedef int QueueDataType;

struct QueueNode {
	QueueDataType val;
	struct QueueNode* next;
};

struct Queue{
	struct QueueNode* head;
	struct QueueNode* tail;
	size_t size;
};

typedef struct Queue Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、实现

3.1 初始化

初始化操作对队列进行赋空操作

void QueueInit(Queue* queue) {
	queue->head = NULL;
	queue->tail = NULL;
	queue->size = 0;
}
1
2
3
4
5

3.2 销毁

销毁是需要对数组进行遍历的，从头结点进行遍历，每个结点进行释放，最后将队列赋空

void QueueDestory(Queue* queue) {
	assert(queue);
	struct QueueNode* cur = queue->head;
	while (cur != NULL) {
		struct QueueNode* ptemp = cur;
		cur = cur->next;
		free(ptemp);
	}
	queue->head = queue->tail = NULL;
	queue->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11

3.3 入队列

入队由于是不带头的链表，因此需要分空链表与多个节点链表的情况，如果是空链表，将新节点作文第一个节点，如果不是空链表，就需要进行尾插操作。将尾节点的指针指向新节点，并移动尾指针指向新节点。当然最后需要对size进行增加图示与代码如下：

void QueuePush(Queue* queue, QueueDataType val) {
	assert(queue);
	// 创建新节点
	struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
	if (newNode == NULL) {
		perror("malloc");
		exit(-1);
	}
	newNode->next = NULL;
	newNode->val = val;

	if (isQueueEmpty(queue) == 1) {
		queue->head = queue->tail = newNode;
		queue->tail->next = NULL;
		queue->size += 1;
	}
	else {
		queue->tail->next = newNode;
		queue->tail = newNode;
		queue->size += 1;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.4 出队列

出队操作首先需要进行对空队列进行判断的，这里使用了断言进行判断。在判断后进行头删，头删也是要分情况的，如果删除后是空链表，需要对头尾指针指向空指针，否则，只需移动头指针即可。而原来的节点，通过一个临时变量储存，并且释放，当然最后还需要修改size值。代码以及图示如下：

void QueuePop(Queue* queue) {
	assert(queue);
	assert(!isQueueEmpty(queue));

	struct QueueNode* ptemp = queue->head;
	if (queue->head == queue->tail) {
		queue->head = queue->tail = NULL;
	}
	else {
		queue->head = queue->head->next;
	}
	free(ptemp);
	queue->size -= 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.5 取队头与队尾

直接通过头尾指针取变量即可，注意判空操作

QueueDataType QueueFront(Queue* queue) {
	assert(queue);
	assert(!isQueueEmpty(queue));
	return queue->head->val;
}
QueueDataType QueueBack(Queue* queue) {
	assert(queue);
	assert(!isQueueEmpty(queue));
	return queue->tail->val;
}
1
2
3
4
5
6
7
8
9
10

3.6 判空

int QueueSize(Queue* queue) {
	return queue->size;
}
1
2
3

3.7 求大小

int isQueueEmpty(Queue* queue) {
	return queue->size == 0;
}
1
2
3

---

补充：

1. 代码将会放到：C_C++_REVIEW: 一套 C/C++ 系统完整的使用手册，以及部分疑难杂症的解析 (gitee.com) ，欢迎查看！
2. 欢迎各位点赞、评论、收藏与关注，大家的支持是我更新的动力，我会继续不断地分享更多的知识！