静态循环队列几个问题
1.静态队列为什么必须是循环队列?
因为不管是入队还是出队,front和rear都是增长的,静态队列使用的是数组来存放入队的数据,由于front和rear都是增长的,那么后方就会腾出空余的空间,为了重复利用,只能将front和rear增长到数组的末尾的时候,将值重新设置为数组第一个元素的位置.
2.循环队列需要几个参数来确定?
首先定义一个循环队列的结构体
typedef struct{
int length;
int * a;
int r;//队尾,入队数据向队尾添加
int f;//队头,出队从队头出队
int isFlag;//标记这个队列是否已满,0表示为空队列,1表示未满,2表示已满
}LoopQueue,*PLoopQueue;
3.循环队列的各个参数的含义?
- length 队列最多能同时入队的元素有多少个(队列的大小)
- a 指向一个指定大小的数组(通过malloc分配的一个length大小的数组)
- r 循环队列的队尾(入队的地方)
- f 循环队列的队头(出队的地方)
- isFlag 标记当前循环队列的:EMPTY(空),UNDER(不为空也没满),FULL(已满)
4.初始化队列
- 创建一个LoopQueue结构体变量
- 申请 length*sizeof(int) 的空间,并赋值给a
- 将r,f都设置成0
- 将isFlag设置成EMPTY
5.循环队列入队伪算法?
- 判满(因为是入队,当队满的时候,无法再继续入队)
- return false
- 否则队列未满,执行入队操作
- 将val赋值给数组位置为r的空间
- 将r加一并与length取余(这样就能非常简单的实现循环)的结果赋值给r
- 判断队列的状态
- 如果r == f(队头队尾在数组同一位置了,由于是入队操作导致r == f,所以只能是队已满),此时说明队列已满 isFlag 设置为 Full
- 否则 isFlag 设置为 UNDER(因为刚入队一个元素,肯定不能是EMPTY)
- return true
6.循环队列出队伪算法?
- 判空(因为是出队,当队列为空的时候,出队失败)
- return false
- 否则不为空,执行出队操作
- 将数组f位置的空间的值赋值给 *val
- 将f加一并与length取余的结果赋值给f
- 判断队列的状态
- 如果f==r(此时是出队操作,只有可能是队列为空了),说明队列为空,将isFlag设置为EMPTY
- 否则设置为UNDER,因为刚出队一个,不可能此时是 Full 了
- return true
程序实现
#include <stdio.h>
#include <stdlib.h>
#define EMPTY 0
#define UNDER 1
#define FULL 2
/**
* 循环队列
*/
typedef struct{
int length;
int * a;
int r;//队尾,入队数据向队尾添加
int f;//队头,出队从队头出队
int isFlag;//标记这个队列是否已满,0表示为空队列,1表示未满,2表示已满
}LoopQueue,*PLoopQueue;
/**
* 创建一个循环队列,默认大小是5
* @param length [description]
* @return [description]
*/
LoopQueue createLoopQueue(int length){
LoopQueue l;
if (length<5){
length=5;
}
l.length=length;
l.a=(int *)malloc(length*sizeof(int));
l.r=0;
l.f=0;
l.isFlag=EMPTY;
return l;
}
/**
* 入队,入队成功返回1,失败返回0
* @param pL [description]
* @param val [description]
* @return [description]
*/
int enqueue(PLoopQueue pL,int val){
if (pL->isFlag == FULL){
//队列已满,无法再添加数据
return 0;
}else{
//否则的话就将当前a数组的r所对应的位置用来存储值
(pL->a)[pL->r]=val;
//r的位置向前移动一次
//被坑的最惨的一次,后加加,使用之后加,在这儿必须使用前 pL->r + 1
pL->r = (pL->r + 1 ) % (pL->length);
//判断当前这个循环队列的状态,因为是如队,所以接下来添加一个元素的可能状态是,UNDER(未满),或者是FULL(满)
if (pL->r==pL->f){
//说明此时的队列已经装满了
pL->isFlag = FULL;
}else{
//说明此时的队列还没有装满
pL->isFlag = UNDER;
}
return 1;
}
}
/**
* 出队
* @param pL [description]
* @param val [description]
* @return [description]
*/
int dequeue(PLoopQueue pL,int * val){
if (pL->isFlag==EMPTY){
//队列为空,无法再出队
return 0;
}else{
//取值
*val=pL->a[pL->f];
//将值清除
pL->a[pL->f]=0;
//f向前移动
pL->f =( pL->f + 1 ) % pL->length;
//判断当前这个循环队列的状态,因为是出队,所以接下来移除一个元素的可能状态是,UNDER(未满),或者是EMPTY(空)
if (pL->f == pL->r){
//此时全部出队了,当前的队列为空
pL->isFlag = EMPTY;
}else{
pL->isFlag = UNDER;
}
return 1;
}
}
int main(){
LoopQueue loopQueue=createLoopQueue(50);
int i,flag;
int temp;
for(i=0;i<60;i++){
flag=enqueue(&loopQueue,i);
if(flag){
printf("入队%d\n", i);
}else{
printf("队列已满\n");
}
}
while(dequeue(&loopQueue,&temp)){
printf("出队%d\n", temp);
}
return 0;
}
