《数据结构（C语言版）第二版》第三章-栈和队列（3.5 队列的表示和操作的实现）

3.5 队列的表示和操作的实现

3.5.1 循环列队的表示和操作的实现

3.5.1.1 循环列队的初始化

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

#define MAXQSIZE 100

typedef int QElemType;

typedef struct
{
	QElemType* base;
	int fornt;
	int rear;
}SqQueue;

void InitQueue(SqQueue& Q);

int  main()
{
	SqQueue N = { NULL,0,0 };
	InitQueue(N);
	return 0;
}

void InitQueue(SqQueue& Q)
{
	Q.base = (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);

	if (!Q.base)
	{
		printf("内存分配失败，导致初始化循环队列失败。");
		return;
	}

	Q.fornt = Q.rear = 0;
	printf("初始化循环队列成功。");
}
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

3.5.1.2 求循环列队的长度

循环队列长度公式推导——我想he可乐

已知：
当Q.rear≥Q.front时，L=Q.rear-Q.front；
当Q.rear<Q.front时，L=MaxSize-Q.front+Q.rear = Q.reare-Q.front+MaxSize.

数学取余的性质：（x+ky）%y=x（x<y，k∈N）.

当Q.rear≥Q.front时，x = Q.rear-Q.front，k = 1,
Q.rear-Q.front = （Q.rear-Q.front + MaxSize）% MaxSize；

当Q.rear<Q.front时，x = Q.rear-Q.front+ MaxSize，k = 1,
Q.reare-Q.front+MaxSize
= （Q.reare-Q.front + MaxSize + MaxSize )% MaxSize
=（Q.reare-Q.front + 2MaxSize )% MaxSize
= Q.reare-Q.front
= （Q.rear-Q.front + MaxSize）% MaxSize

所以可将三种情况下的公式合成一个：

循环队列中现有元素的个数：
L = （Q.rear-Q.front+MaxSize）%MaxSize.

①MaxSize是循环列队中整个环形所包含的元素的个数（或者叫循环列队的长度），是不变的。
②循环列队存储数据的一维数组QElemType base[MaxSize]的位置，及其每个位置所代表的数组下标（从0到MaxSize-1），在初始化成功，申请了内存空间之后，也是固定不变的。
③队头Q.front和队尾Q.rear也是数组下标，但在元素入队和出队过程中，均是动态变化的。
因此，不管是空队，还是满队，队头和队尾不一定就是0号下标或MaxSize-1号下标。

利用这个原则来判断循环链表中存储数据的到底是数组中的哪些位置：
①为了避免判别队列空间是“满”还是“空”的条件冲突，牺牲的那一个存储空间一定是在沿着从队头Q.front到队尾Q.rear顺时针方向的，队尾Q.rear的后面。
②且这个被牺牲掉的存储空间所代表的下标，可以是数组中的任意一个，不一定就是最大下标MaxSize-1处。

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

#define MAXQSIZE 100  //申请了MAXQSIZE个，可利用空间MAXQSIZE-1个

typedef int QElemType;

typedef struct
{
	QElemType* base;
	int front;
	int rear;
}SqQueue;

void InitQueue(SqQueue& Q);
void ValueQueue(SqQueue& Q);
void printQueue(SqQueue Q);
int QueueLength(SqQueue Q);


int  main()
{
	SqQueue N = { NULL,0,0 };
	InitQueue(N);

	ValueQueue(N);
	printQueue(N);

	printf("列队长度为：%d\n", QueueLength(N));
	return 0;
}

//算法3.11 循环队列的初始化
void InitQueue(SqQueue& Q)
{
	Q.base = (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);
	//申请了MAXQSIZE个，可利用空间MAXQSIZE-1个

	if (!Q.base)
	{
		printf("内存分配失败，导致初始化循环队列失败。");
		return;
	}

	Q.front = 0;
	Q.rear = 0;
	printf("初始化循环队列成功。\n");
}


//批量元素进入循环队列
void ValueQueue(SqQueue& Q)
{
	int len = 0;
	int i = 0;
	int num = 0;

	if (!Q.base) {
		printf("循环队列不存在，元素无法入栈\n");
		return;
	}

	while (1)
	{
		printf("请输入循环队列的长度：");
		scanf_s("%d", &len);

		if (len > MAXQSIZE-1)
		{
			printf("长度过大，请重新输入。\n");
			continue;
		}

		if(len <= MAXQSIZE-1)
		{
			break;
		}
	}

	for (i = 1;i <= len; i++)
	{
		printf("请输入第%d个元素的值：", i);
		scanf_s("%d", &num);

		Q.base[Q.rear] = num;
		Q.rear = (Q.rear+1)%MAXQSIZE;
	}

	printf("%d个元素已成功进入循环队列。\n", i-1);
}

