数组 和 链表是最基本的数据结构，栈、队列、树、图等复杂数据结构都是基于数组或链表方式存储

队列(Queue)特征：

• 循环队列的顺序存储是基于数组来实现的

• 队列是一种操作受限的线性表。队列只能在表的一端进行插入操作，在另一端进行删除操作。其中，允许插入的一端叫队尾，允许删除的一端叫队头。【遵守: 先进先出(First In First Out，FIFO) 规则，例如元素A、B、C、D依次入队，则出队顺序也必须是A、B、C、D】

注意咯：很多初学者都容易将 队头 和 队尾 搞混，以为元素是在队头插入在队尾删除。

循环队列特征：

• 循环队列是对队列的一种改进，主要是为了解决队尾溢出而实际上数组仍有空余空间这种“假溢出”（如图一）问题

• 循环队列的rear和front到达队尾端点，能折回数组开始处。相当于将数组首尾相连，想象 成环状（如图二）。

头指针Front 和 尾指针Rear：

• 循环队列中，一般头指针front指向队头元素，尾指针rear指向队尾元素的下一个元素；或者 头指针front指向队头元素的下一个元素，尾指针rear指向队尾元素。 这样的目的是满足front == rear判空条件

循环队列 - 结构体

#define MAX_SIZE 255 //循环队列的最大容量

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


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

循环队列 - 创建

• 【通过malloc()函数动态创建一个循环队列】

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

	return q;
}

循环队列 - 判空

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

循环队列 - 判满

• rear 和 front的值相等时（图一和图二），队列可能出现队空或队满两种情况，从而无法判别队满还是队空。

• 针对这一问题，解决方法有两种：

    1. 定义一个变量size来记录当前队列的元素个数【队尾插入一个元素，size+1； 队头删除一个元素，size-1】

    2. 牺牲一个存储单元（如图三），在队尾指针rear+1就能赶上队头指针front时，我们就认为队满了。【即：循环队列最大实际长度 = MAX_SIZE - 1】，这种方法的队满条件是：(q->rear+1)%MAX_SIZE == q->front 【记得%MAX_SIZE取模 ，否则可能会超出数组最大下标】，下面用的就是这种方法。

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

循环队列 - 求长度

• 【由图可知：MAX_SIZE = 8，q->rear = 1，q->front = 3，队列长度length = 6】

• 验证一下：(q->rear - q->front + MAX_SIZE) % MAX_SIZE; 是不是可以求队列长度。（length = (1 - 3 + 8) % 8 = 6，没毛病）
  

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

循环队列 - 入队

• 队尾插入元素，入队前要先判断循环队列是否已满

• 先将待入队的元素，插入尾指针原本指向的位置

• 尾指针rear + 1，并%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; //尾指针+1
		return TRUE;
	}
}

循环队列 - 出队

• 队头删除元素，出对前要先判断循环队列是否为空

• 用x记录，要出队元素的值，作为函数的返回值

• 头指针front + 1，并%MAX_SIZE取模。【模MAX_SIZE后，当头指针指向数组下标最大值时，可以让头指针折回数组开始处】

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;
	}
}

循环队列 - 获取队头元素

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]);  //输出头指针front指向元素的值
		q->front = (q->front + 1) % MAX_SIZE;  //头指针front + 1
	}
}

整个程序代码

#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("当前队列长度为：%d\n", 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("当前队头元素为：%d\n", queue_get_front(q));
	printf("\n当前队列长度为：%d\n", queue_length(q));


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

	return 0;
}

循环队列总结：

1. 循环队列的两个状态

• 队空状态：q->front = q->rear

• 队满状态：(q->rear + 1) % MAX_SIZE = q->front

2. 循环队列的三个操作

• 求队列长度：length = (q->rear - q->front + MAX_SIZE) % MAX_SIZE

• 元素 x 入队：q->data[q->rear] = x ;   q->rear = (q->rear + 1) % MAX_SIZE ;

• 元素 x 出队：x = q->data[q->front] ;   q->front = (q->front + 1) % MAX_SIZE ;

来几道题目巩固下

1. 循环队列存储在数组A[0…n]中，则入队时的操作为：__ rear = (rear+1) mod (n+1) __

• 解析：因为数组下标是从0开始的，所以数组的最大容量为n+1，即循环队列的MAX_SIZE = n+1，入队操作为：(q->rear + 1) % MAX_SIZE = (rear + 1) mod (n + 1) 【mod是%的意思，N mod M = N % M】

