时间戳

首页 > 技术文章 > 循环队列的判断满、空的三种方法以及具体代码实现（数组实现）

循环队列的判断满、空的三种方法以及具体代码实现（数组实现）

leechanx 2013-09-12 12:29 原文


由于循环队列的特殊性，当队首指针=队尾指针的时候，既可能表示空也可能表示满，所以需要另加一个判断位。

我现在介绍的循环队列判断满空的三种方法分别是：1.设标志位法  2.预留一位法； 3.预存长度法（顾名思义，很简单）


1.设标志位法  

思路：预设一个标志,tag，初值=0，每当入队成功，tag=1；每当出队成功，tag=0；那么，当front==rear &&  tag 则表示“在入队操作之后front=rear”，显然入队造成的f=r的原因就是满了，故 front==rear &&  tag 表示队列满；同理，front==rear && !tag 表示队列空。 

例子：初始:front=-1,rear=-1,tag=0,下面对队列queue[3]执行：入1，出2，出3，入4，入5，入6，入7，出8，入9，入10  的动作。

          （1）入1：此时f=r=-1,tag=0 说明为空，可以入队,存入queue[rear++]，入队之后，tag=1, rear=rear+1%3;

          （2）出2：此时f=-1,r=0,可以出队，出队内容是queue[front++]，出队之后，tag=0,front=front+1%3；

          （3）出3：此时f=r=0,tag=0 说明为空，不能再出队了，过；

          （4）入4：此时f=r=0,tag=0 为空，可以入队，存入queue[rear++],入队之后，tag=1,rear=rear+1%3;

          （5）入5：此时f=0，r=1，tag=0 ，可以入队，存入queue[rear++],入队之后，tag=1,rear=rear+1%3;

          （6）入6：此时f=0，r=2，tag=0 ，可以入队，存入queue[rear++],入队之后，tag=1,rear=rear+1%3;

          （7）入7：此时f=0=r，tag=1 ，说明队列满了，不可入队，过;

          （8）出8：此时f=0=r，tag=1 ，说明队列满,可以出队，出队内容是queue[front++]，出队之后，tag=0,front=front+1%3；

 

           （9）入9：此时f=1，r=0，tag=0 ，可以入队，存入queue[rear++],入队之后，tag=1,rear=rear+1%3;

          （10）入10：此时f=r=1，tag=1 ，说明队列满了，不可入队，过;

代码如下：

#include <stdio.h>
#include <stdlib.h>
#define MAXQUEUE 5
struct Student{
	char name[20];
	char id[20];
};
typedef struct Student student;
student Queue[MAXQUEUE];// queue
int front=-1;  
int rear=-1;
int tag=0;
void enqueue(student new);
student* dequeue();

main(){
	student mystu[10]={
		{"LeechanX","1100300803"},
		{"CongBaoE","1100300804"},
		{"Hebe","1100300708"},
		{"AiNi","1100300801"},
		{"Wang","1100300812"},
		{"PaoziBianwa","1100300831"},
		{"Daijuhua","1100300829"},
		{"Haomeng","1100300422"},
		{"Gengbaoe","1100300621"},
		{"Zhaoyan","1100300501"}		
	};
	int i=0;
	for(;i<2;i++)
		enqueue(mystu[i]);

	printf("Queue written over...\n");
	student* stu;
	i=0;
	
	for(;i<1;i++){
		stu=dequeue();
		if(!stu) break;
		printf("Name:%s,ID:%s\n",stu->name,stu->id);
		printf("---\n");
	}
	
	enqueue(mystu[3]);
	enqueue(mystu[4]);
	enqueue(mystu[5]);
	enqueue(mystu[6]);
	enqueue(mystu[7]);
	
	for(;;){
		stu=dequeue();
		if(!stu) break;
		printf("Name:%s,ID:%s\n",stu->name,stu->id);
	}

}

void enqueue(student new){
	if(tag && front==rear)	return;
	rear++;
	rear=rear%MAXQUEUE;
	Queue[rear]=new;
	tag=1;
}

student* dequeue(){
	if(front==rear && !tag)	return NULL;
	front++;
	front=front%MAXQUEUE;
	tag=0;
	return &(Queue[front]);
}


2.预留一位法：  

思路：让front指向头部之前的那一位，rear指向尾部，这样一来，实际使用空间是SIZE-1。

当front=(rear+1)%SIZE or  (front==-1 && rear=SIZE-2)  的时候，说明满了（其实没有满，但是剩下的那个空间不可用）

当front==rear的时候，说明空。

这个方法相信所有的书里都有。

例子：初始:front=-1,rear=-1,tag=0,下面对队列queue[3]执行：入1，出2，出3，入4，入5，入6

 

          （1）入1：此时f=r=-1说明为空，可以入队,存入queue[rear++]，入队之后，tag=1, rear=rear+1%3;

          （2）出2：此时f=-1,r=0,可以出队，出队内容是queue[front++]，出队之后，tag=0,front=front+1%3；

          （3）出3：此时f=r=0 说明为空，不能再出队了，过；

          （4）入4：此时f=r=0 为空，可以入队，存入queue[rear++],入队之后，tag=1,rear=rear+1%3;

          （5）入5：此时f=0，r=1，tag=0 ，可以入队，存入queue[rear++],入队之后，tag=1,rear=rear+1%3;

          （6）入6：此时f=0，r=2，（r+1）%SIZE=f,说明满了，不可以入队，过;  存储的实际空间是2。

代码：
#include <stdio.h>
#include <stdlib.h>

#define MAXQUEUE 5
struct Student{
	char name[20];
	char id[20];
};

typedef struct Student student;
student Queue[MAXQUEUE];

int front=-1; // means start, using in dequeue(read)
int rear=-1; // means end, using in enqueue(write)
void enqueue(student new);
student* dequeue();

main(){
	student mystu[10]={
		{"LeechanX","1100300803"},
		{"CongBaoE","1100300804"},
		{"Hebe","1100300708"},
		{"AiNi","1100300801"},
		{"Wang","1100300812"},
		{"PaoziBianwa","1100300831"},
		{"Daijuhua","1100300829"},
		{"Haomeng","1100300422"},
		{"Gengbaoe","1100300621"},
		{"Zhaoyan","1100300501"}		
	};
	int i=0;
	for(;i<2;i++)
		enqueue(mystu[i]);

	printf("Queue written over...\n");
	student* stu;
	i=0;
	
	for(;i<1;i++){
		stu=dequeue();
		if(!stu) break;
		printf("Name:%s,ID:%s\n",stu->name,stu->id);
		printf("---\n");
	}
	enqueue(mystu[3]);
	enqueue(mystu[4]);
	enqueue(mystu[5]);
	enqueue(mystu[6]);
	enqueue(mystu[7]);
	for(;;){
		stu=dequeue();
		if(!stu) break;
		printf("Name:%s,ID:%s\n",stu->name,stu->id);
		printf("---\n");
	}
}

void enqueue(student new){
	if((rear+1)%MAXQUEUE==front || (front==-1 && rear==MAXQUEUE-2)
)	return;
	rear++;
	rear=rear%MAXQUEUE;
	Queue[rear]=new;
}

student* dequeue(){
	if(front==rear)	return NULL;
	front++;
	front=front%MAXQUEUE;
	return &(Queue[front]);
}



3.预存长度法：

思路：就是加一个变量存储长度，入队成功+1，出队成功-1，=0空，=SIZE满，太简单，不说了。










推荐阅读