探索数据结构：链式队与循环队列的模拟、实现与应用_数据结构链式队列的实现及应用体会

1. 队列的定义

队列（queue）是一种只允许在一端进行插入操作，而在另一端进行删除操作的线性表。其严格遵循先进先出（First In First Out）的规则，简称FIFO。

• 队头（Front）：允许删除的一端，又称队首。
• 队尾（Rear）：允许插入的一端。

2. 队列的分类

队列与栈类似，实现方式有两种。一种是以数组的方式实现，另一种以单链表来实现。这两种实现方式各有优劣，并且都有细节需要处理。

1. 基于单链表实现：我们可以将链表的头节点与尾节点分别作为队列的队首与队尾，这样我们就能用两个指针来对其进行操作。如下图：

1. 基于数组实现：我们同样可以通过两个下标分别指向数组的起始与结束，但这时我们就可能发现两个问题：

• 问题一：在不断出队与进队得到过程中，起始下标与末尾下标都在向后移动，当两个下标同时指向数组末尾时就无法再移动了，并且**浪费前面大量空间，**如图1

• 问题二：为了解决上述问题，我们将数组首尾相接变为循环数组。但这时又会出现一个问题，那便是当队首与队尾下标指向同一个节点时，这个队列到底是空还是满呢？这时我们有三个解决方法

• 第一种：牺牲一个单元来区分队空和队满，这时若队列不为空，让队尾下标指向队尾的下一个位置。约定以队头指针在队尾指针的下一位置作为队满的标志，即Q->rear+1==Q->front。如图二。

• 第二种：增设表示元素个数的数据成员 size 。这样，队空的条件为 Q->size==0；队满的条件为 Q->size==MaxSize。

• 第三种：增加表示队满的数据成员flag。将flag初始化为0，当队满时将其置为1。

3. 队列的功能

1. 队列的初始化。
2. 判断队列是否为空。
3. 判断队列是否满了。
4. 返回队头与队尾的元素。
5. 返回队列的大小。
6. 入队与出队。
7. 打印队列的元素。
8. 销毁队列。

4. 队列的声明

4.1. 链式队

链式队的声明十分简单，参照上面图我们就可以直接实现了。

typedef int QDataType;
typedef struct QueueNode 
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue 
{
	QNode* front;
	QNode* rear;
	size_t size;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12

4.2. 循环队

根据上述分析，我们采用一个数组来实现队列，其声明如下

typedef int QDataType;
#define MAXSIZE 50  //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct {
    QDataType *data;
    int front;  //头指针
    int rear;   //尾指针
}Queue;
1
2
3
4
5
6
7
8

5. 队列的初始化

对队列声明的数据进行初始化，防止随机值。

5.1. 链式队

void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
1
2
3
4
5
6

5.2. 循环队

void QueueInit(Queue* q) 
{
    q->data = (QDataType*)malloc(sizeof(QDataType )* MAXSIZE);
	if (q->data == NULL)
	{
		perror("malloc fail:");
		return;
	}
    q->front = 0;
    q->rear = 0;
}
1
2
3
4
5
6
7
8
9
10
11

5.3. 复杂度分析

• 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
• 空间复杂度：链式队空间是一个固定大小，空间复杂度为O(1)。而需要开辟整个队列的大小，空间复杂度为O(N)。

6. 判断队列是否为空

判断队列是否为空十分简单，这里就不在赘述。

6.1. 链式队

bool QueueEmpty(Queue* q)
{
	assert(q);
	return (q->front == NULL) && (q->rear == NULL);
}
1
2
3
4
5

6.2. 循环队

bool QueueEmpty(Queue*q)
{
    assert(q);
    return q->front == q->rear;
}
1
2
3
4
5

6.3. 复杂度分析

• 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
• 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

7. 判断队列是否为满

7.1. 链式队

链式队不需要判断是否为满的情况。

7.2. 循环队

为了完成循环操作，需要对其进行取模操作，防止越界。

