队列之循环队列详解（C语言版）

2024-01-19 03:58| 来源: 网络整理| 查看: 265

文章目录前言一、循环队列的定义二、循环队列的结构三、循环队列的常用操作结语附录

前言

大家好，越努力，越幸运。本篇文章小猿将跟您分享数据结构队列中的循环队列，希望对您有所帮助。

在这里插入图片描述

一、循环队列的定义

顺序队列在使用过程中容易出现虚假的满状态，为了解决这个问题，就产生了一个较巧妙的方法，将顺序队列臆造为一个环状的空间，称之为循环队列。循环队列中指针和队列元素之间的关系不变，我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题，在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”，可有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。此处使用方法二来解决这个问题。

二、循环队列的结构

结构图在这里插入图片描述

代码描述

//数据类型 #define ElemType int //队列的最大空间 #define MAXSIZE 8 //队列的管理结构 typedef struct Queue { ElemType *base; //指向队列空间的基址 int front; //头指针 int rear; //尾指针 }Queue; 三、循环队列的常用操作

初始化

//队列初始化 void InitQueue(Queue *Q) { //为队列分配存储空间 Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE); assert(Q->base != NULL); //初始时队列为空，头指针和尾指针都指向0位置 Q->front = Q->rear = 0; }

入队

//入队操作 void EnQueue(Queue *Q, ElemType x) { //判断循环队列是否已满 if(((Q->rear+1)%MAXSIZE) == Q->front) return; //队列未满，将数据入队 Q->base[Q->rear] = x; //更改尾指针的指向 Q->rear = (Q->rear+1)%MAXSIZE; }

出队

//出队操作 void DeQueue(Queue *Q) { //判断循环队列是否为空 if(Q->front == Q->rear) return; //如果非空，实现可循环出队 Q->front = (Q->front+1)%MAXSIZE; }

打印队列数据

//打印循环队列中的数据 void ShowQueue(Queue *Q) { //遍历循环队列中的元素，并将数据打印 for(int i=Q->front; i!=Q->rear;) { printf("%d ",Q->base[i]); //此操作是为了实现循环遍历 i = (i+1)%MAXSIZE; } printf("\n"); }

获取队头元素

//获取队头元素 void GetHdad(Queue *Q, ElemType *v) { //判断循环队列是否为空 if(Q->front == Q->rear) return; //如果队列不为空，获取队头元素 *v = Q->base[Q->front]; }

求队列长度

//获取队列长度（元素个数） int Length(Queue *Q) { //计算尾指针位置与头指针位置的差距 int len= Q->rear - Q->front; //如果为正数，那么len就是队列的长度；如果为负数，那么MAXSIZE+len才是队列的长度 len = (len>0) ? len : MAXSIZE+len; return len; }

清空队列

//清空队列 void ClearQueue(Queue *Q) { //将队头指针和队尾指针都置为0 Q->front = Q->rear = 0; }

销毁队列

//销毁队列 void DestroyQueue(Queue *Q) { //释放队列的存储空间 free(Q->base); //将队列基址置空 Q->base = NULL; } 结语

对循环队列的介绍就到这里啦，希望这篇文章能给予你一些帮助，感谢各位人才的：点赞、收藏和评论，我们下次见。在这里插入图片描述

附录

以下提供循环队列的测试代码

SeqQueue.h

#ifndef __SEQQUEUE_H__ #define __SEQQUEUE_H__ #include #include #include //数据类型 #define ElemType int //队列的最大空间 #define MAXSIZE 8 //队列的管理结构 typedef struct Queue { ElemType *base; //指向队列空间的基址 int front; //头指针 int rear; //尾指针 }Queue; void InitQueue(Queue *Q); void EnQueue(Queue *Q, ElemType x); void ShowQueue(Queue *Q); void DeQueue(Queue *Q); void GetHdad(Queue *Q, ElemType *v); int Length(Queue *Q); void ClearQueue(Queue *Q); void DestroyQueue(Queue *Q); #endif //__SEQQUEUE_H__

SeqQueue.cpp

#include"SeqQueue.h" //队列初始化 void InitQueue(Queue *Q) { //为队列分配存储空间 Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE); assert(Q->base != NULL); //初始时队列为空，头指针和尾指针都指向0位置 Q->front = Q->rear = 0; } //入队操作 void EnQueue(Queue *Q, ElemType x) { //判断循环队列是否已满 if(((Q->rear+1)%MAXSIZE) == Q->front) return; //队列未满，将数据入队 Q->base[Q->rear] = x; //更改尾指针的指向 Q->rear = (Q->rear+1)%MAXSIZE; } //打印循环队列中的数据 void ShowQueue(Queue *Q) { //遍历循环队列中的元素，并将数据打印 for(int i=Q->front; i!=Q->rear;) { printf("%d ",Q->base[i]); //此操作是为了实现循环遍历 i = (i+1)%MAXSIZE; } printf("\n"); } //出队操作 void DeQueue(Queue *Q) { //判断循环队列是否为空 if(Q->front == Q->rear) return; //如果非空，实现可循环出队 Q->front = (Q->front+1)%MAXSIZE; } //获取队头元素 void GetHdad(Queue *Q, ElemType *v) { //判断循环队列是否为空 if(Q->front == Q->rear) return; //如果队列不为空，获取队头元素 *v = Q->base[Q->front]; } //获取队列长度（元素个数） int Length(Queue *Q) { //计算尾指针位置与头指针位置的差距 int len= Q->rear - Q->front; //如果为正数，那么len就是队列的长度；如果为负数，那么MAXSIZE+len才是队列的长度 len = (len>0) ? len : MAXSIZE+len; return len; } //清空队列 void ClearQueue(Queue *Q) { //将队头指针和队尾指针都置为0 Q->front = Q->rear = 0; } //销毁队列 void DestroyQueue(Queue *Q) { //释放队列的存储空间 free(Q->base); //将队列基址置空 Q->base = NULL; }

Main.cpp

#include"SeqQueue.h" void main() { Queue Q; InitQueue(&Q); for(int i=1; i

【本文地址】

公司简介

联系我们