循环队列的基本操作（3种处理方式，2种实现方式）

为区分队空队满有3种处理方式：
①牺牲一个单元
②增设表示元素个数的数据成员
③增设tag数据成员

1.front->队头元素，rear->队尾元素下一位置

1.1牺牲一个单元

1.1.1定义

#define MaxSize 50
typedef struct {
	ElemType data[MaxSize];
	int front, rear;
}SqQueue;
1
2
3
4
5

1.1.2初始化

void InitQueue(SqQueue &Q) {
	Q.rear = Q.front = 0;
}
1
2
3

1.1.3判空

bool isEmpty(SqQueue Q) {
	if(Q.rear = Q.front)
		return true;
	else
		return false;
}
1
2
3
4
5
6

1.1.4 入队

bool EnQueue(SqQueue &Q, ElemType x) {
	if((Q.rear + 1) % MaxSize == Q.front)//队满报错
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	return true;
}
1
2
3
4
5
6
7

1.1.5出队

bool DeQueue(SqQueue &Q, ElemType &x) {
	if(Q.rear = Q.front)//队空报错
		return false;
	x = Q.data[Q.front];
	Q.front= (Q.front+ 1) % MaxSize;
	return true;
}
1
2
3
4
5
6
7

1.1.6 读队头元素

bool GetHead(SqQueue &S, ElemType &x) {
	if(Q.rear = Q.front)//队空报错
		return false;
	x = Q.data[Q.front];
	return true;
}
1
2
3
4
5
6

1.2增设表示元素个数的数据成员

1.2.1定义

#define MaxSize 50
typedef struct {
	ElemType data[MaxSize];
	int front, rear;
	int size;
}SqQueue;
1
2
3
4
5
6

1.2.2初始化

void InitQueue(SqQueue &Q) {
	Q.rear = Q.front = 0;
	Q.size = 0;
}
1
2
3
4

1.2.3判空

bool isEmpty(SqQueue Q) {
	if(Q.size == 0)
		return true;
	else
		return false;
}
1
2
3
4
5
6

1.2.4 入队

bool EnQueue(SqQueue &Q, ElemType x) {
	if(Q.size == MaxSize)//队满报错
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	return true;
}
1
2
3
4
5
6
7

1.2.5出队

bool DeQueue(SqQueue &Q, ElemType &x) {
	if(Q.size == 0)//队空报错
		return false;
	x = Q.data[Q.front];
	Q.front= (Q.front+ 1) % MaxSize;
	return true;
}
1
2
3
4
5
6
7

1.2.6 读队头元素

bool GetHead(SqQueue &S, ElemType &x) {
	if(Q.size == 0)//队空报错
		return false;
	x = Q.data[Q.front];
	return true;
}
1
2
3
4
5
6

1.3增设tag数据成员

1.3.1定义

#define MaxSize 50
typedef struct {
	ElemType data[MaxSize];
	int front, rear;
	int tag;
}SqQueue;
1
2
3
4
5
6

1.3.2初始化

void InitQueue(SqQueue &Q) {
	Q.rear = Q.front = 0;
	Q.tag = 0;
}
1
2
3
4

1.3.3判空

bool isEmpty(SqQueue Q) {
	if(Q.rear = Q.front && Q.tag == 0)
		return true;
	else
		return false;
}
1
2
3
4
5
6

1.3.4 入队

bool EnQueue(SqQueue &Q, ElemType x) {
	if(Q.rear = Q.front && Q.tag == 1)//队满报错
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	tag = 1;
	return true;
}
1
2
3
4
5
6
7
8

1.3.5出队

bool DeQueue(SqQueue &Q, ElemType &x) {
	if(Q.rear = Q.front && Q.tag == 0)//队空报错
		return false;
	x = Q.data[Q.front];
	Q.front= (Q.front+ 1) % MaxSize;
	tag = 1;
	return true;
}
1
2
3
4
5
6
7
8

1.2.6 读队头元素

bool GetHead(SqQueue &S, ElemType &x) {
	if(Q.rear = Q.front && Q.tag == 0)//队空报错
		return false;
	x = Q.data[Q.front];
	return true;
}
1
2
3
4
5
6

2.front->队头元素，rear->队尾元素

2.1牺牲一个单元

2.1.1定义

