行业资讯
您现在所在的位置:首页>企业动态>行业资讯

循环队列

编辑:学到牛牛IT培训    发布日期: 2023-10-08 08:56:07  


循环队列是指以数组实现的队列,是解决顺序队列内存空间利用率最大化的一种解决方案。


1.jpg


如上图就是队列元素的入队列和出队列的操作过程,在入队列时,元素只能从队尾进入队列,而在出队列的时候则只能从队首出,也就是我们常说的“先进先出“。以这种方式进行数据的入队出队,会造成数组前面出现空闲单元未被充分使用,这种现象也称为假溢出。

针对顺序队列出现的假溢出现象,我们一般可以使用循环队列的方式去解决。循环队列的构造图如下:


2.jpg


那么当循环队列为空或为满的时候,都是头指针和尾指针相等,即front == rear。当front == rear的时候怎么判断为空为满呢?我们可以设置一个计数器,当新元素入队时计数器加一,元素出队时计数器减一,当计数器==队列长度时队满,当计数器 == 0时队空。或者保留一个元素空间,当队尾指针的空闲单元的后继单元是队头元素所在的位置时,队满。队满的条件为(q->rear+1)%SIZEOF_MAX == q->front;队空的条件为q->rear == q->front。

代码如下: 

#include <stdio.h>

#include <string.h>

#define SIZEOF_MAX 10


struct stack

{

int arr[SIZEOF_MAX];

int front;    //队首 

int rear;    //队尾 

};


void init(struct stack *p) //初始化队列

{

p->front = 0;

p->rear = 0; //定义头尾指针的初始状态

memset(p->arr, 0, sizeof(p->arr)); //将队列的内存置零

printf("队列初始化成功 ");

printf("队列总长度为:%d ",SIZEOF_MAX);

}


int isFull(struct stack *p) //判断队列是否为满

{

if((p->rear+1)%SIZEOF_MAX == p->front) //当尾指针为队列最大值时队列为满

{

return 1;

}

else

{

return 0;

}

}


int isEmpty(struct stack *p) //判断队列是否为空

{

if(p->rear == p->front) //当头指针和尾指针重合时队列为空

{

return 1;

}

else

{

return 0;

}

}


int push(struct stack *p, int val) //入队列

{

if(isFull(p) == 1) //先判断队列是否为满

{

printf("FULL! ");

return -1;

}

p->arr[p->rear] = val;

p->rear = (p->rear + 1)%SIZEOF_MAX;

printf("入队成功,入队元素为 %d ", val);

printf("队首: %d   队尾: %d ", p->front, p->rear);

return 0;

}


int pop(struct stack *p) //出队列

{

if(isEmpty(p) == 1) //先判断队列是否为空

{

printf("EMPTY! ");

return -1;

}

int result = p->arr[p->front]; //先将要出队列的元素存放

p->arr[p->front] = 0; //再将该元素置零

p->front = (p->front + 1)%SIZEOF_MAX; //头指针指向下一元素

printf("出队成功,出队元素为 %d ", result);

printf("队首: %d   队尾: %d ", p->front, p->rear);

return result;

}


int show(struct stack *p) //队列的遍历

{

int i = 0;

int len = 0;

int res = 0;

if(isEmpty(p) == 1)

{

printf("EMPTY! ");

return 0;

}

i = p->front;

while(i != p->rear)

{

len++;

printf("%d ", p->arr[i]);

i = (i + 1)%SIZEOF_MAX;


}

printf(" ");

res = SIZEOF_MAX - 1 - len;

printf("队列使用空间:%d ", len);

printf("队列剩余空间:%d ", res);

}



int main()

{

struct stack sta;

struct stack *p = &sta;

init(p);

int i = 0;

for(i = 0; i < SIZEOF_MAX; i++) //入队列操作

{

push(p, i+1);

show(p);

printf(" ");

}

for(i = 0; i < SIZEOF_MAX; i++) //出队列操作

{

pop(p);

show(p);

printf(" ");

}

return 0;


免费试学
课程好不好,不如实地听一听

封闭学习

2

1

联系我们

电话:028-61775817

邮箱:1572396657@qq.com

地址:成都市金牛区西城国际A座8楼

  • 新闻频道_关注IT技术应用资讯-学到牛牛
    新闻频道_关注IT技术应用资讯-学到牛牛

    扫一扫,免费咨询

  • 新闻频道_关注IT技术应用资讯-学到牛牛
    新闻频道_关注IT技术应用资讯-学到牛牛

    微信公众号

  • 新闻频道_关注IT技术应用资讯-学到牛牛
新闻频道_关注IT技术应用资讯-学到牛牛

学一流技术,找高薪工作

新闻频道_关注IT技术应用资讯-学到牛牛

7-24小时服务热线:

028-61775817

版权声明 网站地图

蜀ICP备2021001672号

课程问题轻松问