C语言实现循环队列_c语言循环双向队列数组法实现

1.C语言版本

循环队列我是基于动态数组的优化实现的

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define DEFAULT_CAPACITY 10
#define ELEMENT_NOT_FOUND -1
// 我们的循环队列是基于队列实现的 所以说只能够在队尾入队 队头出队 而且这次循环队列我们就要基于数组实现了 而不是队列的基于实现--双向链表
int size;// 数组元素个数
int front;// 首元素的位置标识
// 初始化一个循环队列
int* initCircleQueue(int capacity) {
	// 首先设置好容量
	capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
	int* array = (int*)malloc(sizeof(int) * capacity);
	return array;
}
// 队尾入队
void enQueue(int data, int* array, int capacity) {
	// 由于队尾入队可能会导致队尾无法容纳指定元素 所以得得往队头继续进行添加操作 所以需要使用取模运算符
	// 获取数组容量
	int length = capacity;
	array[(front + size) % length] = data;
	// 更新队列长度
	size++;
}
// 队头出队
int deQueue(int* array, int capacity) {
	// 对队列进行判空操作
	if (size == 0)return -1;
	// 由于队头出队会导致队头元素更新 而队头元素很有可能从队尾移动到队头 所以说我们需要进行取模运算才行
	// 获取数组长度
	int length = capacity;
	int data = array[front];
	front = (front + 1) % length;
	// 更新队列长度
	size--;
	return data;
}
// 获取队头元素
int get(int* array) {
	// 对队列进行判空操作
	if (size == 0)return -1;
	return array[front];
}
// 对队列执行清空操作
void clear(int* array) {
	size = 0;
	front = 0;
}
// 获取队列长度
int getSize() {
	return size;
}
// 打印函数
void printCircleQueue(int* array, int capacity) {
	int length = capacity;
	for (int i = front; i < (front + size) % length; ++i) {
		printf("%d ", array[i]);
	}
	printf("\n");
}
int getLength(int* array) {
	int count = 0;
	while (array[count]) {
		count++;
	}
	return count;
}
// 定义一个主函数
int main() {
	int* circleQueue = initCircleQueue(8);
	int capacity = getLength(circleQueue);
	enQueue(1, circleQueue, capacity);
	enQueue(2, circleQueue, capacity);
	enQueue(3, circleQueue, capacity);
	printCircleQueue(circleQueue, capacity);// 1 2 3
	deQueue(circleQueue, capacity);// 2 3
	printCircleQueue(circleQueue, capacity);// 2 3
	printf("%d\n", get(circleQueue));// 2
	clear(circleQueue);
	printf("%d\n", getSize());// 0
	printf("%d\n", front);// 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

2.循环队列的升级

既然动态数组的添加方法有对数组是否需要扩容的判断 那么现在的循环队列也需要有这一步操作
并且由于enQueue、deQueue以及printCircleQueue这些方法中均使用到了将索引还原成真实索引的操作 所以我们何不将其封装成一个函数供这些函数调用呢
改进后的代码如下所示

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define DEFAULT_CAPACITY 10
#define ELEMENT_NOT_FOUND -1
// 我们的循环队列是基于队列实现的 所以说只能够在队尾入队 队头出队 而且这次循环队列我们就要基于数组实现了 而不是队列的基于实现--双向链表
int size;// 数组元素个数
int front;// 首元素的位置标识
// 初始化一个循环队列
int* initCircleQueue(int capacity) {
	// 首先设置好容量
	capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
	int* array = (int*)malloc(sizeof(int) * capacity);
	return array;
}
// 判断是否需要进行数组扩容操作
void ensureCapacity(int size, int* array, int capacity) {
	// 如果参数元素个数小于等于旧数组的容量的话 那么说明无需进行扩容操作
	if (size <= capacity)return;
	// 否则就要重置数组的容量
	int newCapacity = capacity + (capacity >> 1);
	int* newArray = (int*)malloc(sizeof(int) * newCapacity);
	for (int i = 0; i < capacity; ++i) {
		newArray[i] = array[(front + i) % capacity];
	}
	// 然后让旧数组指向新申请的数组对象
	array = newArray;
	// 重置首元素的标识
	front = 0;
}
// 索引映射方法
/*
	enQueue--array[(front + size) % length] = data;
	deQueue--front = (front + 1) % length;
	ensureCapacity……
	我们可以发现这些语句的共性就是都将一个指定的索引还原成了其真实的索引 所以我们可以将其封装成一个函数 供其他函数进行调用
*/
int index(int index, int length) {
	index = (front + index) % length;
	return index;
}
// 队尾入队
void enQueue(int data, int* array, int capacity) {
	// 判断数组是否需要进行扩容操作
	ensureCapacity(size + 1, array, capacity);
	// 由于队尾入队可能会导致队尾无法容纳指定元素 所以得得往队头继续进行添加操作 所以需要使用取模运算符
	// 获取数组容量
	int length = capacity;
	array[index(size, length)] = data;
	// 更新队列长度
	size++;
}
// 队头出队
int deQueue(int* array, int capacity) {
	// 对队列进行判空操作
	if (size == 0)return -1;
	// 由于队头出队会导致队头元素更新 而队头元素很有可能从队尾移动到队头 所以说我们需要进行取模运算才行
	// 获取数组长度
	int length = capacity;
	int data = array[front];
	front = index(1, length);
	// 更新队列长度
	size--;
	return data;
}
// 获取队头元素
int get(int* array) {
	// 对队列进行判空操作
	if (size == 0)return -1;
	return array[front];
}
// 对队列执行清空操作
void clear(int* array) {
	size = 0;
	front = 0;
}
// 获取队列长度
int getSize() {
	return size;
}
// 打印函数
void printCircleQueue(int* array, int capacity) {
	int length = capacity;
	for (int i = front; i < index(size, length); ++i) {
		printf("%d ", array[i]);
	}
	printf("\n");
}
int getLength(int* array) {
	int count = 0;
	while (array[count]) {
		count++;
	}
	return count;
}
// 定义一个主函数
int main() {
	int* circleQueue = initCircleQueue(8);
	int capacity = getLength(circleQueue);
	enQueue(1, circleQueue, capacity);
	enQueue(2, circleQueue, capacity);
	enQueue(3, circleQueue, capacity);
	printCircleQueue(circleQueue, capacity);// 1 2 3
	deQueue(circleQueue, capacity);// 2 3
	printCircleQueue(circleQueue, capacity);// 2 3
	printf("%d\n", get(circleQueue));// 2
	clear(circleQueue);
	printf("%d\n", getSize());// 0
	printf("%d\n", front);// 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

结果显示 正常的测试可以通过
但是现在我们专门测试一下ensureCapacity功能是否合理

1