队列的链式存储结构

1、队列的链式存储结构

​ （1）链队列中结点结构和单链表一样，指针域指向队列中的下一个元素，定义如下

// 定义队列结点
typedef struct QNode
{
	ElemType data;
	struct QNode* next;
}QNode, *QNodePrt;

// 定义队首、队尾指针
typedef struct
{
	QNodePrt front, rear;
}LinkQueue;
1
2
3
4
5
6
7
8
9
10
11
12

​ （2）链队列的初始化

// 初始化队列
Status InitQueue(LinkQueue* q)
{
	// 分配内存空间，建立头结点
	q->front = q->rear = (QNodePrt)malloc(sizeof(QNode));
	// 判断分配是否成功	
	if (!q->front) {
		printf("内存分配失败\n");
		exit(ERROR);
	}
	// 指针域指向空
	q->front->next = NULL;
	printf("初始化队列成功\n");

	return SUCCESS;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

​ （3）入队操作

// 入队操作
Status InsertQueue(LinkQueue* q, ElemType e)
{
	QNodePrt p;
	p = (QNodePrt)malloc(sizeof(QNode));

	if (p == NULL) {
		printf("内存分配失败!\n");
		exit(ERROR);
	}

	// 赋值给新结点
	p->data = e;
	// 新结点的指针域为空
	p->next = NULL;
	// 尾指针后移，指向新结点
	q->rear->next = p;
	q->rear = p;

	printf("%d入队成功\n", e);
	return SUCCESS;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

入队思路：元素e申请入队，则先为元素e申请一个及结点空间，将e存放至该结点的数据域中，并将该结点的指针域置空，用于插入到队尾，作为队尾结点；那么，原队尾指针指向的队尾结点为q->rear->next，此时应更新为p（q->rear->next = p;），队尾指针指向新的队尾结点（q->rear = p;）。

​ （4）出队操作

// 出队操作
Status OutQueue(LinkQueue* q, ElemType* e)
{
	QNodePrt p; // 临时结点
	// 判断队列是否为空
	if (q->front == q->rear) {
		printf("队列为空\n");
		return ERROR;
	}

	// 出队列操作
	p = q->front->next;
	*e = p->data; // 获取结点值

	// 将队首移动到第二个结点，第一个结点出队
	q->front->next = p->next;

	// 判断队列是否只有一个结点，只有一个结点则出队后队首队尾指向同一结点
	if (q->rear = p) {
		q->rear = q->front;
	}
	// 释放出队结点
	free(p);

	return SUCCESS;
}
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

出队思路：出队操作可以参考链表的删除操作，只不过每次删除的都是首元结点。需要申请一个临时结点，用于队首指针的移动标记，当队首指针等于队尾指针时，队列为空，则不能进行出队操作；反之，则进行出队操作，进行出队操作首先获取到待出队的结点（q->front->next;）存放于临时结点p中，获取出队结点数据域内的数据，队首结点出队，队首指针需指向到下一个结点（q->front->next = q->front->next->next），在队列出队后还需判断出队的结点是否是尾结点，如果是，则尾结点出队后，队首指针和队尾指针需要指向同一个地址，最后将临时结点释放。

​ （5）获取队列长度

// 获取队列长度
Status QueueLength(LinkQueue* q)
{
	int length = 0;
	QNodePrt p;
	p = q->front->next;
	while (p)
	{
		length++;
		p = p->next;
	}
	printf("队列长度为:%d\n", length);
	return SUCCESS;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

​ （6）打印队列

// 打印队列
Status printQueue(LinkQueue* q)
{
	// 判断队列是否为空
	if (q->front == q->rear) {
		printf("队列为空\n");
		return ERROR;
	}

	QNodePrt p;
	p = q->front->next;

	printf("\n队列内数据为：");
	while (p)
	{
		printf("%d", p->data);
		p = p->next;
	}

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

完整的代码

#include <stdio.h>
#include <stdlib.h>

#define ElemType int
#define Status int

#define SUCCESS 1
#define FAILURE 0
#define ERROR 0

// 定义队列结点
typedef struct QNode
{
	ElemType data;
	struct QNode* next;
}QNode, *QNodePrt;

// 定义队首、队尾指针
typedef struct
{
	QNodePrt front, rear;
}LinkQueue;

// 初始化队列
Status InitQueue(LinkQueue* q)
{
	// 分配内存空间，建立头结点
	q->front = q->rear = (QNodePrt)malloc(sizeof(QNode));
	// 判断分配是否成功	
	if (!q->front) {
		printf("内存分配失败\n");
		exit(ERROR);
	}
	// 指针域指向空
	q->front->next = NULL;
	printf("初始化队列成功\n");

	return SUCCESS;
}

// 出队操作
Status OutQueue(LinkQueue* q, ElemType* e)
{
	QNodePrt p; // 临时结点
	// 判断队列是否为空
	if (q->front == q->rear) {
		printf("队列为空\n");
		return ERROR;
	}

	// 出队列操作
	p = q->front->next;
	*e = p->data; // 获取结点值

	// 将队首移动到第二个结点，第一个结点出队
	q->front->next = p->next;

	// 判断队列是否只有一个结点，只有一个结点则出队后队首队尾指向同一结点
	if (q->rear = p) {
		q->rear = q->front;
	}
	// 释放出队结点
	free(p);

	return SUCCESS;
}

// 获取队列长度
Status QueueLength(LinkQueue* q)
{
	int length = 0;
	QNodePrt p;
	p = q->front->next;
	while (p)
	{
		length++;
		p = p->next;

	}
	printf("队列长度为:%d\n", length);
	return SUCCESS;
}

// 打印队列
Status printQueue(LinkQueue* q)
{
	// 判断队列是否为空
	if (q->front == q->rear) {
		printf("队列为空\n");
		return ERROR;
	}

	QNodePrt p;
	p = q->front->next;

	printf("\n队列内数据为：");
	while (p)
	{
		printf("%d", p->data);
		p = p->next;

	}

	return SUCCESS;
}

// 入队操作
Status InsertQueue(LinkQueue* q, ElemType e)
{
	QNodePrt p;
	p = (QNodePrt)malloc(sizeof(QNode));

	if (p == NULL) {
		printf("内存分配失败!\n");
		exit(ERROR);
	}

	// 赋值给新结点
	p->data = e;
	// 新结点的指针域为空
	p->next = NULL;
	// 尾指针后移，指向新结点
	q->rear->next = p;
	q->rear = p;

	printf("%d入队成功\n", e);
	return SUCCESS;
}

int main(int argc, char const* argv[])
{
	ElemType data;

	printf("开始初始化队列\n\n");
	LinkQueue linkQ;
	InitQueue(&linkQ);

	printf("入队开始\n");
	int i = 0;
	for (i = 0; i < 5; i++)
		InsertQueue(&linkQ, i);

	QueueLength(&linkQ);
	printQueue(&linkQ);

	OutQueue(&linkQ, &data);
	printf("\n出队数据为:%d\n", data);

	return 0;
}
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
'
运行
运行