循环队列

常见的定义方法：

①rear 指向队尾元素后一个位置 ②rear 指向队尾元素
a.牺牲一个存储单元 b.增加size变量记录队列长度 c.增加tag标记操作

1 2的区别主要在于初始化和出入队时指针指向不同
abc的区别主要在于判断为空或已满的方式不同

以下是6种定义和基本函数实现的代码，主要理解它们之间的区别

循环队列①a

//1a rear指向队尾元素后一个位置 牺牲一个存储单元
#include<bits/stdc++.h>
using namespace std;

typedef int ElemType; 		//栈元素数据类型

#define MaxSize 50  		//栈中元素最大个数
typedef struct{
	ElemType data[MaxSize]; //存放栈中元素
	int front,rear;         //队头指针和队尾指针
}SqQueue;

void InitQueue(SqQueue &Q);//初始化
bool QueueEmpty(SqQueue Q);//判空
bool EnQueue(SqQueue &Q,ElemType x);//入队
bool DeQueue(SqQueue &Q,ElemType &x);//出队
bool GetHead(SqQueue Q,ElemType &x);//读队头元素
//需要注意的是，栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

void test(){
	SqQueue Q;
	ElemType x;
	InitQueue(Q);
	
	EnQueue(Q,1); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,3); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,5); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,7); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,9); GetHead(Q,x); printf("队头元素为%d\n",x);
	
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
}

int main(){
	test();
	return 0;
}

//初始化队列,构造一个空队列Q。
void InitQueue(SqQueue &Q){
	Q.front=Q.rear=0;   //初始化队首、队尾指针
}
//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(SqQueue Q){
    return Q.front==Q.rear;
}
///入队,若队列Q未满，将x加入，使之成为新的队尾。
bool EnQueue(SqQueue &Q,ElemType x){
	if ((Q.rear+1)%MaxSize==Q.front) return false;  //队列Q已满
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear+1)%MaxSize;
}
//出队，若队列Q非空，删除队头元素，并用x返回。
bool DeQueue(SqQueue &Q,ElemType &x){
	if (Q.front==Q.rear) return false; //队列Q为空
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
}
//读队头元素，若队列○非空，则将队头元素赋值给x。
bool GetHead(SqQueue Q,ElemType &x){
	x=Q.data[Q.front];
    return Q.front==Q.rear;
}

循环队列①b

//1b rear指向队尾元素后一个位置 增加size变量记录队列长度
#include<bits/stdc++.h>
using namespace std;

typedef int ElemType; 		//栈元素数据类型

#define MaxSize 50  		//栈中元素最大个数
typedef struct{
	ElemType data[MaxSize]; //存放栈中元素
	int front,rear,size;         //队头指针 队尾指针 队列长度
}SqQueue;

void InitQueue(SqQueue &Q);//初始化
bool QueueEmpty(SqQueue Q);//判空
bool EnQueue(SqQueue &Q,ElemType x);//入队
bool DeQueue(SqQueue &Q,ElemType &x);//出队
bool GetHead(SqQueue Q,ElemType &x);//读队头元素
//需要注意的是，栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

void test(){
	SqQueue Q;
	ElemType x;
	InitQueue(Q);

	EnQueue(Q,1); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,3); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,5); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,7); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,9); GetHead(Q,x); printf("队头元素为%d\n",x);

	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
}

int main(){
	test();
	return 0;
}

//初始化队列,构造一个空队列Q。
void InitQueue(SqQueue &Q){
	Q.front=Q.rear=0;   //初始化队首、队尾指针
	Q.size=0;
}
//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(SqQueue Q){
    return Q.size==0;
}
///入队,若队列Q未满，将x加入，使之成为新的队尾。
bool EnQueue(SqQueue &Q,ElemType x){
	if (Q.size==MaxSize) return false;  //队列Q已满
	Q.data[Q.rear]=x;
	Q.size++;
	Q.rear=(Q.rear+1)%MaxSize;
}
//出队，若队列Q非空，删除队头元素，并用x返回。
bool DeQueue(SqQueue &Q,ElemType &x){
	if (Q.size==0) return false; //队列Q为空
	x=Q.data[Q.front];
	Q.size--;
	Q.front=(Q.front+1)%MaxSize;
}
//读队头元素，若队列○非空，则将队头元素赋值给x。
bool GetHead(SqQueue Q,ElemType &x){
	x=Q.data[Q.front];
    return Q.front==Q.rear;
}

