【C语言 数据结构】队列 - 链式、顺序

---

---

队列 - 链式、顺序

一、概念

1.和栈不同的是，队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端进行删除操作

• 队尾：允许插入的一端
• 队头：允许删除的一端
  

2.在队列的形成过程中，可以利用线性链表的原理，来生成一个队列。

• 基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。

3.队列采用的 FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。

1.1 队列的定义

// 定义队列数据类型
typedef int QDataType;
// 定义队列节点
typedef struct QueueNode{
 struct QueueNode* next; // 节点link
 QDataType data; // 节点数据
}QNode;
// 定义队列
typedef struct Queue{
 QNode* head; // 定义头指针
 QNode* tail; // 定义尾指针
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12

返回顶部

---

1.2 队列的初始化

// 队列初始化
void QueueInit(Queue* pq){
 assert(pq); // 断言
 pq->head = pq->tail = NULL; // 置空
}
1
2
3
4
5

返回顶部

---

1.3 队列的销毁

// 队列的销毁
void QueueDestroy(Queue* pq){
 assert(pq); // 断言
 QueueNode* cur = pq->head; // 定义临时节点遍历 
 while (cur){
  // 保存下一个节点的地址
  QueueNode* next = cur->next;
  // 释放空间
  free(cur);
  // 指向下一个节点
  cur = next;
 }
 // 置空
 pq->head = pq->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

返回顶部

---

1.4 队列的判空

// 队列的判空
int QueueIsEmpty(Queue* pq){
 assert(pq); // 断言
 return pq->tail == NULL;
}
1
2
3
4
5

返回顶部

---

1.5 队列的尾插

// 对列的插入
void QueuePush(Queue* pq,QDataType x){
 // 断言
 assert(pq);
 // 创建新的队列节点
 QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
 if(newNode == NULL){
 	printf("创建空间失败！");
    	exit(-1);
 }
 // 节点赋值
 newNode->data = x;  
 newNode->next = NULL;
 // 如果是空队列
 if(pq->head==NULL){
  	// 当前节点作为队列的第一个元素节点
  	pq->head = pq->tail = newNode;
 }else {
 	 // 如果不是空队列那么，上一个节点的link指向newNode，且将尾指针指向新节点
  	pq->tail->next = newNode;
  	pq->tail = newNode;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

返回顶部

---

1.6 队列的头删

// 队列的头删 
void QueueHeadPop(Queue* pq){
	// 断言
	assert(pq);
	// 判空
	assert(!QueueIsEmpty(pq));
	// 如果不是空，只允许头删，那么就是将头指针后一个节点即可
	QueueNode* next = pq->head->next;
	free(pq->head);  // 释放当前head指向的节点 - 删除的头节点
	pq->head = next; // 头指针后移

	// 判空,如果删完了,不能再删了
	if(pq->head ==NULL){
		pq->tail = NULL;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

返回顶部

---

1.7 取队头、取队尾

// 取队头
QDataType QueueFront(Queue* pq){
	// 断言
	assert(pq);
	// 判空
	assert(!QueueIsEmpty(pq));
	return pq->head->data;
}

// 取队尾
QDataType QueueBack(Queue* pq){
	// 断言
	assert(pq);
	// 判空
	assert(!QueueIsEmpty(pq));
	return pq->tail->data;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

返回顶部

---

1.8 获取队列的元素个数

// 获取队列的元素个数
int QueueLength(Queue* pq){
	// 断言
	assert(pq);
	int i = 0; // 计数
	QueueNode* curr = pq->head;
	// 遍历
	while(curr){
		i++; 
		curr = curr->next;
	}
	return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

返回顶部

---

1.9 打印队列

// 打印队列
void QueuePrint(Queue* pq){
	// 断言 
	assert(pq);
	// 判空
	assert(!QueueIsEmpty(pq));
	// 创建临时节点
	QueueNode* curr = pq->head;
	// 遍历
	while(curr){
		printf("%d->",curr->data); 
		curr = curr->next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

返回顶部

---

二、循环队列 - 顺序

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。

循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。

因此，队列判空的条件是front=rear，而队列判满的条件是front=（rear+1)%MaxSize。

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#define  MAX_SIZE  6

typedef char CQDataType;
typedef struct {
	CQDataType *base;
	int front;   // 头
	int rear;    // 尾
} SqQueue;

// 队列初始化
void InitQueue(SqQueue* Q){
	Q->base= (CQDataType*)malloc(MAX_SIZE*sizeof(CQDataType));
	if (Q->base== NULL) exit(-1);
	Q->front = 0;
	Q->rear = 0;
}
 //入队元素
void PushQueue(SqQueue* Q, CQDataType data)  {
	assert(Q); // 断言
    // 队满
	if ((Q->rear + 1) % MAX_SIZE == Q->front)   {
		printf("full!");
		exit(-1);
	}
	Q->base[Q->rear] = data;//当前尾指针处添加数据
	Q->rear = (Q->rear + 1) % MAX_SIZE;//尾指针向前移动
}
//出队元素
void PopQueue(SqQueue* Q, int* e)    {
	assert(Q); // 断言
    if (Q->front == Q->rear){
		printf("empty");
		exit(-1);
	}
	*e = Q->base[Q->front];
	Q->front = (Q->front + 1) % MAX_SIZE; //头指针向前移动
}


// 求当前队列长度
int queueLength(SqQueue* Q) {
	assert(Q); // 断言
	return ((Q->rear) - (Q->front) + MAX_SIZE) % MAX_SIZE;
} 

// 输出队列中的数据元素 
int PrintQueue(SqQueue* Q){
	assert(Q); // 断言
	if (Q->rear == Q->front){
		printf("当前队列为空队列\n");
	}
	while (Q->front != Q->rear){
		printf("该队列的第%d个的值为:%c\n", Q->front, Q->base[Q->front]);
		Q->front = (Q->front + 1) % MAX_SIZE;
	}
	return 0;
}

int main() {
	SqQueue Q;
	InitQueue(&Q);
	PushQueue(&Q, 'A');
	printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
	PushQueue(&Q, 'B');
	printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
	PushQueue(&Q, 'C');
	printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
	PushQueue(&Q, 'D');
	printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
	PushQueue(&Q, 'E');
	printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
	PushQueue(&Q, 'F');
	printf("当前循环队列的元素个数为：%d\n", queueLength(&Q));
	// 输出队列
	PrintQueue(&Q);

	system("pause");
	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

返回顶部

---