bool QueueFull(Queue*q)
{
    assert(q);
    return q->front == (q->rear+1)%MAXSIZE;
}
1
2
3
4
5

7.3. 复杂度分析

• 时间复杂度：循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
• 空间复杂度：循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

8. 返回队头与队尾元素

因为定义了头指针与尾指针，所以访问数据也十分方便。

8.1. 链式队

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}
1
2
3
4
5
6
7
8
9
10
11
12

8.2. 循环队

rear下标可能指向下标0，这时贸然减一就可能出现越界的情况。为了解决这个问题我们可以加上MAXSIZE再对其取模。

QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[q->front];
}
QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[(q->rear-1+MAXSIZE)%MAXSIZE];
}
1
2
3
4
5
6
7
8
9
10
11
12

8.3. 复杂度分析

• 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
• 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

9. 队列的大小

9.1. 链式队

size_t QueueSize(Queue* q)
{
	return q->size;
}
1
2
3
4

9.2. 循环队

求循环队列的大小，我们很容易想到用Q->rear-Q->front得出队列元素个数。但是我们要考虑到一种特殊情况：当队列先删除元素再添加元素时，末尾下标**rear**可能循环重置，如下图。

那到底该如何解决这个问题呢？其实我们只需要在原来基础上加上一个MAXSIZE就行了，为了使图一情况也适用我们仍需模上一个MAXSIZE。

size_t QueueSize(Queue*q) 
{
    assert(q);
    return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}
1
2
3
4
5

9.3. 复杂度分析

• 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
• 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

10. 入队

10.1. 链式队

链式队列入队时需要判断队列是否为空的特殊情况，如果是则还需要将尾指针也指向这个节点。

void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	if (q->front == NULL)
	{
		q->front = q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
	q->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

10.2. 循环队

为了使循环队列在插入数据时实现循环操作，我们可以每次进行取模操作。并且每次入队之前要检查循环队是否已满。

void QueuePush(Queue* q, QDataType x) 
{
    assert(q);
    if(QueueFull)
    {
        printf("队列已满\n");
        return ;
    }
    q->data[q->rear] = x;   
    q->rear = (q->rear + 1) % MAXSIZE;  //rear指针向后移一位置，若到最后则转到数组头部
}
1
2
3
4
5
6
7
8
9
10
11

10.3. 复杂度分析

• 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
• 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

11. 出队

11.1. 链式队

同样考虑特殊情况，防止队列为空。并且当队列只有一个节点时需要将头指针与尾指针都置为空。

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	//1.只有一个结点
	if (q->front == q->rear)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	//2.有多个结点
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
		del = NULL;
	}
	q->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

11.2. 循环队

同样为了实现循环，我们可以进行取模操作。

 void QueuePop(Queue* q)
 {
     assert(q);
     assert(!QueueEmpty(q));
    q->front = (q->front + 1) % MAXSIZE;    //front指针向后移一位置，若到最后则转到数组头部
 }
1
2
3
4
5
6

11.3. 复杂度分析

• 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
• 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

12. 打印队列

12.1. 链式队

void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	QNode* tail = q->rear;
	printf("队头->");
	while (cur != tail->next)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("队尾\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13

12.2. 循环队

 void QueuePrint(Queue* q)
 {
     assert(q);
     int cur = q->front;
     printf("队头->");
     while (cur != q->rear)
     {
         printf("%d->", q->data[cur]);
         cur = (cur + 1) % MAXSIZE;
     }
     printf("队尾\n");
 }
1
2
3
4
5
6
7
8
9
10
11
12

12.3. 复杂度分析

• 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
• 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

13. 销毁队列

13.1. 链式队

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	q->front = q->rear = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

13.2. 循环队

void QueueDestroy(Deque* q)//销毁队列
{
	assert(q);
	free(q->data);
	q->data = NULL;
	q->front = q->rear = 0;
}
1
2
3
4
5
6
7

13.3. 复杂度分析

• 时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
• 空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

14. 链式队与循环队列的对比与应用

14.1. 对比

14.2. 应用

队列的应用与栈一样，十分广泛

1. 当我们去食堂扫码订餐时，你的订单就会加入一个队列中。
2. 在操作系统中，队列可以用来管理任务进度与进程切换。

15. 完整代码

15.1. 链式队

15.1.1. 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* front;
	QNode* rear;
	size_t size;
}Queue;
void QueueInit(Queue* q);//初始化队列
bool QueueEmpty(Queue* q);//判断是否为空
QDataType QueueFront(Queue* q);//获取队头元素
QDataType QueueBack(Queue* q);//或许队尾元素
size_t QueueSize(Queue* q);//或许队列长度
void QueuePush(Queue* q, QDataType x);//入队
void QueuePop(Queue* q);//出队
void QueuePrint(Queue* q);//打印队列元素
void QueueDestroy(Queue* q);//销毁队列
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

