【数据结构】线性表之《队列》超详细实现

一.队列的概念及结构

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

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

二.顺序队列与链队列

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，
出队列在数组头上出数据，效率会比较低。

1.顺序队列

2.链队列

那是不是再用一个指针指向队尾就可以了呢？是的如下图：

这种链表结构完美的解决了尾插时效率低的问题。

三.链队列的实现

1.创建队列

先创建结构体（存放数据和先一个节点的地址）用来表示节点，再额外创建队列结构体（成员：队头指针和队尾指针），队头指针指向队列的队头，队尾指针指向队列的队尾。

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

Queue q;//q代表链队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.初始化队列

将队头指针和队尾指针初始化为NULL。

void QueueInit(Queue* pq)
{
	assert(pq);//断言
	pq->head = pq->tail = NULL;
}
1
2
3
4
5

3.入队

先是创建一个新的节点，存放数据和NULL指针，入队分两种情况：

1. 若队头和队尾指针都为NULL，则队头和队尾指针都指向新的节点。
2. 若队头和队尾指针不为NULL，则向队尾插入新的节点，再更新队尾指针。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	
	//创建入队的节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)//开辟失败
	{
		perror("malloc fail!");
		exit(-1);
	}
	//开辟成功
	newnode->data = x;
	newnode->next = NULL;

	//入队操作
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
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

4.出队

出队也有两种情况

1. 队列只有一个节点，先删除队头，再让队头和队尾指针指向NULL，防止队尾指针变成野指针。
2. 队列有多个节点，先保存队头的下一个节点指针，再删除队头，最后更新队头指针。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//队列不能为空

	//队列只有一个节点
	if (pq->tail->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//队列有多个节点
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5.获取队头元素

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//队列不能为空
	return pq->head->data;
}
1
2
3
4
5
6

6.获取队尾元素

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail != NULL);//队列不能为空
	return pq->tail->data;
}
1
2
3
4
5
6

7.队列的大小

定位队头节点，利用NULL这一条件遍历队列即可。

int QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//定位队头节点
	int size = 0;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;//更新cur
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12

8.队列的判空

判断队头指针是否为NULL即可。

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
1
2
3
4
5

9.清空队列

定位队头节点，依次先后删除即可。

void QueueClear(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//定位队头节点
	while (cur != NULL)
	{
		QNode* next = cur->next;
		free(cur);//逐个删除
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

10.销毁队列

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueClear(pq);
	//注意不能释放pq，这不是动态开辟的地址，而是栈区的地址，所以清空与销毁没什么区别
}
1
2
3
4
5
6

四.队列的盲区

由于队列的特殊结构，只能遵循先进先出的原则，不允许随便遍历队列，否则就失去了队列的特点，只能用以下的代码得到数据：

while (!QueueEmpty(&q))
{
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
}
1
2
3
4
5

五.模块化源代码

1.Queue.h

//#pragma once 防止头文件被重复包含
#ifndef __QUEUE_H__
#define __QUEUE_H__

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

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(Queue* pq);//初始化队列

void QueuePush(Queue* pq, QDataType x);//入队

void QueuePop(Queue* pq);//出队

QDataType QueueFront(Queue* pq);//获取队头元素

QDataType QueueBack(Queue* pq);//获取队尾元素

int QueueSize(Queue* pq);//队列大小

bool QueueEmpty(Queue* pq);//队列判空

void QueueClear(Queue* pq);//清空队列

void QueueDestory(Queue* pq);//销毁队列
#endif
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

2.Queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);//断言
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	
	//创建入队的节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)//开辟失败
	{
		perror("malloc fail!");
		exit(-1);
	}
	//开辟成功
	newnode->data = x;
	newnode->next = NULL;

	//入队操作
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//队列不能为空

	//队列只有一个节点
	if (pq->tail->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//队列有多个节点
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//队列不能为空
	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail != NULL);//队列不能为空
	return pq->tail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//定位队头节点
	int size = 0;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;//更新cur
	}
	return size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

void QueueClear(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//定位队头节点
	while (cur != NULL)
	{
		QNode* next = cur->next;
		free(cur);//逐个删除
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueClear(pq);
	//注意不能释放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
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

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

enum //匿名枚举
{
	EXIT,
	PUSH,
	POP,
	FRONT,
	BACK,
	SIZE,
	EMPTY,
	CLEAR
};

void Menu()
{
	printf("*************队列*************\n");
	printf("****1.入队          2.出队****\n");
	printf("****3.队头          4.队尾****\n");
	printf("****5.大小          6.判空****\n");
	printf("****7.清空          0.退出****\n");
	printf("******************************\n");
}

int main()
{
	Queue q;
	QueueInit(&q);
	int select = 0;
	bool flag;
	QDataType value;
	do
	{
		Menu();
		printf("请选择您的操作：");
		scanf("%d", &select);
		switch (select)
		{
		case EXIT:
			printf("退出队列！\n");
			break;
		case PUSH:
			printf("请输入您要入队的值：");
			scanf("%d", &value);
			QueuePush(&q, value);
			break;
		case POP:
			QueuePop(&q);
			break;
		case FRONT:
			value = QueueFront(&q);
			printf("队头元素值为：%d\n", value);
			break;
		case BACK:
			value = QueueBack(&q);
			printf("队尾元素值为：%d\n", value);
			break;
		case SIZE:
			printf("队列的大小为：%d\n", QueueSize(&q));
			break;
		case EMPTY:
			flag = QueueEmpty(&q);
			if (flag)
			{
				printf("队列为空！\n");
			}
			else
			{
				printf("队列不为空！\n");
			}
			break;
		case CLEAR:
			QueueClear(&q);
			break;
		default:
			printf("输入错误，请重新输入！\n");
			break;
		}
	} while (select);
	QueueDestory(&q);
	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

六.栈和队列必做OJ题

1. 括号匹配问题
2. 用队列实现栈
3. 用栈实现队列

创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！