2. 已知循环队列的存储空间为数组A[21]，front指向队头元素的前一个位置，rear指向队尾元素，假设当前front和rear的值分别为8和3，则该队列的长度为：__ 16 __

• 解析：length = (q->rear - q->front + MAX_SIZE) % MAX_SIZE = (3 - 8 + 21) % 21 = 16

循环队列JAVA语言实现

c++实现循环队列中的基本操作：

1、循环队列的初始化
2、循环队列的入队
3、循环队列的出队
4、循环队列的取值
5、循环队列的求长
6、循环队列的判空
7、循环队列的清空
8、循环队列的销毁
9、循环队列的打印

有了用C++实现顺序表和顺序栈的基础后，编写循环队列的代码就会容易很多，相应的链接如下：
C++实现顺序表_平头哥melo的博客-CSDN博客
C++实现顺序栈_平头哥melo的博客-CSDN博客

 代码实现：

//Date：2021/11/16

#include <iostream>
using namespace std;
#define Maxsize 100
#define QElemType int//QElemType类型可根据实际情况自行设定

//*****************************队列的顺序存储结构******************************
typedef struct
{
	QElemType* base;
	int front;
	int rear;
}SqQueue;

//***************************循环队列的基本操作函数****************************

//循环队列的初始化
int InitQueue(SqQueue& Q)
{
	//构造一个空队列Q
	Q.base = new QElemType[Maxsize];//为队列分配一个最大容量为Maxsize的数组空间
	if (!Q.base)
		exit(OVERFLOW);//存储分配失败
	Q.front = Q.rear = 0;//头指针和尾指针置为零，队列为空
	return 0;
}

//循环队列的入队
bool EnQueue(SqQueue& Q, QElemType e)
{
	//插入一个元素e为Q的新的队尾元素
	if ((Q.rear + 1) % Maxsize == Q.front)
		return false;//队满
	Q.base[Q.rear] = e;//新元素插入队尾
	Q.rear = (Q.rear + 1) % Maxsize;//队尾指针加1
	return true;
}

//循环队列的出队
bool DeQueue(SqQueue& Q, QElemType& e)
{
	//删除Q的队头元素，用e返回其值
	if (Q.front == Q.rear)
		return false;//队空
	e = Q.base[Q.front];//保存队头元素
	Q.front = (Q.front + 1) % Maxsize;//队头指针加1
	return true;
}

//取循环队列的队头元素
bool GetHead(SqQueue Q, QElemType& e)
{
	//返回Q的队头元素，不修改队头指针
	if (Q.front == Q.rear)
		return false;//队列为空，取元素失败
	e = Q.base[Q.front];
	return true;
}

//***************************循环队列的基本功能函数****************************

//1、入队
void EnQueue(SqQueue& Q)
{
	QElemType e;
	int flag;
	cout << "请输入入队元素：" << endl;
	cin >> e;
	flag = EnQueue(Q, e);
	if (flag)
		cout << "入队成功！" << endl;
	else
		cout << "入队失败！" << endl;
}

//2、出队
void DeQueue(SqQueue& Q)
{
	QElemType e;
	int flag;
	flag = DeQueue(Q, e);
	if (flag)
		cout << "出队元素为：" << e << endl;
	else
		cout << "出队失败！" << endl;
}

//3、取值
void GetHead(SqQueue Q)
{
	QElemType e;
	int flag;
	flag=GetHead(Q,e);
	if (flag)
		cout << "取得的队头元素为：" << e << endl;
	else
		cout << "取值失败！" << endl;
}

//4、求长
void QueueLength(SqQueue Q)
{
	//返回Q的元素个数，即队列的长度
	int n = (Q.rear - Q.front + Maxsize) % Maxsize;
	cout << "队列长度为：" << n << endl;
}

//5、判空
void QueueEmpty(SqQueue Q)
{
	if (Q.front == Q.rear)
		cout << "队列为空！" << endl;
	else
		cout << "队列不为空！" << endl;
}

//6、清空
void ClearQueue(SqQueue& Q)
{
	Q.rear = Q.front = 0;
}

//7、销毁
void DestoryQueue(SqQueue& Q)
{
	if (Q.base)
	{
		delete[]Q.base;
		Q.base = NULL;
		Q.rear = Q.front = 0;
	}
}

//8、打印
void PrintQueue(SqQueue Q)
{
	QElemType* p = Q.base;
	int n = (Q.rear - Q.front + Maxsize) % Maxsize;
	for (int i = 1; i <= n; i++)
		cout << "第" << i << "个元素为：" << *p++ << endl;
}