//打印循环队列并求循环队列的长度
void printQueue(SqQueue Q)
{
	int i = 0;
	int temp = Q.front; 
	//打印时不建议直接修改队头的位置Q.front，使用临时变量追踪打印位置

	if (Q.front == Q.rear)
	{
		printf("打印循环队列时，队列为空。\n");
		return;
	}


	for (i = 0; i < ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE); i++)   	
	//或者是将判断条件改为：i != Q.rear，代表直到i到达了队尾Q.rear的位置即可宣告遍历的结束。
	{
		//队头的元素是先被存入队列的，从队头开始打印
		printf("%d ", Q.base[temp]);
		temp = (temp + 1) % MAXQSIZE; 
		//临时变量代表的下标在循环队列中依环状增一
	}

	printf("\nQueue_length : %d\n",i);
	/*for循环中i从0开始，对应判断条件中i<长度，对应此处长度为i；
	for循环中i从1开始，对应判断条件中 i<=长度，对应此处长度为i-1
	原因：最后一次i加1之后，不执行语句，即跳出循环；下标从0开始，其最大值比长度小1  */
}

//算法3.12 求循环队列的长度
int QueueLength(SqQueue Q)
{
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
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

3.5.1.3 循环列队的入队、出队、取队头元素

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

#define MAXQSIZE 100  //申请了MAXQSIZE个，可利用空间MAXQSIZE-1个

typedef int QElemType;

typedef struct
{
	QElemType* base;
	int front;
	int rear;
}SqQueue;

void InitQueue(SqQueue& Q);
void ValueQueue(SqQueue& Q);
void printQueue(SqQueue Q);
int QueueLength(SqQueue Q);
void EnQueue(SqQueue& Q, QElemType e);
int DeQueue(SqQueue& Q);
int GetHead(SqQueue Q);

int  main()
{
	SqQueue N = { NULL,0,0 };
	InitQueue(N);

	ValueQueue(N);
	printQueue(N);

	printf("\n列队长度为：%d\n", QueueLength(N));
	
	EnQueue(N, 999);
	printQueue(N);

	printf("\n删除队头元素：%d\n", DeQueue(N));
	printf("\n新的队头元素：%d\n", GetHead(N));

	return 0;
}

//算法3.11 循环队列的初始化
void InitQueue(SqQueue& Q)
{
	Q.base = (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);
	//申请了MAXQSIZE个，可利用空间MAXQSIZE-1个

	if (!Q.base)
	{
		printf("内存分配失败，导致初始化循环队列失败。");
		return;
	}

	Q.front = 0;
	Q.rear = 0;
	printf("初始化循环队列成功。\n");
}


//批量元素进入循环队列
void ValueQueue(SqQueue& Q)
{
	int len = 0;
	int i = 0;
	int num = 0;

	if (!Q.base) {
		printf("循环队列不存在，元素无法入栈\n");
		return;
	}

	while (1)
	{
		printf("请输入循环队列的长度：");
		scanf_s("%d", &len);

		if (len > MAXQSIZE-1)
		{
			printf("长度过大，请重新输入。\n");
			continue;
		}

		if(len <= MAXQSIZE-1)
		{
			break;
		}
	}

	for (i = 1;i <= len; i++)
	{
		printf("请输入第%d个元素的值：", i);
		scanf_s("%d", &num);

		Q.base[Q.rear] = num;
		Q.rear = (Q.rear+1)%MAXQSIZE;
	}

	printf("%d个元素已成功进入循环队列。\n", i-1);
}

//打印循环队列并求循环队列的长度
void printQueue(SqQueue Q)
{
	int i = 0;
	int temp = Q.front; 
	//打印时不建议直接修改队头的位置Q.front，使用临时变量追踪打印位置

	if (Q.front == Q.rear)
	{
		printf("打印循环队列时，队列为空。\n");
		return;
	}


	for (i = 0; i < ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE); i++)   	
	//或者是将判断条件改为：i != Q.rear，代表直到i到达了队尾Q.rear的位置即可宣告遍历的结束。
	{
		//队头的元素是先被存入队列的，从队头开始打印
		printf("%d ", Q.base[temp]);
		temp = (temp + 1) % MAXQSIZE; 
		//临时变量代表的下标在循环队列中依环状增一
	}

	printf("\nQueue_length : %d\n",i);
	/*for循环中i从0开始，对应判断条件中i<长度，对应此处长度为i；
	for循环中i从1开始，对应判断条件中 i<=长度，对应此处长度为i-1
	原因：最后一次i加1之后，不执行语句，即跳出循环；下标从0开始，其最大值比长度小1  */
}