15.1.2. Queue.c

#include"Queue.h"
void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
bool QueueEmpty(Queue* q)
{
	assert(q);
	return (q->front == NULL) && (q->rear == NULL);
}
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}
size_t QueueSize(Queue* q)
{
	return q->size;
}
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	if (q->front == NULL)
	{
		q->front = q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
	q->size++;
}
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	//1.只有一个结点
	if (q->front == q->rear)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	//2.有多个结点
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
		del = NULL;
	}
	q->size--;
}
void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	QNode* tail = q->rear;
	printf("队头->");
	while (cur != tail->next)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("队尾\n");
}
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	q->front = q->rear = NULL;
}
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

15.2. 循环队列

15.2.1. Queue.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
#define MAXSIZE 50  //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct {
    QDataType *data;
    int front;  //头指针
    int rear;   //尾指针
}Queue;

void QueueInit(Queue* q);//初始化队列
bool QueueEmpty(Queue* q);//判断是否为空
bool QueueFull(Queue*q);//判断队列是否满
QDataType QueueFront(Queue* q);//获取队头元素
QDataType QueueBack(Queue* q);//或许队尾元素
size_t QueueSize(Queue* q);//或许队列长度
void QueuePush(Queue* q, QDataType x);//入队
void QueuePop(Queue* q);//出队
void QueuePrint(Queue* q);//打印队列元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

15.2.2. Queue.c

void QueueInit(Queue* q) 
{
    q->data = (QDataType*)malloc(sizeof(QDataType )* MAXSIZE);
	if (q->data == NULL)
	{
		perror("malloc fail:");
		return;
	}
    q->front = 0;
    q->rear = 0;
}
bool QueueEmpty(Queue*q)
{
    assert(q);
    return q->front == q->rear;
}
bool QueueFull(Queue*q)
{
    assert(q);
    return q->front == (q->rear+1)%MAXSIZE;
}
QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[q->front];
}
QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->data[(q->rear-1+MAXSIZE)%MAXSIZE];
}
size_t QueueSize(Queue*q) 
{
    assert(q);
    return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}
void QueuePush(Queue* q, QDataType x) 
{
    assert(q);
    if(QueueFull)//判断队列是否满了
    {
        printf("队列已满\n");
        return ;
    }
    q->data[q->rear] = x;   
    q->rear = (q->rear + 1) % MAXSIZE;  //rear指针向后移一位置，若到最后则转到数组头部
}
 void QueuePop(Queue* q)
 {
     assert(q);
     assert(!QueueEmpty(q));
    q->front = (q->front + 1) % MAXSIZE;    //front指针向后移一位置，若到最后则转到数组头部
 }
 void QueuePrint(Queue* q)
 {
     assert(q);
     int cur = q->front;
     printf("队头->");
     while (cur != q->rear)
     {
         printf("%d->", q->data[cur]);
         cur = (cur + 1) % MAXSIZE;
     }
     printf("队尾\n");
 }
void QueueDestroy(Deque* q)//销毁队列
{
	assert(q);
	free(q->data);
	q->data = NULL;
	q->front = q->rear = 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