循环队列的数组实现（）

106 阅读 0 评论 70 点赞

我是靠谱客的博主含蓄小懒虫，这篇文章主要介绍循环队列的数组实现（），现在分享给大家，希望可以做个参考。

理论知识

由于顺序存储的队列会产生“假溢出的情况”，我们可以将队列的存储结构臆想为一个闭合的环状结构，这便是我们所说的循环队列，如下图所示。
假溢出图示循环队列的逻辑结构
在这里插入图片描述但是循环队列中，判断队空和堆满的条件都是Q.rear = Q.front,这给我们的编程实现带来了很多麻烦，这样我们会有三种处理方法，
1.牺牲一个存储单元，入队的时候将队头指针在队尾指针的下一位置最为队列满的条件
这是判断队空的条件仍然是：Q.rear = Q.front
但是判断队满的条件变为：(Q.rear+1)%MAXSIZE = Q.front
队列中元素的个数为:(Q.rear-Q.front+MAXSIZE)%MAXSIZE
2.在结构体的定义中增加表示元素个数的成员
队空：Q.size = 0
队满：Q.size = MAXSIZE
队列元素个数：Q.size
3.第一种情况牺牲的存储空间利用起来，当flag = 0时，因为删除发生了Q.rear = Q.front 则表示队空，当flag = 1时，因为增加导致了Q.rear = Q.front 则表示队满

以下使用第一种方法进行代码实现

存储结构

复制代码

1
2
3
4
5
typedef struct {
	int data[MAXSIZE];
	int front,rear;
}Quene;

初始化

复制代码

1
2
3
4
5
//初始化
void initQuene(Quene &Q){
	Q.rear = Q.front = 0;
}

判空

复制代码

1
2
3
4
5
6
7
8
bool isEmpty(Quene &Q){
	if((Q.rear+1)%MAXSIZE == Q.front){
		cout<<"队列已满"<<endl;
		return true;
	}
	return false;
}

入队

复制代码

1
2
3
4
5
6
7
8
9
10
//入队
bool push(Quene &Q,int e){
	if(!isEmpty(Q)){
		Q.data[Q.rear] = e;
		Q.rear = (Q.rear+1) % MAXSIZE;
		return true; 
	}
	return false;
}

出队

复制代码

1
2
3
4
5
6
7
8
9
10
11
//出队
bool pop(Quene &Q){
	if(Q.rear == Q.front){
		return false;
	}else{
		Q.data[Q.front] = -1;
		Q.front = (Q.front+1)%MAXSIZE;
		return true;
	}
}

整合测试

复制代码

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
#include<iostream>
using namespace std;
#define MAXSIZE 4
typedef struct {
	int data[MAXSIZE];
	int front,rear;
}Quene;
//初始化
void initQuene(Quene &Q){
	Q.rear = Q.front = 0;
}
//判空 
bool isEmpty(Quene &Q){
	if((Q.rear+1)%MAXSIZE == Q.front){
		cout<<"队列已满"<<endl;
		return true;
	}
	return false;
}
//入队
bool push(Quene &Q,int e){
	if(!isEmpty(Q)){
		Q.data[Q.rear] = e;
		Q.rear = (Q.rear+1) % MAXSIZE;
		return true; 
	}
	return false;
}
//出队
bool pop(Quene &Q){
	if(Q.rear == Q.front){
		return false;
	}else{
		Q.data[Q.front] = -1;
		Q.front = (Q.front+1)%MAXSIZE;
		return true;
	}
}
int main()
{
	Quene Q;
	initQuene(Q);
	push(Q,1);
	cout << Q.data[Q.rear-1] << endl;
	push(Q,2);
	cout << Q.data[Q.rear-1] << endl;
	push(Q,3);
	cout << Q.data[Q.rear-1] << endl;
	push(Q,4);
	cout << Q.data[Q.front] << endl;
	pop(Q);
	cout << Q.data[Q.front] << endl;
	pop(Q);
	cout << Q.data[Q.front] << endl;
	return 0;
 }