循环队列①c

//1c rear指向队尾元素后一个位置 增加tag标记操作
#include<bits/stdc++.h>
using namespace std;

typedef int ElemType; 		//栈元素数据类型

#define MaxSize 50  		//栈中元素最大个数
typedef struct{
	ElemType data[MaxSize]; //存放栈中元素
	int front,rear,tag;         //队头指针 队尾指针 操作标记
}SqQueue;

void InitQueue(SqQueue &Q);//初始化
bool QueueEmpty(SqQueue Q);//判空
bool EnQueue(SqQueue &Q,ElemType x);//入队
bool DeQueue(SqQueue &Q,ElemType &x);//出队
bool GetHead(SqQueue Q,ElemType &x);//读队头元素
//需要注意的是，栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

void test(){
	SqQueue Q;
	ElemType x;
	InitQueue(Q);

	EnQueue(Q,1); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,3); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,5); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,7); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,9); GetHead(Q,x); printf("队头元素为%d\n",x);

	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
}

int main(){
	test();
	return 0;
}

//初始化队列,构造一个空队列Q。
void InitQueue(SqQueue &Q){
	Q.front=Q.rear=0;   //初始化队首、队尾指针
	Q.tag=0;
}
//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(SqQueue Q){
    return (Q.front==Q.rear && Q.tag=0);
}
//入队,若队列Q未满，将x加入，使之成为新的队尾。
bool EnQueue(SqQueue &Q,ElemType x){
	if ( Q.front==Q.rear && Q.tag==1 ) return false;  //队列Q已满
	Q.data[Q.rear]=x;
	Q.tag=1;    //1表示入队
	Q.rear=(Q.rear+1)%MaxSize;
}
//出队，若队列Q非空，删除队头元素，并用x返回。
bool DeQueue(SqQueue &Q,ElemType &x){
	if ( Q.front==Q.rear && Q.tag==0 ) return false; //队列Q为空
	x=Q.data[Q.front];
	Q.tag=0;    //0表示出队
	Q.front=(Q.front+1)%MaxSize;
}
//读队头元素，若队列○非空，则将队头元素赋值给x。
bool GetHead(SqQueue Q,ElemType &x){
	x=Q.data[Q.front];
    return Q.front==Q.rear;
}

循环队列②a

//1c rear指向队尾元素后一个位置 增加tag标记操作
#include<bits/stdc++.h>
using namespace std;

typedef int ElemType; 		//栈元素数据类型

#define MaxSize 50  		//栈中元素最大个数
typedef struct{
	ElemType data[MaxSize]; //存放栈中元素
	int front,rear,tag;         //队头指针 队尾指针 操作标记
}SqQueue;

void InitQueue(SqQueue &Q);//初始化
bool QueueEmpty(SqQueue Q);//判空
bool EnQueue(SqQueue &Q,ElemType x);//入队
bool DeQueue(SqQueue &Q,ElemType &x);//出队
bool GetHead(SqQueue Q,ElemType &x);//读队头元素
//需要注意的是，栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

void test(){
	SqQueue Q;
	ElemType x;
	InitQueue(Q);

	EnQueue(Q,1); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,3); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,5); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,7); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,9); GetHead(Q,x); printf("队头元素为%d\n",x);

	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
}

int main(){
	test();
	return 0;
}