//菜单
void menu()
{
	cout << "***************************************************************************" << endl;
	cout << "***********************************1、入队*********************************" << endl;
	cout << "***********************************2、出队*********************************" << endl;
	cout << "***********************************3、取值*********************************" << endl;
	cout << "***********************************4、求长*********************************" << endl;
	cout << "***********************************5、判空*********************************" << endl;
	cout << "***********************************6、清空*********************************" << endl;
	cout << "***********************************7、销毁*********************************" << endl;
	cout << "***********************************8、打印*********************************" << endl;
	cout << "***********************************0、退出*********************************" << endl;
	cout << "***************************************************************************" << endl;
}

int main()
{
	SqQueue Q;
	int select;
	InitQueue(Q);
	while (1)
	{
		system("CLS");//清屏操作
		menu();
		cout << "请输入菜单序号：" << endl;
		cin >> select;
		switch (select)
		{
		case 1://入队
			EnQueue(Q);
			system("pause");//按任意键继续
			break;
		case 2://出队
			DeQueue(Q);
			system("pause");
			break;
		case 3://取队头元素
			GetHead(Q);
			system("pause");
			break;
		case 4://求队列长度
			QueueLength(Q);
			system("pause");
			break;
		case 5://判断队列是否为空
			QueueEmpty(Q);
			system("pause");
			break;
		case 6://清空队列
			ClearQueue(Q);
			system("pause");
			break;
		case 7://销毁队列，销毁后会自动退出
			DestoryQueue(Q);
			system("pause");
			return 0;
			break;
		case 8://从队头到队尾遍历栈并打印
			PrintQueue(Q);
			system("pause");
			break;
		case 0:
			cout << "欢迎下次使用!" << endl;//退出
			system("pause");
			return 0;
			break;
		default:
			cout << "菜单序号输入有误！" << endl;
			system("pause");
			break;
		}
	}
	system("pause");
	return 0;
}

参考资料：《数据结构》（C语言版）严蔚敏

循环队列

（一） 要求

假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq->quelen0；队满的条件：sq->quelenm。

(二)循环队列

定义：为充分利用向量空间，克服”假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表的方式来在实际编程应用中来实现, 当然也可以利用顺序表来实现。顺序表就是我们熟悉的数组 eg. sun[] 。
回顾：我们再来回顾一下关于顺序队列的重要知识点。队列通常与栈对应，栈是一种后进先出的单端（尾端）处理的数据结构；那么与之对应的队列是一种先进先出的双端（头尾两端）的数据结构。队列的特点就是在一段进行入队（存储数据）操作，在另一端进行出队（删除数据）操作。
为什么设计循环队列：大家在处理队列的时候，会遇到如下情况。例如说：我们的队列空间能够容纳1000个元素。首先，格格入队1000个元素，队列上溢，此时为“真溢出”。那么现在我们进行出队操作，我们一直出队，一直出队， 知道1000个元素全部被删除，此时我们发现队列仍然处于“上溢”状态，why？ 其实原因很简单，在非循环队列当中，无论我们的front指（偏移）到哪里，只要我们的rear指（偏移）向上阙，那么队列就是“满溢”的。这就造成了空间明明还被占据着，但是队列却已经无用武之地的窘境。对于空间有限的计算机来说，这无疑是一种浪费。也不是一个优秀的程序猿想要看到的。所以在这种情况下，循环队列诞生了。循环队列当中的“满溢”只有一种情况，那就是所有数据空降都被占领了。而不会存在非循环队列当中的“假溢出”现象。

结构一

typedef struct
{
    datatype sequ[m];
    //sequ[]为我们所建立的顺序表（sequence）
    int  front,rear;
    //front表示队列头的偏移量，rear表示队列的尾的偏移量
}qu;//qu是队列（queue）的缩写

结构二

typedef struct
{
    datatype sequ[m];
    //sequ[]为我们所建立的顺序表（sequence）
    int  rear, quelen;
    //rear表示队列的尾的偏移量，quelen表示的是队列中元素的个数
}qu;//qu是队列（queue）的缩写

（三） 循环队列的算法设计

在上面我们了解了循环队列的数据机构，但是仅仅学会了数据结构还远远不够。我们设计数据结构的目的是为了更好的存储数据，并利用数据。下面我们来看一看关于循环队列我们要掌握哪些最基本的算法（利用数据机构）。

3.1 建立循环队列

//建立队
qu* creatqueue();//函数声明
qu* creatqueue()//函数实现
{
    qu *sq;
    sq=(qu*)malloc(sizeof(qu));
    return sq;  
}