#define MaxSize 50
typedef struct {
	ElemType data[MaxSize];
	int front, rear;
}SqQueue;
1
2
3
4
5

2.1.2初始化

void InitQueue(SqQueue &Q) {
	Q.front = 0;
	Q.rear = MaxSize - 1;
}
1
2
3
4

2.1.3判空

bool isEmpty(SqQueue Q) {
	if((Q.rear + 1) % MaxSize == Q.front)
		return true;
	else
		return false;
}
1
2
3
4
5
6

2.1.4 入队

bool EnQueue(SqQueue &Q, ElemType x) {
	if((Q.rear + 2) % MaxSize == Q.front)//队满报错
		return false;
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.data[Q.rear] = x;
	return true;
}
1
2
3
4
5
6
7

2.1.5出队

bool DeQueue(SqQueue &Q, ElemType &x) {
	if((Q.rear + 1) % MaxSize == Q.front)//队空报错
		return false;
	x = Q.data[Q.front];
	Q.front= (Q.front+ 1) % MaxSize;
	return true;
}
1
2
3
4
5
6
7

2.1.6 读队头元素

bool GetHead(SqQueue &S, ElemType &x) {
	if((Q.rear + 1) % MaxSize == Q.front)//队空报错
		return false;
	x = Q.data[Q.front];
	return true;
}
1
2
3
4
5
6

2.2增设表示元素个数的数据成员

2.2.1定义

#define MaxSize 50
typedef struct {
	ElemType data[MaxSize];
	int front, rear;
	int size;
}SqQueue;
1
2
3
4
5
6

2.2.2初始化

void InitQueue(SqQueue &Q) {
	Q.front = 0;
	Q.rear = MaxSize - 1;
	Q.size = 0;
}
1
2
3
4
5

2.2.3判空

bool isEmpty(SqQueue Q) {
	if(Q.size == 0)
		return true;
	else
		return false;
}
1
2
3
4
5
6

2.2.4 入队

bool EnQueue(SqQueue &Q, ElemType x) {
	if(Q.size == MaxSize)//队满报错
		return false;
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.data[Q.rear] = x;
	return true;
}
1
2
3
4
5
6
7

2.2.5出队

bool DeQueue(SqQueue &Q, ElemType &x) {
	if(Q.size == 0)//队空报错
		return false;
	x = Q.data[Q.front];
	Q.front= (Q.front+ 1) % MaxSize;
	return true;
}
1
2
3
4
5
6
7

2.2.6 读队头元素

bool GetHead(SqQueue &S, ElemType &x) {
	if(Q.size == 0)//队空报错
		return false;
	x = Q.data[Q.front];
	return true;
}
1
2
3
4
5
6

2.3增设tag数据成员

2.3.1定义

#define MaxSize 50
typedef struct {
	ElemType data[MaxSize];
	int front, rear;
	int tag;
}SqQueue;
1
2
3
4
5
6

2.3.2初始化

void InitQueue(SqQueue &Q) {
	Q.front = 0;
	Q.rear = MaxSize - 1;
	Q.tag = 0;
}
1
2
3
4
5

2.3.3判空

bool isEmpty(SqQueue Q) {
	if((Q.rear + 1) % MaxSize == Q.front && Q.tag == 0)
		return true;
	else
		return false;
}
1
2
3
4
5
6

2.3.4 入队

bool EnQueue(SqQueue &Q, ElemType x) {
	if((Q.rear + 1) % MaxSize == Q.front && Q.tag == 1)//队满报错
		return false;
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.data[Q.rear] = x;
	tag = 1;
	return true;
}
1
2
3
4
5
6
7
8

2.3.5出队

bool DeQueue(SqQueue &Q, ElemType &x) {
	if((Q.rear + 1) % MaxSize == Q.front && Q.tag == 0)//队空报错
		return false;
	x = Q.data[Q.front];
	Q.front= (Q.front+ 1) % MaxSize;
	tag = 1;
	return true;
}
1
2
3
4
5
6
7
8

2.3.6 读队头元素

bool GetHead(SqQueue &S, ElemType &x) {
	if((Q.rear + 1) % MaxSize == Q.front && Q.tag == 0)//队空报错
		return false;
	x = Q.data[Q.front];
	return true;
}
1
2
3
4
5
6