【数据结构】-循环队列3(顺序存储)

ゝ一纸荒年。 2023-02-28 12:58 12阅读 0赞

### 顺序存储-循环队列3 ###

*  1.头文件及类型定义
 *  2.循环队列类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 初始化队列
     *  4.2 判空
     *  4.3 入队
     *  4.4 出队
     *  4.5 获取队头元素
     *  4.6 main函数
 *  5.小结

# 1.头文件及类型定义 #

#include<stdio.h>
    #define MaxSize 10			//定义队列中元素的最大个数
    #define ElemType int

# 2.循环队列类型定义 #

typedef struct {
        				//顺序队列类型定义
    	ElemType data[MaxSize];		//静态数组存放队列元素
    	int front, rear;			//队头指针和队尾指针
    	int tag;					//引入辅助变量tag表示最后一次操作是入队还是出队，为判空判满提供方便且节省一个队列单元
    }SqQueue;

# 3.函数声明 #

/*函数声明*/
    void InitQueue(SqQueue& Q);					//1.初始化队列
    bool QueueEmpty(SqQueue Q);					//2.判空
    bool EnQueue(SqQueue& Q, ElemType x);		//3.入队
    bool ExQueue(SqQueue& Q, ElemType& x);		//4.出队
    bool GetHead(SqQueue Q, ElemType& x);		//5.获取队头元素

# 4.基本操作 #

## 4.1 初始化队列 ##

//1.初始化队列
    void InitQueue(SqQueue& Q) {
        
    	Q.front = 0;	//队头指针指向队头元素	
    	Q.rear = MaxSize-1;		//初始化时队尾指针指向队头指针的前一个元素，这样在之后的操作中队尾指针始终指向队尾元素
    	Q.tag = 0;		//初始化最后一次操作为删除，因为当前队空
    }

## 4.2 判空 ##

//2.判空
    bool QueueEmpty(SqQueue Q) {
        
    	return ((Q.rear + 1) % MaxSize == Q.front && Q.tag == 0);		//队尾+1=队头且最后一次进行是出队操作则队空
    }

## 4.3 入队 ##

//3.入队操作：在队尾进行插入操作
    bool EnQueue(SqQueue& Q, ElemType x) {
        
    	if ((Q.rear + 1) % MaxSize == Q.front && Q.tag == 1)		//队尾+1=队头且最后一次进行是入队操作则队满
    		return false;
    	Q.rear = (Q.rear + 1) % MaxSize;		//队尾指针加1取模，用模运算j将存储空间在逻辑上变成了“环状”，这也是叫循环队列的原因
    	Q.data[Q.rear] = x;					//新元素插入队尾
    	Q.tag = 1;		//标识此次进行的是入队操作
    	return true;
    }

## 4.4 出队 ##

//4.出队操作：在队头进行删除操作
    bool ExQueue(SqQueue& Q, ElemType& x) {
        
    	if ((Q.rear + 1) % MaxSize == Q.front && Q.tag == 0)		//队空，报错
    		return false;
    	x = Q.data[Q.front];		//返回出队元素的值
    	Q.front = (Q.front + 1) % MaxSize;		//队头指针+1取模，指向下一个元素
    	Q.tag = 0;		//标识此次进行的是出队操作
    	return true;
    }

## 4.5 获取队头元素 ##

//5.获得队头元素的值，用x返回
    bool GetHead(SqQueue Q, ElemType& x) {
        
    	if ((Q.rear + 1) % MaxSize == Q.front && Q.tag == 0)	//队空，报错	
    		return false;
    	x = Q.data[Q.front];	//获取队头元素
    	return true;
    }

## 4.6 main函数 ##

int main() {
        
    	SqQueue Q;		//声明一个循环队列(分配内存空间)
    
    	/*1、初始化队列*/
    	InitQueue(Q);
    
    	/*2、判空*/
    	if (QueueEmpty(Q))
    		printf("当前队列为空！\n");
    	else
    		printf("当前队列非空！\n");
    
    	/*3、入队操作*/
    	ElemType e1;
    	printf("请输入入队元素的值：");
    	scanf("%d", &e1);
    	if (EnQueue(Q, e1))
    		printf("新元素入队成功！\n");
    	else
    		printf("队列已满,新元素入队失败！\n");
    
    	/*本段代码仅用作测试-循环入队直至队满
    		ElemType e1;
    		printf("初始rear为：%d\n", Q.rear);
    		int n=1;
    		while (!((Q.rear + 1) % MaxSize == Q.front && Q.tag == 1)) {	//队不满则一直入队
    			printf("请输入第%d个元素的值：",n);
    			scanf("%d", &e1);
    			EnQueue(Q, e1);
    			printf("当前rear为：%d\n", Q.rear);		//查看入队后的rear变化
    			n++;
    		}
    	*/
    	
    	/*4、读取队头元素*/
    	ElemType e2 = -1;
    	if (GetHead(Q, e2))
    		printf("读取队头元素成功，当前队头元素值为：%d\n", e2);
    	else
    		printf("队列已空，读取队头元素失败！\n");
    
    	/*5、出队操作*/
    	ElemType e3 = -1;
    	if (ExQueue(Q, e3))
    		printf("队头元素出队成功，出队元素值为：%d\n", e3);
    	else
    		printf("队列已空，队头元素出队失败！\n");
    
    	/*本段代码仅用作测试-循环出队直至队空
    		ElemType e3 = -1;
    		printf("当前front为：%d\n", Q.front);
    		while (ExQueue(Q, e3)) {		
    			printf("当前出队元素的值为：%d\n", e3);
    			printf("当前front为：%d\n", Q.front);
    		}
    	*/
    
    	/*6、读取队头元素*/
    	ElemType e4 = -1;
    	if (GetHead(Q, e4))
    		printf("读取队头元素成功，当前队头元素值为：%d\n", e4);
    	else
    		printf("队列已空，读取队头元素失败！\n");
    
    	return 0;
    }

# 5.小结 #

本文承接上两篇循环队列，与上篇两均不同，本文将队尾指针初始化为MaxSize-1并且引入了辅助变量tag来方便判断队空和队满。  
为了对比，总结如下：  
![循环队列][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center]  
在上图中带小红旗的是已实现的三种方式，其余三种核心思想没有大的变化，后续文章不再阐述。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/21f80645b8444112a9287658f7b4cc67.png