循环队列 (顺序存储)

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MAX_SIZE 255 //循环队列的最大容量

typedef struct C_Queue {
	int data[MAX_SIZE];  //指定循环队列大小
	int front;       //循环队列头指针
	int rear;	//循环队列尾指针
} *Queue;


注意：结构体后面的*Queue是指向C_Queue的结构体指针，
如果不加*，使用结构体指针需要Queue *q这样，
加了*，使用结构体指针，只需Queue q即可；

1
2
3
4
5
6
7
Queue queue_create() {
	Queue q = (Queue)malloc(sizeof(C_Queue)); //给循环队列分配内存空间
	q->front = q->rear = 0;  //初始状态下，头指针和尾指针 均指向0(下标)

	return q;
}

1
2
3
4
5
6
7
8
boolean queue_empty(Queue q) {
	if (q->front == q->rear) {  //当front和rear相等时，队列为空
		return TRUE;
	} else {
		return FALSE;
	}
}

1
2
3
4
5
6
7
8
boolean queue_full(Queue q) {
	if ((q->rear + 1) % MAX_SIZE == q->front) {
		return TRUE;
	} else {
		return FALSE;
	}
}

1
2
3
4
int queue_length(Queue q) {
	return (q->rear - q->front + MAX_SIZE) % MAX_SIZE;
}

1
2
3
4
5
6
7
8
9
10
11
boolean queue_rear_insert(Queue q, int x) {
	if (queue_full(q)) { //判断队满
		printf("队列已满！n");
		return FALSE;
	} else {
		q->data[q->rear] = x; //先将元素插入尾指针原本指向的位置
		q->rear = (q->rear + 1) % MAX_SIZE; //尾指针+1
		return TRUE;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
int queue_front_delete(Queue q) {
	int x;
	if (queue_empty(q)) {
		printf("队列无元素可删除！n");
		return 0;
	} else {
		x = q->data[q->front];  //用x记录头指针指向的元素值
		q->front = (q->front + 1) % MAX_SIZE;  //头指针front + 1，并%MAX_SIZE取模
		return x;
	}
}

1
2
3
4
5
6
7
int queue_get_front(Queue q) {
	if (!queue_empty(q)) {
		return q->data[q->front];
	}
	return 0;
}

1
2
3
4
5
6
7
void queue_items_printf(Queue q) {
	while (!(q->front == q->rear)) {
		printf("%d ", q->data[q->front]);  //输出头指针front指向元素的值
		q->front = (q->front + 1) % MAX_SIZE;  //头指针front + 1
	}
}

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
#include <stdio.h>
#include <stdlib.h>

typedef enum {FALSE, TRUE} boolean;

#define MAX_SIZE 8 //循环队列的最大长度

//结构体
typedef struct C_Queue {
	int data[MAX_SIZE];  //指定循环队列大小
	int front;       //循环队列头指针
	int rear;	//循环队列尾指针
} *Queue;

//创建队列
Queue queue_create() {
	Queue q = (Queue)malloc(sizeof(C_Queue)); //给循环队列分配内存空间
	q->front = q->rear = 0;  //初始状态下，头指针和尾指针 均指向0(下标)
	if (q == NULL) { //内存分配失败
		return NULL;
	}
	return q;
}

//队列判空
boolean queue_empty(Queue q) {
	if (q->front == q->rear) {  //当front和rear相等时，队列为空
		return TRUE;
	} else {
		return FALSE;
	}
}

//队列判满
boolean queue_full(Queue q) {
	if ((q->rear + 1) % MAX_SIZE == q->front) {
		return TRUE;
	} else {
		return FALSE;
	}
}

//队列长度
int queue_length(Queue q) {
	return (q->rear - q->front + MAX_SIZE) % MAX_SIZE;
}

//队尾插入元素
boolean queue_rear_insert(Queue q, int x) {
	if (queue_full(q)) {
		printf("队列已满！n");
		return FALSE;
	} else {
		q->data[q->rear] = x;
		q->rear = (q->rear + 1) % MAX_SIZE;
		return TRUE;
	}
}

//队头删除元素
int queue_front_delete(Queue q) {
	int x;
	if (queue_empty(q)) {
		printf("队列无元素可删除！n");
		return 0;
	} else {
		x = q->data[q->front];
		q->front = (q->front + 1) % MAX_SIZE;
		return x;
	}
}

//获取队头元素
int queue_get_front(Queue q) {
	if (!queue_empty(q)) {
		return q->data[q->front];
	}
	return 0;
}


//将队列所有元素出队
void queue_items_printf(Queue q) {
	while (!(q->front == q->rear)) {
		printf("%d ", q->data[q->front]);
		q->front = (q->front + 1) % MAX_SIZE;
	}
}


int main() {
	/* 创建一个循环队列 */
	Queue q = queue_create();
	int A[8], i;

	if (NULL == q) {
		printf("队列创建失败！n");
		return -1;
	}

	printf("当前队列长度为：%dn", queue_length(q));

	printf("输入要入队的元素: ");
	for (i = 0; i < 8; i++) {
		scanf("%d", &A[i]);
	}
	//将数组中的元素按顺序插入循环队列
	for (i = 0; i < 8 ; i++) {
		queue_rear_insert(q, A[i]);
	}
	printf("当前队头元素为：%dn", queue_get_front(q));
	printf("n当前队列长度为：%dn", queue_length(q));


	printf("n队列元素出队顺序：");
	//将循环队列所有元素出队，并输出
	queue_items_printf(q);
	printf("n当前队列长度为：%dn", queue_length(q));

	return 0;
}