3.2 置空队列

//置空队
void setnull(qu*);//函数声明
void setnull(qu *sq)//函数实现
{
    sq->rear = m - 1;
    sq->quelen = 0;
}

3.3 入队

//入队
void enqueue(qu*, datatype);//函数声明
void enqueue(qu*sq, datatype x)//函数实现
{
    if (sq->quelen == 5)
        printf("Errot! The queue will be overflow! \n");
    else if((sq->rear+1)==m)
    {
        sq->rear = (sq->rear + 1) % m;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("过5入队成功!\n");
    }
    else
    {
        sq->rear++;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("入队成功！\n");
    }
}

3.4 出队

//出队
datatype *dequeue(qu*);//函数声明
datatype *dequeue(qu*sq)//函数实现
{
    datatype sun=0;
    if (sq->quelen == 0)
    {
        printf("Error! The queue will be under flow!\n");
        return 0;
    }
    else if ((sq->rear + 1) >= sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen];
        return(&sun);
    }
    else    //  if(sq->rear < sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen + m];
        return(&sun);
    }
}

3.5 打印队

//打印队
void print(qu*);//函数声明
void print(qu*sq)//函数定义
{
    if (sq->quelen == 0)
        printf("Error! The queue is Null!\n");
    else if ((sq->rear + 1) >= sq->quelen)
    {
        int i = sq->rear + 1 - sq->quelen;
        for (i; i <= sq->rear; i++)
            printf("%d   ", sq->sequ[i]);
    }
    else
    {
        int t = sq->rear - sq->quelen + m +1;
        int time = 1;
        for (t; time <= (sq->quelen); time++)
        {
            printf("%d   ", sq->sequ[t]);
            t++;
            if (t == m)
            {
                t = 0;
                continue;
            }
            else
            {
                continue;
            }
        }
    }
    printf("\n");
}

3.6 完整代码

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define m 5

//循环队列的结构类型定义
typedef int datatype;
typedef struct
{
    datatype sequ[m];
    int  rear, quelen;
}qu;

//函数声明
qu* creatqueue();
void setnull(qu*);
void enqueue(qu*, datatype);
datatype *dequeue(qu*);
void print(qu*);

//主函数
void main()
{
    qu *sq= creatqueue();

    datatype x, *p;
    int key;

    setnull(sq);
    do
    {
        printf("1.Enter Queue   2.Delete Queue   3.clc display   4.print queue   -1.Quit:");
        scanf_s("%d", &key);
        switch (key)
        {
        case 1:  printf("Enter the Data:"); scanf_s("%d", &x);
            enqueue(sq, x);  break;
        case 2:  p = dequeue(sq);
            if (p != NULL) printf("%d\n", *p);
            break;
        case 3:system("cls"); break;
        case 4:print(sq); break;
        case -1: exit(0);
        }
    } while (1);
}

//建立队
qu* creatqueue()
{
    qu *sq;
    sq=(qu*)malloc(sizeof(qu));
    return sq;  
}
//置空队
void setnull(qu *sq)
{
    sq->rear = m - 1;
    sq->quelen = 0;
}

//入队
void enqueue(qu*sq, datatype x)
{
    if (sq->quelen == 5)
        printf("Errot! The queue will be overflow! \n");
    else if((sq->rear+1)==m)
    {
        sq->rear = (sq->rear + 1) % m;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("过5入队成功!\n");
    }
    else
    {
        sq->rear++;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("入队成功！\n");
    }
}


//出队
datatype *dequeue(qu*sq)
{
    datatype sun=0;
    if (sq->quelen == 0)
    {
        printf("Error! The queue will be under flow!\n");
        return 0;
    }
    else if ((sq->rear + 1) >= sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen];
        return(&sun);
    }
    else    //  if(sq->rear < sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen + m];
        return(&sun);
    }
}

//打印队列
void print(qu*sq)
{
    if (sq->quelen == 0)
        printf("Error! The queue is Null!\n");
    else if ((sq->rear + 1) >= sq->quelen)
    {
        int i = sq->rear + 1 - sq->quelen;
        for (i; i <= sq->rear; i++)
            printf("%d   ", sq->sequ[i]);
    }
    else
    {
        int t = sq->rear - sq->quelen + m +1;
        int time = 1;
        for (t; time <= (sq->quelen); time++)
        {
            printf("%d   ", sq->sequ[t]);
            t++;
            if (t == m)
            {
                t = 0;
                continue;
            }
            else
            {
                continue;
            }
        }
    }
    printf("\n");
}