顺序循环队列

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
#include <stdio.h>
#include <stdlib.h>
// 队列最大长度
#define MAXQSIZE 100

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// ElemType 顺序队列的数据类型
typedef char QElemType;

// 顺序队列的结构
typedef struct {
	// 初始化动态分配存储空间
	QElemType* base;
	// 头指针
	int front;
	// 尾指针
	int rear;
}SqQueue;

// 循环队列的初始化
Status initQueue(SqQueue& Q) {
	// c++语法
	Q.base = new QElemType(MAXQSIZE);
	// c语法
	// Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
	if (!Q.base) exit(OVEREFLOW);
	// 头指针和尾指针都指向队头
	Q.front = Q.rear = 0;
	return OK;
}

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

// 循环队列入队
Status EnQueue(SqQueue& Q, QElemType e) {
	if ((Q.rear + 1) % MAXQSIZE == Q.front) exit(OVEREFLOW);
	Q.base[Q.rear] = e;
	// 尾指针加一
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return OK;
}

// 循环队列出队
Status InQueue(SqQueue& Q, QElemType& e) {
	if (Q.front == Q.rear) return ERROR;
	// 保存对头元素
	e = Q.base[Q.front];
	// 头指针加一
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}

// 取队头元素
QElemType getTop(SqQueue& Q) {
	// 队列不为空，取出队头元素
	if (Q.front != Q.rear) {
		return Q.base[Q.front];
	}
}

int main() {
	SqQueue Q;
	// 初始化队列
	initQueue(Q);
	// 入队
	for (int i = 0; i < 2; i++) {
		EnQueue(Q, i);
	}
	// 判断队列长度
	printf("队列长度：%d\n", QueueLength(Q));
	// 出队
	QElemType e;
	InQueue(Q, e);
	printf("出队元素：%d\n", e);
	// 取对头元素
	printf("队头元素：%d\n", getTop(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
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
#include <stdio.h>
#include <stdlib.h>

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// ElemType 队列的数据类型
typedef char QElemType;

// 链队的结构定义
typedef struct Qnode {
	QElemType data;
	struct Qnode* next;
}QNode, *QueuePtr;

// 链队的指针结构定义
typedef struct {
	// 头指针
	QueuePtr front;
	// 尾指针
	QueuePtr rear;
}LinkQueue;

// 链队的初始化
Status initQueue(LinkQueue& Q) {
	// 头指针和尾指针指向头结点
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q.front) exit(OVEREFLOW);
	// 头结点的指针域置为空
	Q.front->next = NULL;
	return OK;
}

// 链队的销毁
Status DestoryQueue(LinkQueue& Q) {
	/*QueuePtr p;
	while (Q.front) {
		p = Q.front->next;
		free(Q.front);
		Q.front = p;
	}*/
	while (Q.front) {
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
	return OK;
}

// 入队
Status EnQueue(LinkQueue& Q, QElemType e) {
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if (!p) exit(OVEREFLOW);
	p->data = e;
	p->next = NULL;
	// 将指针p指向的结点接在尾指针后面
	Q.rear->next = p;
	// 将尾指针更新为p指针，指向链队尾部
	Q.rear = p;
	return OK;
}

// 出队
Status InQueue(LinkQueue& Q, QElemType& e) {
	if (Q.rear == Q.front) return ERROR;
	QueuePtr p = Q.front->next;
	e = p->data;
	// 删除指针p指向的结点
	Q.front->next = p->next;
	// 如果此时出队元素为最后一个元素，那么也需要把尾指针也更新为指向头结点
	if (Q.rear == p) Q.rear = Q.front;
	// 释放
	free(p);
	return OK;
}

// 取队头元素
QElemType getHead(LinkQueue& Q) {
	// 队列为空
	if (Q.rear == Q.front) return ERROR;
	return Q.front->next->data;
}

int main(){
	LinkQueue Q;
	// 初始化链队
	initQueue(Q);
	// 入队
	for (int i = 0; i < 2; i++) {
		EnQueue(Q, i);
	}
	// 出队
	QElemType e;
	InQueue(Q, e);
	printf("出队元素：%d\n", e);
	// 取队头元素
	printf("队头元素：%d\n", getHead(Q));
	// 销毁链队
	DestoryQueue(Q);
	return 0;
}