数据结构之顺序循环队列

队列思维导图：队列的定义：队列的特点队列的基本操作：思维导图：队列的定义：队列依旧是一种特殊的线性表。但是它只允许在一端进行插入，在另一端进行删除操作。队列的特点FIFO：first in first out队列的基本操作：初始化队列：InitQueue(&Q)销毁队列：DestoryQueue(&L)入队：EnQueue(&Q,x)出队：...

千寻瀑༄

3565人浏览 · 2020-04-22 12:25:15

千寻瀑༄ · 2020-04-22 12:25:15 发布

顺序循环队列

思维导图：
队列的定义：
队列的特点
队列的基本操作：
顺序循环队列基本操作的实现：

思维导图：

在这里插入图片描述

队列的定义：

队列依旧是一种特殊的线性表。但是它只允许在一端进行插入，在另一端进行删除操作。
在这里插入图片描述

队列的特点

FIFO：first in first out

队列的基本操作：

 初始化队列：InitQueue(&Q)
 销毁队列：DestoryQueue(&L)
 入队：EnQueue(&Q,x)
 出队：DeQueue(&Q,&x)
 读队头元素：GetHead(s,&x)
 判空栈：QueueEmpty(S)

顺序循环队列基本操作的实现：

情况一：rear和front指向同一位置时

在这里插入图片描述

队列定义：

1.用牺牲一个节点为代价判断空和满

typedef struct{
	int data[MaxSize];
	int front,rear;
}SqQueue;

2.用size标记判断空和满

typedef struct{
	int data[MaxSize];
	int front,rear;
	int size;		//size为0则空，size为MaxSize则满
}SqQueue;

3.用tag标记判断空和满

typedef struct{
	int data[MaxSize];
	int front,rear;
	int tag;		//入队为1，出队为0
}SqQueue;

队列初始化：

1.用牺牲一个节点为代价判断空和满

void InitQueue(SqQueue &Q){
	Q.rear = Q.front = 0;
}

2.用size标记判断空和满

void InitQueue(SqQueue &Q){
	Q.rear = Q.front = 0;
	size = 0;
}

3.用tag标记判断空和满

void InitQueue(SqQueue &Q){
	Q.rear = Q.front = 0;
	tag = 0;
}

入队：

1.用牺牲一个节点为代价判断空和满
在这里插入图片描述 ps: 计算队列元素个数：
　　(rear+MaxSize-front) % MaxSize
eg:(2+10-3) % 10 = 9(上图)

bool EnQueue(SqQueue &Q,int x){
	if((Q.rear+1) % MaxSize == Q.front)
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	return true; 
}

2.用size标记判断空和满
在这里插入图片描述

bool EnQueue(SqQueue &Q,int x){
	if(Q.size == MaxSize)
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	size ++;
	return true; 
}

3.用tag标记判断空和满
在这里插入图片描述

bool EnQueue(SqQueue &Q,int x){
	if(Q.front == Q.rear && tag == 1)
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	tag = 1;
	return true; 
}

出队：

1.用牺牲一个节点为代价判断空和满
在这里插入图片描述

bool DeQueue(SqQueue &Q,int &x){
	if(Q.rear == Q.front)
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) & MaxSize;
	return true;
}

2.用size标记判断空和满
在这里插入图片描述

bool DeQueue(SqQueue &Q,int &x){
	if(Q.size == 0)
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	size --;
	return true;
}

3.用tag标记判断空和满
在这里插入图片描述

//每次删除操作成功时都令tag=0，只有删除操作才可能导致队空
//每次插入操作成功时都令tag=1，只有插入操作才可能导致队满
bool EnQueue(SqQueue &Q,int x){
	if(Q.front == Q.rear && tag == 0)
		return false;
	x = Q.data[Q.rear];
	Q.front= (Q.front+ 1) % MaxSize;
	tag = 0;
	return true; 
}

队列判空：

1.用牺牲一个节点为代价判断空和满

bool QueueEmpty(SqQueue Q){
	if(Q.rear == Q.front)
		return true;
	else
		return false;
}

2.用size标记判断空和满

bool QueueEmpty(SqQueue Q){
	if(Q.size == MaxSize)
		return true;
	else
		return false;
}

3.用tag标记判断空和满

bool QueueEmpty(SqQueue Q){
	if(Q.front == Q.rear && tag == 1)
		return true;
	else
		return false;
}

返回队头元素：

1.用牺牲一个节点为代价判断空和满

bool GetHead(SqQueue &Q,int &x){
	if(Q.rear == Q.front)
		return false;
	x = Q.data[Q.front];
	return true;
}

2.用size标记判断空和满

bool GetHead(SqQueue &Q,int &x){
	if(Q.size == 0)
		return false;
	x = Q.data[Q.front];
	return true;
}