//算法3.12 求循环队列的长度
int QueueLength(SqQueue Q)
{
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

//算法3.13 循环列队的入队
void EnQueue(SqQueue& Q, QElemType e)
{
	//插入元素e为Q的新的队尾元素
	if ((Q.rear + 1) % MAXQSIZE == Q.front)
	{
		printf("入队时，循环队列已满。\n");
		return;
	}

	Q.base[Q.rear] = e;
	Q.rear = (Q.rear +1)%MAXQSIZE;
}

//算法3.14 循环列队的出队
int DeQueue(SqQueue& Q)
{
	//删除Q的队头元素
	int e = 0;

	if (Q.front == Q.rear)
	{
		printf("删除队头元素时，循环队列为空。\n");
		return -1;
	}

	e = Q.base[Q.front];
	Q.front = (Q.front+1)%MAXQSIZE;
	return e;
}


//算法3.15 取循环列队的队头元素
int GetHead(SqQueue Q)
{
	if (Q.front == Q.rear)
	{
		printf("取队头元素时，循环队列为空。\n");
		return -1;
	}

	return Q.base[Q.front];
}
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

3.5.2 链队的表示和操作的实现

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

typedef struct QNode
{
	int data;
	struct QNode* next;
}QNode,*QueuePtr;

typedef struct
{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

void InitQueue(LinkQueue& Q);
void ValueQueue(LinkQueue& Q);
void printQueue(LinkQueue& Q);
void Enqueue(LinkQueue& Q, int e);
int DeQueue(LinkQueue& Q);
int GetHead(LinkQueue Q);

int main()
{
	LinkQueue N = { NULL,NULL };
	InitQueue(N);
	ValueQueue(N);
	printQueue(N);

	Enqueue(N,999);
	printQueue(N);

	printf("删除的链队的队头元素是：%d\n", DeQueue(N));
	printQueue(N);
	printf("\n新的链队的队头元素是：%d", GetHead(N));

	return 0;
}

//算法3.16 链队的初始化
void InitQueue(LinkQueue& Q)
{
	//构造一个空队列Q
	Q.front = (QueuePtr)malloc(sizeof(QNode)); 
	//生成新结点作为头结点。在链队中头结点可能会被修改，但始终处于队头，且头指针始终指向头结点。
	//这里分配的内存不能仅是指向结点的指针大小，而应该是指针指向的整个结构体的大小

	Q.rear = Q.front; //将尾指针指向头结点
	Q.front->next = NULL;
}

//批量元素进入链队
void ValueQueue(LinkQueue& Q)
{
	int len = 0;
	int i = 0;
	int num = 0;

	printf("请输入链队的长度：");
	scanf_s("%d", &len);

	for (i = 1; i <= len; i++)
	{
		printf("请输入第%d个元素的值：", i);
		scanf_s("%d", &num);

		QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
		s->data = num;
		s->next = NULL;

		Q.rear->next = s;
		Q.rear = s;
	}

	printf("%d个元素已入链队成功。\n", i - 1);
}

//遍历打印链队
void printQueue(LinkQueue &Q)
{
	QueuePtr pMove = Q.front->next;
	int i = 1;

	while (pMove)
	{
		printf("%d ", pMove->data);
		pMove = pMove->next;
		i++;
	}

	printf("\nQueue_length : %d\n", i);
}

//算法3.17 链队的入队
void Enqueue(LinkQueue& Q, int e)
{
	//插入元素e为Q新的队尾元素
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));

	p->data = e;
	p->next = NULL;

	Q.rear->next = p;
	Q.rear = p;
}

//算法3.18 链队的出队
int DeQueue(LinkQueue& Q)
{
	if (Q.front == Q.rear)
	{
		printf("删除队头元素时，链队为空。\n");
		return -1;
	}

	QueuePtr p = Q.front->next;
	int e = p->data;
	Q.front->next = p->next;

	/*当链队中只有一个数值时，此时p和rear指向同一个结点。
	为了避免p所指结点的内存空间被释放之后rear失去指向的对象，要先将尾指针rear指向头结点。
	删除唯一的队头元素后，链队变为空。*/
	if (Q.rear == p)
	{
		Q.rear = Q.front;
	}

	free(p);
	return e;
}

//算法3.19 取链队的队头元素
int GetHead(LinkQueue Q)
{
	if (Q.front == Q.rear)
	{
		printf("取队头元素时，链队为空。\n");
		return -1;
	}

	return Q.front->next->data;
}
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