循环队列讲解
循环队列
循环队列是指以数组实现的队列，是解决顺序队列内存空间利用率最大化的一种解决方案。
如上图就是队列元素的入队列和出队列的操作过程，在入队列时，元素只能从队尾进入队列，而在出队列的时候则只能从队首出，也就是我们常说的“先进先出“。以这种方式进行数据的入队出队，会造成数组前面出现空闲单元未被充分使用，这种现象也称为假溢出。
针对顺序队列出现的假溢出现象，我们一般可以使用循环队列的方式去解决。循环队列的构造图如下：
那么当循环队列为空或为满的时候，都是头指针和尾指针相等，即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;
}
