数据结构——队列的C语言代码实现

系列文章目录

数据结构——顺序表的C语言代码实现
数据结构——八种链表的C语言代码实现
数据结构——栈的C语言代码实现
数据结构——队列的C语言代码实现
数据结构——堆的C语言代码实现

---

前言

主要实现链式队列。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、基础知识

队列的概念（queue）

援引百科：
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

基于对链表和栈的熟悉，我们可以较为容易认识到队列的特点。
通俗而言：队列是一种较之栈更为公平的结构，它实现了先进先出多的功能。 可以将其比作银行的排队队列，我们只能在人群的末尾排队，在人群的最前端接受服务。

二、代码实现

1.queue.h

注意为了方便在尾部和头部进行操作，我们可以设置头尾指针。对于两个需要设置的指针，如果不想使用全局变量，可以将两个指针结合为一个结构体 ，便于操作。
代码如下（示例）：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int DataType;
//定义队列
typedef struct QueueNode
{
	DataType data;
	struct QueueNode* next;
}QNode;
//设置头尾指针
typedef struct PQueue
{
	QNode* head;
	QNode* tail;
}PQueue;

//初始化
void QueueInit(PQueue* pq);
//删除队列
void QueueDestroy(PQueue* pq);
//尾插
void QueuePush(PQueue* pq, DataType data);
//头删
void QueuePop(PQueue* pq);
//头结点
DataType QueueFront(PQueue* pq);
//尾节点
DataType QueueBack(PQueue* pq);
//判读队空
bool QueueEmpty(PQueue* pq);
//打印队列
void PrintQueue(PQueue* pq);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

2.queue.c

代码如下（示例）：

#include"Queue.h"
//初始化
void QueueInit(PQueue* pq)
{
	pq->head = NULL;
	pq->tail = NULL;
}
//删除队列
void QueueDestroy(PQueue* pq)
{
	QNode* p = pq->head;
	while (p!= NULL)
	{
		QNode* tem = p->next;
		free(p);
		p = tem;
	}
}
//尾插
void QueuePush(PQueue* pq, DataType data)
{
	//确保队列初始化成功
	assert(pq);
	QNode* tem = (QNode*)malloc(sizeof(QNode));
	tem->data = data;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = tem;
	}
	else
	{
		pq->tail->next = tem;
		pq->tail = tem;
	}
}
//头删
void QueuePop(PQueue* pq)
{
	//确保队列不为空
	assert(pq);
	QNode* tem = pq->head->next;
	free(pq->head);
	pq->head = tem;
}
//头结点
DataType QueueFront(PQueue* pq)
{
	bool ret = QueueEmpty(pq);
	if (ret)
	{
		printf("队列为空！\n");
		exit(-1);
	}
	return pq->head->data;
}
//尾节点
DataType QueueBack(PQueue* pq)
{
	bool ret = QueueEmpty(pq);
	if (ret)
	{
		printf("队列为空！\n");
		exit(-1);
	}
	return pq->tail->data;
}
//判读队空
bool QueueEmpty(PQueue* pq)
{
	if (pq->head == NULL)
	{
		return true;
	}
	else
		return false;
}
//打印队列
void PrintQueue(PQueue* pq)
{
	bool ret = QueueEmpty(pq);
	if (ret)
	{
		printf("队列为空！\n");
		return;
	}
	QNode* tem = pq->head;
	while (tem != pq->tail->next)
	{
		printf("%d ", tem->data);
		tem = tem->next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

该处使用的url网络请求的数据。

3.test.c

代码如下：

#include"Queue.h"
int main()
{
	PQueue pq;
	QueueInit(&pq);
	QueuePush(&pq, 1);
	QueuePush(&pq, 2);
	QueuePush(&pq, 3);
	QueuePush(&pq, 4);
	QueuePush(&pq, 5);
	QueuePop(&pq);
	PrintQueue(&pq);
	int ret = QueueFront(&pq);
	printf("\n%d ", ret);
	int tem = QueueBack(&pq);
	printf("\n%d ", tem);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

总结

在熟练掌握线性表、链表和栈之后，队列的实现已十分简单。这篇文章只是简单地实现了队列，便于大家更好地理解和认识队列。