循环队列（详解）---＞数据结构、C++实现

问题引入

        在数据结构中，队列也是一种重要的线性结构，常和栈放在一起进行学习。队列分为多种类型，常见的如循环队列、链队列等，如果此时此刻你对“循环队列”感到困惑，那就继续看下去，我们一步一步去剖析。

        本文主要讲述“循环队列”，如果想要进一步学习“链队列”，

        请看文章  “链队列（详解）--->数据结构（队列）”（点击查看）。

问题分析（很重要）

        如果想要搞明白队列，首先你要明白两个问题：

        1.什么是队列？

        答：“队列”（queue）是一种“先进先出”的线性表。

        2.队列的特点是什么？

        答：队列只允许在表的一端进行插入元素，在另一端删除元素。

        通过上面两个问题，综合到一起就是，队列也是一种线性表，有两端，一端是队列的开头，一端是队列的结尾，例如：& 1 2 3 4 5 6 #，“&”就相当于队列的头，“#”就相当于队列的尾。同时，队列是“先进先出”的特点，一端进行插入，一端进行删除，例如：& 1 2 3 4 5 6 #，我们要插入元素必须从队尾#后进行插入，删除元素必须从&开始删除，只有这种顺序才能满足队列“先进先出”的特点，因为排在队头的一定是先到来的。（如果迷糊，不妨再多看一遍。）

        如下图所示，顺序由0-8,0是队头，元素从队尾进入，从队头删除。

循环队列整体结构分析

        循环队列中所谓的“循环”就是指“在指定长度的队列中，只有队列中有空位，数据就可以重复的利用这个位置存储数据”，由于不断的重复，类似循环，因此称为“循环队列”。

        既然涉及到元素出、入队列，结合队列的特点，“队头删除元素，队尾插入元素”，因此我们借助队头（front）、队尾（rear）两个指针进行“移动指定”，实现在队头、队尾的不同操作，两者互不影响。如下图，两指针初始位置均在队头，如果插入元素则队尾指针rear后移，如若删除元素则删除元素后队头指针front也后移。如果仍然感到困惑，接下来我们分过程去看元素入循环队列和出循环队列的过程。

 

元素入循环队列分析

        为什么要借助队头、队尾指针记录位置？因此队列特点为“先进先出”，队头删除元素，队尾插入元素，因此必须要时刻知道目前所在位置以及队列是否满了才能正确进行操作。

        例如：

                        在循环队列中插入元素77。

        分析：首先，我们要确保rear指向一个空白的位置，如图1；其次，将数据记录在rear所指位置中，之后将rear向后移一位。等待下一数据的插入，如图2。如果rear后移过程中队列满了该如何判断呢，我们则通过“公式”进行计算，“(队尾指针rear位置+1)%队列的长度==队头指针front位置”，如果满足这个关系式，那么队列中就不能再插入元素。

 

图1

 

图2

元素出循环队列分析

         例如：

                        在循环队列中删除元素11。

        明白了元素入队列，那么元素的出队列与入队列相似，我们只在队头删除数据，那么只要将队头指针front所指向位置的元素删除，如图1；之后将队头指针front后移即可，如图2。

 图1

 图2

代码实现

        说明：采用C++语言，编译环境为DevC++。

//导入头文件
#include<malloc.h>
#include<stdio.h>
#include<iostream>
using namespace std;
#define queueSize 9 //定义队列长度为 9 (根据需要修改 长度值 即可) 
 
//创建队列结构
typedef struct{
	int *base; //基址 
	int front; //队头指针
	int rear; //队尾指针 
}SqQueue;
 
//初始化队列
void initQueue(SqQueue &Q){
	Q.base=(int *)malloc(queueSize*sizeof(int)); //分配队列长度个存储空间
	Q.front=Q.rear=0; //队头、队尾指向起始空间 
} 
 
//数据元素入队列
void createQueue(SqQueue &Q,int e){
	if((Q.rear+1)%queueSize==Q.front) {
		cout<<"当前队列元素满了，无法再输入"<<endl;
	}
	Q.base[Q.rear]=e; //插入数据元素 
	Q.rear=(Q.rear+1)%queueSize; //队尾指针后移一位
	cout<<"元素"<<e<<"已入队列"<<endl<<endl;
} 
 
//求当前队列长度
int queueLength(SqQueue Q){ 
	return (Q.rear-Q.front+queueSize)%queueSize;
} 
 
//数据元素出队列
int deleteQueue(SqQueue &Q,int &e){
	if(Q.front==Q.rear){
		cout<<"队列为空，已无数据元素"<<endl;
	}
	e=Q.base[Q.front]; //删除并由e返回数据元素 
	Q.front=(Q.front+1)%queueSize; //队头指针后移一位 
	return e;
} 
 
//输出队列中的数据元素 
void printQueue(SqQueue Q){
	while(Q.rear!=Q.front){
		cout<<Q.base[Q.front]<<' '; //从队头到队尾输出队列中元素 
		Q.front=(Q.front+1)%queueSize;
	}
	
} 
 
int main(){
	SqQueue Q;
	int e,n,choose;
	initQueue(Q);
	cout<<"选择操作：0-退出，1-入队列，2-出队列，3-输出验证"<<endl<<endl;
	cin>>choose;
	while(choose!=0){
		switch(choose){
			case 1:{
				cout<<"请输入数据元素："<<endl;
				cin>>e;
				createQueue(Q,e);
				break;
			}
			case 2:{
				n=1; //传入数据元素输出载体 
				cout<<"元素"<<deleteQueue(Q,n)<<
				"已出队列"<<endl<<endl;
				break;
			}
			case 3:{
				printQueue(Q);
				cout<<endl; //换行
				cout<<"当前队列长度为："<<queueLength(Q)<<endl<<endl; 
				break;
			}
			default:
				cout<<"\n操作不正确，请重新选择！\n";
				
		}
		cin>>choose;//记录选择操作 
	}
}

运行结果

 

写在最后：

        读两遍下来，如果仍然有不清楚的地方，可在评论区留言。

        如果你有其他感到困惑的问题，欢迎留言。