3.用tag标记判断空和满

bool GetHead(SqQueue &Q,int &x){
	if(Q.front == Q.rear && tag == 0)
		return false;
	x = Q.data[Q.front];
	return true;
}

情况二：rear在front后面

在这里插入图片描述

队列定义：

1.用牺牲一个节点为代价判断空和满

typedef struct{
	int data[MaxSize];
	int front,rear;
}SqQueue;

2.用size标记判断空和满

typedef struct{
	int data[MaxSize];
	int front,rear;
	int size;
}SqQueue;

3.用tag标记判断空和满

typedef struct{
	int data[MaxSize];
	int front,rear;
	int tag;
}SqQueue;

队列初始化：

1.用牺牲一个节点为代价判断空和满

void InitQueue(SqQueue &Q){
	Q.front = 0;
	Q.rear = (Q.front - 1) % MaxSize;
}

2.用size标记判断空和满

void InitQueue(SqQueue &Q){
	Q.front = 0;
	Q.rear = (Q.front - 1) % MaxSize;
	int size;
}

3.用tag标记判断空和满

void InitQueue(SqQueue &Q){
	Q.front = 0;
	Q.rear = (Q.front - 1) % MaxSize;
	int tag;
}

入队：

1.用牺牲一个节点为代价判断空和满
在这里插入图片描述

bool EnQueue(SqQueue &Q,int x){
	if((Q.rear+2) % MaxSize == Q.front)
		return false;
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.data[Q.rear] = x;
	return true; 
}

2.用size标记判断空和满

bool EnQueue(SqQueue &Q,int x){
	if(Q.size == MaxSize)
		return false;
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.data[Q.rear] = x;
	size ++;
	return true; 
}

3.用tag标记判断空和满

bool EnQueue(SqQueue &Q,int x){
	if((Q.rear+1) % MaxSize == Q.front && tag == 1)
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	tag = 1;
	return true; 
}

出队：

1.用牺牲一个节点为代价判断空和满
在这里插入图片描述

bool DeQueue(SqQueue &Q,int &x){
	if((Q.rear+1) % MaxSize == Q.front)
		return false;
	Q.front = (Q.front + 1) & MaxSize;
	x = Q.data[Q.front];
	return true;
}

2.用size标记判断空和满

bool DeQueue(SqQueue &Q,int &x){
	if(Q.size == 0)
		return false;
	Q.front = (Q.front + 1) % MaxSize;
	x = Q.data[Q.front];
	size --;
	return true;
}

3.用tag标记判断空和满

//每次删除操作成功时都令tag=0，只有删除操作才可能导致队空
//每次插入操作成功时都令tag=1，只有插入操作才可能导致队满
bool EnQueue(SqQueue &Q,int x){
	if((Q.rear+1) % MaxSize == Q.front && tag == 0)
		return false;
	Q.front= (Q.front+ 1) % MaxSize;
	x = Q.data[Q.rear];
	tag = 0;
	return true; 
}

队列判空：

1.用牺牲一个节点为代价判断空和满

bool QueueEmpty(SqQueue Q){
	if((Q.rear+1) % MaxSize == Q.front)
		return true;
	else
		return false;
}

2.用size标记判断空和满

bool QueueEmpty(SqQueue Q){
	if(Q.size == MaxSize)
		return true;
	else
		return false;
}

3.用tag标记判断空和满

bool QueueEmpty(SqQueue Q){
	if((Q.rear+1) % MaxSize == Q.front && tag == 0 )
		return true;
	else
		return false;
}

返回队头元素：

1.用牺牲一个节点为代价判断空和满

bool GetHead(SqQueue &Q,int &x){
	if((Q.rear+1) % MaxSize == Q.front)
		return false;
	x = Q.data[Q.front];
	return true;
}

2.用size标记判断空和满

bool GetHead(SqQueue &Q,int &x){
	if(Q.size == 0)
		return false;
	x = Q.data[Q.front];
	return true;
}

3.用tag标记判断空和满

bool GetHead(SqQueue &Q,int &x){
	if((Q.rear+1) % MaxSize == Q.front && tag == 0)
		return false;
	x = Q.data[Q.front];
	return true;
}

DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

KingbaseES数据库：医疗信创潮涌沅江，国产化信创打造医疗新质生产力

DAMO开发者矩阵

告别迁移焦虑：金仓KDMS V4带你轻松搞定数据库国产化替代

DAMO开发者矩阵

KingbaseES数据库在常德二院全栈国产化信创中产生新质生产力,医疗信创的部署如何实现，如何操作？

DAMO开发者矩阵

所有评论(0)

查看更多评论

千寻瀑༄

@qq_41587740

已为社区贡献5条内容