博客

循环队列处理队满和队空的方式

顺序存储的队列在队满时再进队出现的溢出往往是假溢出，即还有空间但用不上，为了有效利用队列空间，可将队列元素存放数组首尾相接，形成循环队列。

但是构造循环队列时不得不考虑到的问题就是如果不加以限制，队空和队满的情况是相同的。即队头指针和队尾指针的指向相同。

一般来说有以下三种解决方式：

方式一：

牺牲一个单元来区分队空和队满，也是普遍在利用的方式。

队满：（rear + 1）% QueueSize == front

队空：front == rear

队长：（rear – front + QueueSize）% QueueSize

#include<iostream>
using namespace std;
#define MaxSize 100

typedef struct{
	int data[MaxSize];
	int front = 0,rear = 0;
}SqQueue;

//判满 
bool QueueFull(SqQueue Q){
	return (Q.rear + 1)% MaxSize == Q.front;
}

//判空 
bool QueueEmpty(SqQueue Q){
	return Q.front == Q.rear;
}

//进队 
bool EnQueue(SqQueue &Q,int x){
	if(QueueFull(Q)) return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1)% MaxSize;
	return true;
}

//出队 
bool DeQueue(SqQueue &Q,int& x){
	if(QueueEmpty(Q)) return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1)% MaxSize;
	return true;
}

//队大小 
int QueueSize(SqQueue Q){
	return (Q.rear - Q.front + MaxSize)% MaxSize;
}

int main(){
	SqQueue q;
	cout<<QueueEmpty(q)<<endl;
	EnQueue(q,1);
	cout<<QueueEmpty(q)<<endl;
	int x = 0;
	DeQueue(q,x);
	cout<<x<<endl;
	cout<<QueueEmpty(q);
}

运行结果：

方式二：

增设 tag 数据成员以区分队满还是队空。

tag 表示 0 情况下，因删除导致 front == rear ，队空。

tag 表示 1 情况下，因插入导致 front == rear ，队满。

#include<iostream>
using namespace std;
#define MaxSize 3

typedef struct{
	int data[MaxSize];
	int front = 0,rear = 0;
	int tag = 0;
}SqQueue;

//队大小 
int QueueSize(SqQueue Q){
	if(Q.tag == 1) return MaxSize;
	return (Q.rear - Q.front + MaxSize)% MaxSize;
}

//判满 
bool QueueFull(SqQueue Q){
	return QueueSize(Q) == MaxSize;
}

//判空 
bool QueueEmpty(SqQueue Q){
	return QueueSize(Q) == 0;
}

//进队 
bool EnQueue(SqQueue &Q,int x){
	if(QueueFull(Q)) return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1)% MaxSize;
	if(Q.front == Q.rear && Q.tag == 0)
		Q.tag = 1;
	return true;
}

//出队 
bool DeQueue(SqQueue &Q,int& x){
	if(QueueEmpty(Q)) return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1)% MaxSize;
	Q.tag = 0;
	return true;
}

int main(){
	SqQueue q;
	cout<<QueueEmpty(q)<<endl;
	cout<<"tag"<<q.tag<<endl;
	EnQueue(q,1);
	int x = 0;
	DeQueue(q,x);
	EnQueue(q,1);
	EnQueue(q,1);
	EnQueue(q,1);
	cout<<"tag"<<q.tag<<endl;
}

运行结果：

方式三：

增设队列元素个数的数据成员 size。

队满：size == QueueSize

队空：size == 0

#include<iostream>
using namespace std;
#define MaxSize 3

typedef struct{
	int data[MaxSize];
	int front = 0,rear = 0;
	int size = 0;
}SqQueue;

//判满 
bool QueueFull(SqQueue Q){
	return Q.size == MaxSize;
}

//判空 
bool QueueEmpty(SqQueue Q){
	return Q.size == 0;
}

//进队 
bool EnQueue(SqQueue &Q,int x){
	if(QueueFull(Q)) return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1)% MaxSize;
	Q.size ++;
	return true;
}

//出队 
bool DeQueue(SqQueue &Q,int& x){
	if(QueueEmpty(Q)) return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1)% MaxSize;
	Q.size --;
	return true;
}

//队大小 
int QueueSize(SqQueue Q){
	return Q.size;
}

int main(){
	SqQueue q;
	cout<<QueueEmpty(q)<<endl;
	int x;
	cout<<DeQueue(q,x)<<endl;
	EnQueue(q,1);
	EnQueue(q,1);
	cout<<QueueFull(q)<<endl;
	EnQueue(q,1);
	cout<<QueueFull(q)<<endl;
	cout<<EnQueue(q,1);
}

运行结果：