//初始化队列,构造一个空队列Q。
void InitQueue(SqQueue &Q){
	Q.front=Q.rear=0;   //初始化队首、队尾指针
	Q.tag=0;
}
//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(SqQueue Q){
    return (Q.front==Q.rear && Q.tag=0);
}
//入队,若队列Q未满，将x加入，使之成为新的队尾。
bool EnQueue(SqQueue &Q,ElemType x){
	if ( Q.front==Q.rear && Q.tag==1 ) return false;  //队列Q已满
	Q.data[Q.rear]=x;
	Q.tag=1;    //1表示入队
	Q.rear=(Q.rear+1)%MaxSize;
}
//出队，若队列Q非空，删除队头元素，并用x返回。
bool DeQueue(SqQueue &Q,ElemType &x){
	if ( Q.front==Q.rear && Q.tag==0 ) return false; //队列Q为空
	x=Q.data[Q.front];
	Q.tag=0;    //0表示出队
	Q.front=(Q.front+1)%MaxSize;
}
//读队头元素，若队列○非空，则将队头元素赋值给x。
bool GetHead(SqQueue Q,ElemType &x){
	x=Q.data[Q.front];
    return Q.front==Q.rear;
}

循环队列②b

//2b rear指向队尾元素 增加size变量记录队列长度
#include<bits/stdc++.h>
using namespace std;

typedef int ElemType; 		//栈元素数据类型

#define MaxSize 50  		//栈中元素最大个数
typedef struct{
	ElemType data[MaxSize]; //存放栈中元素
	int front,rear,size;         //队头指针 队尾指针 队列长度
}SqQueue;

void InitQueue(SqQueue &Q);//初始化
bool QueueEmpty(SqQueue Q);//判空
bool EnQueue(SqQueue &Q,ElemType x);//入队
bool DeQueue(SqQueue &Q,ElemType &x);//出队
bool GetHead(SqQueue Q,ElemType &x);//读队头元素
//需要注意的是，栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

void test(){
	SqQueue Q;
	ElemType x;
	InitQueue(Q);

	EnQueue(Q,1); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,3); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,5); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,7); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,9); GetHead(Q,x); printf("队头元素为%d\n",x);

	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
}

int main(){
	test();
	return 0;
}

//初始化队列,构造一个空队列Q。
void InitQueue(SqQueue &Q){
	Q.front=0;
	Q.rear=MaxSize-1;   //初始化队首、队尾指针
	Q.size=0;
}
//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(SqQueue Q){
    return Q.size==0;
}
///入队,若队列Q未满，将x加入，使之成为新的队尾。
bool EnQueue(SqQueue &Q,ElemType x){
	if (Q.size==MaxSize) return false;  //队列Q已满
	Q.rear=(Q.rear+1)%MaxSize;
	Q.data[Q.rear]=x;
}
//出队，若队列Q非空，删除队头元素，并用x返回。
bool DeQueue(SqQueue &Q,ElemType &x){
	if (Q.size==0) return false; //队列Q为空
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
}
//读队头元素，若队列○非空，则将队头元素赋值给x。
bool GetHead(SqQueue Q,ElemType &x){
	x=Q.data[Q.front];
    return Q.front==Q.rear;
}

循环队列②c

//2c rear指向队尾元素 增加tag标记操作
#include<bits/stdc++.h>
using namespace std;

typedef int ElemType; 		//栈元素数据类型

#define MaxSize 50  		//栈中元素最大个数
typedef struct{
	ElemType data[MaxSize]; //存放栈中元素
	int front,rear,tag;         //队头指针 队尾指针 操作标记
}SqQueue;

void InitQueue(SqQueue &Q);//初始化
bool QueueEmpty(SqQueue Q);//判空
bool EnQueue(SqQueue &Q,ElemType x);//入队
bool DeQueue(SqQueue &Q,ElemType &x);//出队
bool GetHead(SqQueue Q,ElemType &x);//读队头元素
//需要注意的是，栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

void test(){
	SqQueue Q;
	ElemType x;
	InitQueue(Q);

	EnQueue(Q,1); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,3); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,5); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,7); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,9); GetHead(Q,x); printf("队头元素为%d\n",x);

	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
}

int main(){
	test();
	return 0;
}

