欢迎来到军工软件开发人才培养基地——学到牛牛

循环队列讲解

时间:2024-05-06 07:01:10 来源:学到牛牛

循环队列

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

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

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

那么当循环队列为空或为满的时候,都是头指针和尾指针相等,即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("队列初始化成功\n");

printf("队列总长度为:%d\n",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!\n");

return -1;

}

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

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

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

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

return 0;

}

 

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

{

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

{

printf("EMPTY!\n");

return -1;

}

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

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

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

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

printf("队首: %d   队尾: %d\n", 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!\n");

return 0;

}

i = p->front;

while(i != p->rear)

{

len++;

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

i = (i + 1)%SIZEOF_MAX;

}

printf("\n");

res = SIZEOF_MAX - 1 - len;

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

printf("队列剩余空间:%d\n", 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("\n");

}

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

{

pop(p);

show(p);

printf("\n");

}

return 0;