循环队列的基本操作C/C++代码实现

妖狐艹你老母 2023-02-14 15:50 7阅读 0赞

## 循环队列的结构： ##

在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置，阴影部分表示队列：  
![在这里插入图片描述][20200603174155833.png]  
另外通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式 ”循环＂ 移动。（为了防止假溢出）

注意：循环队列为了方便判断队空和队满，一般少用一个元素空间， 即最后一个元素不用，队列空间大小为m时，有m-1个元素就认为是队满。详情见入队和出队。

## 求队列长度： ##

队列长度为：(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE

## 入队： ##

队满的条件： (Q rear+ 1)%MAXQSIZE= Q.front

## 出队： ##

队空的条件： Q.front == Q.rear

## 循环队列特点： ##

与顺序栈相似，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度！若用户无法预估所用队列的最大长度， 则宜采用链队列。

## 代码如下： ##

#include<stdio.h>
    #include<stdlib.h>
    
    #define MAXQSIZE 100
    typedef int QElemType;
    
    //循环队列的结构
    typedef struct
    {
        
    	QElemType *base;	//基地址
    	int front;			//头指针
    	int rear;			//尾指针
    }SqQueue;
    
    //初始化
    void InitQueue(SqQueue &Q)
    {
        
    	Q.base = new QElemType[MAXQSIZE];
    	if (!Q.base) exit;		//分配失败退出
    
    	Q.front = Q.rear = 0;	//初始化尾指针与头指针为0
    }
    
    //求队列长度
    int QueueLength(SqQueue Q)
    {
        
    	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
    }
    
    //入队
    int EnQueue(SqQueue &Q,QElemType e)
    {
        
    	if ((Q.rear + 1) % MAXQSIZE == Q.front) return 0; //队满
    
    	Q.base[Q.rear] = e;
    	Q.rear=(Q.rear+1)%MAXQSIZE;  //循环队列，防止假溢出
    	return 1;
    }
    
    //出队
    int DeQueue(SqQueue &Q, QElemType &e)
    {
        
    	if (Q.rear == Q.front) return 0;   //队空
    
    	e = Q.base[Q.front];
    	Q.front = (Q.front + 1) % MAXQSIZE;  //循环队列，防止假溢出
    	return 1;
    }
    
    //取队头元素
    QElemType GetHead(SqQueue Q)
    {
        
    	if (Q.front != Q.rear)			//非空时 取值
    		return Q.base[Q.front];
    }
    
    //遍历输出队列
    void printQueue(SqQueue Q)
    {
        
    	printf("队头：");
    	QElemType p =Q.front;
    	while (p!= Q.rear)
    	{
        
    		printf("%d ", Q.base[p]);
    		p = (p + 1) % MAXQSIZE;
    	}
    	printf("\n");
    }
    
    
    int main()
    {
        
    	SqQueue Q;
    	int e;
    	InitQueue(Q);
    	printf("请输入一个要入队的元素（-1表示结束）：");
    	scanf("%d", &e);
    	while (e != -1)
    	{
        
    		EnQueue(Q, e);
    		printf("请输入一个要入队的元素（-1表示结束）：");
    		scanf("%d", &e);
    	}
    	printQueue(Q);
    	printf("当前队列长度为%d\n\n", QueueLength(Q));
    	printf("出队测试：");
    	DeQueue(Q, e);
    	printQueue(Q);
    	printf("当前队列长度为%d\n\n", QueueLength(Q));
    
    	printf("取队头元素测试：");
    	e = GetHead(Q);
    	printf("取出的队头元素为：%d\n", e);
    	printf("当前队列长度为%d\n", QueueLength(Q));
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

[20200603174155833.png]: https://img-blog.csdnimg.cn/20200603174155833.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200603182717387.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70