//初始化队列,构造一个空队列Q。
void InitQueue(SqQueue &Q){
	Q.front=0;
	Q.rear=MaxSize-1;   //初始化队首、队尾指针
	Q.tag=0;
}
//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(SqQueue Q){
    return ((Q.rear+1)%MaxSize==Q.front && Q.tag==0);
}
///入队,若队列Q未满，将x加入，使之成为新的队尾。
bool EnQueue(SqQueue &Q,ElemType x){
	if ((Q.rear+1)%MaxSize==Q.front && Q.tag==1) return false;  //队列Q已满
	Q.rear=(Q.rear+1)%MaxSize;
	Q.data[Q.rear]=x;
}
//出队，若队列Q非空，删除队头元素，并用x返回。
bool DeQueue(SqQueue &Q,ElemType &x){
	if ((Q.rear+1)%MaxSize==Q.front && Q.tag==0) return false; //队列Q为空
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
}
//读队头元素，若队列○非空，则将队头元素赋值给x。
bool GetHead(SqQueue Q,ElemType &x){
	x=Q.data[Q.front];
    return Q.front==Q.rear;
}

链式队列 带头节点

#include<bits/stdc++.h>
using namespace std;

typedef int ElemType; //线性表元素数据类型

typedef struct LNode{   //定义队列结点类型
	ElemType data;      //每个节点存放一个数据元素
	struct LNode *next; //指针指向下一元素
}LNode;      

typedef struct{
	LNode *front,*rear;	//头指针和尾指针
}LinkQueue;

void InitQueue(LinkQueue &Q);//初始化
bool QueueEmpty(LinkQueue Q);//判空
void EnQueue(LinkQueue &Q,ElemType x);//入队
bool DeQueue(LinkQueue &Q,ElemType &x);//出队
bool GetHead(LinkQueue Q,ElemType &x);//读队头元素

void test(){
	LinkQueue Q;
	ElemType x;
	InitQueue(Q);

	EnQueue(Q,1); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,3); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,5); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,7); GetHead(Q,x); printf("队头元素为%d\n",x);
	EnQueue(Q,9); GetHead(Q,x); printf("队头元素为%d\n",x);

	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
	DeQueue(Q,x);
	printf("出队元素为%d ",x);GetHead(Q,x);printf("队头元素为%d\n",x);
}

int main(){
	test();
	return 0;
}

//初始化队列,构造一个空队列Q。
void InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(LNode *) malloc(sizeof(LNode));   //初始化队首、队尾指针
	Q.front->next=NULL;
}
//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(LinkQueue Q){
    return Q.front==Q.rear;
}
///入队 将x加入，使之成为新的队尾。
void EnQueue(LinkQueue &Q,ElemType x){
	LNode *s=(LNode *) malloc(sizeof(LNode));
	s->data=x;s->next=NULL;
	Q.rear->next=s;
	Q.rear=s;
}
//出队，若队列Q非空，删除队头元素，并用x返回。
bool DeQueue(LinkQueue &Q,ElemType &x){
	if (Q.front==Q.rear) return false; //队列Q为空
	LNode *q=Q.front->next;
	x=q->data;
	Q.front->next=q->next;
	if(Q.rear==q) Q.rear=Q.front;
	free(q);
}
//读队头元素，若队列○非空，则将队头元素赋值给x。
bool GetHead(LinkQueue Q,ElemType &x){
	if (Q.front==Q.rear) return false;
	x=Q.front->next->data;
}

双端队列

即两段都能进行入队和出队操作的队列，还有入队受限和出队受限的双端队列，指的是有一端不能入队或出队的双端队列，主要考查输入输出的序列

队列的应用

树的遍历、图的广度优先遍历、 操作系统（先来先服务（FCFS）、打印数据缓冲区）

精选试题

队列练习题

笔记

栈详解

# 数据结构 # c语言 # c++ # 排序算法 # 算法
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

大数据毕业设计选题推荐-基于大数据的农作物产量数据分析与可视化系统-Hadoop-Spark-数据可视化-BigData

avatar 魔乐社区
cover

大模型推理适配实战：手把手带你完成vLLM Ascend迁移实操

avatar 魔乐社区
cover

基于python大数据的汽车数据分析系统设计与实现

avatar 魔乐社区