考研篇——数据结构王道3.2.2_队列的顺序实现

1.实现方式说明

多在选择题中考察

队尾指针（rear）有两种指向方式：

• 队尾指针指向队尾元素的位置，
• 队尾指针指向队尾元素的下一个位置。

区分队空与队满：

1. 牺牲一个存储空间，利用队头元素和队尾元素的相对位置来区分队空与队满。
2. 增加一个变量size记录队列元素个数
3. 增加一个变量tag记录操作是删除（tag为0）还是插入（tag为1），插入后rear（队尾）=front是队满，删除后rear=front是队空。

所以队列的实现一共有六种情况

书写代码注意操作实现的前提条件，也就是逻辑问题：

1. 查、删的前提是队列非空，要进行判断；
2. 插入的前提是队列不满，要进行判断。

静态数组实现的队列是循环队列，为了循环利用空间，rear的下一个元素为(rear+1)%MaxSize.

2.代码实现

2.1

2.1.1 代码1

C++静态数组实现rear（队尾指针）指向队尾元素的下一个元素，且牺牲一个存储空间来区分队满和队空的判断。
这种情况下队列的长度为(rear+MaxSize-front)%MaxSize.

#include <stdio.h>
#include <assert.h>
#define MaxSize 10
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int front, rear;
}SqQueue;
void InitQueue(SqQueue &Q)
{
	Q.rear = Q.front = 0;
}
bool QueueEmpty(SqQueue Q)
{
	if (Q.rear == Q.front)
		return true;
	else
		return false;
}
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;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{
	if (QueueEmpty(Q))
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	return true;
}
bool GetHead(SqQueue Q, ElemType& x)
{
	//assert(!QueueEmpty(Q));
	if (QueueEmpty(Q))
		return false;
	x = Q.data[Q.front];
	return true;
}
void testQueue()
{
	SqQueue Q;
	InitQueue(Q);
	//printf("%d\n",QueueEmpty(Q));
	EnQueue(Q, 5);
	int x = 0;
	DeQueue(Q, x);
	GetHead(Q, x);
	printf("%d\n",x);
}
int main() {
	testQueue();
	return 0;
}

后续代码与代码1相同的部分省略

2.1.2 代码2

C++静态数组实现rear（队尾指针）指向队尾元素的下一个元素，且增加一个变量size记录队列长度来区分队满和队空的判断。

//队尾指针指向队尾元素
//引入size变量来记录队列元素个数
typedef struct {
	ElemType data[MaxSize];
	int front, rear;
	int size;
}SqQueue;
void InitQueue(SqQueue& Q)
{
	Q.rear = Q.front = 0;
	Q.size = 0;
}
bool QueueEmpty(SqQueue Q)
{
	if (Q.size==0)
		return true;
	else
		return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
	if (Q.size==MaxSize)//队满的判断
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.size++;
	return true;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{
	if (QueueEmpty(Q))
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	Q.size--;
	return true;
}

2.1.3 代码3

C++静态数组实现rear（队尾指针）指向队尾元素的下一个元素，且增加一个变量tag来记录判断前队列的上一步操作是入队还是出队来区分队满和队空的判断。

//队尾指针指向队尾元素
//引入tag变量来记录队列元素个数，元素入队tag为1，出队tag为1
typedef struct {
	ElemType data[MaxSize];
	int front, rear;
	int tag;
}SqQueue;
void InitQueue(SqQueue& Q)
{
	Q.rear = Q.front = 0;
	Q.tag = 0;
}
bool QueueEmpty(SqQueue Q)
{
	if (Q.rear == Q.front&&Q.tag==0)
		return true;
	else
		return false;
}
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;
	Q.tag = 1;
	return true;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{
	if (QueueEmpty(Q))
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	Q.tag = 0;
	return true;
}

其实我们遇到的问题是，Q.rear==Q.front可以表示队空和队满两种状态，那么我们考虑怎么将二者分开呢？1.牺牲一个存储单元，将队满对队空的判断条件区别开；2.增加size变量；3.增加tag变量，只有入队之后才有可能队满，出队之后才有可能队空。
三种情况的对比图如下：

2.2

2.2.1 代码4

C++静态数组实现rear（队尾指针）指向队尾元素，且牺牲一个存储空间来区分队满和队空的判断。

//队尾指针指向队尾元素下一个元素
//牺牲一个存储空间
void InitQueue(SqQueue& Q)
{
	Q.rear = -1;
	Q.front = 0;
}
bool QueueEmpty(SqQueue Q)
{
	if ((Q.rear + 1) % MaxSize == Q.front)
		return true;
	else
		return false;
}
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;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{
	if (QueueEmpty(Q))
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	return true;
}

2.2.5 代码5

C++静态数组实现rear（队尾指针）指向队尾元素，且增加一个变量size记录队列长度来区分队满和队空的判断。

typedef struct {
	ElemType data[MaxSize];
	int front, rear;
	int size;
}SqQueue;
void InitQueue(SqQueue& Q)
{
	Q.rear = -1;
	Q.front = 0;
	Q.size=0;
}
bool QueueEmpty(SqQueue Q)
{
	if (Q.size==0)
		return true;
	else
		return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
	if (Q.size==MaxSize)
		return false;
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.data[Q.rear] = x;
	Q.size++;
	return true;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{
	if (QueueEmpty(Q))
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	Q.size--;
	return true;
}

2.2.6 代码6

C++静态数组实现rear（队尾指针）指向队尾元素的下一个元素，且增加一个变量tag来记录判断前队列的上一步操作是入队还是出队来区分队满和队空的判断。

typedef struct {
	ElemType data[MaxSize];
	int front, rear;
	int tag;
}SqQueue;
void InitQueue(SqQueue& Q)
{
	Q.rear = -1;
	Q.front = 0;
	Q.tag=0;
}
bool QueueEmpty(SqQueue Q)
{
	if (Q.tag==0)
		return true;
	else
		return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
	if ((Q.rear + 1) % MaxSize == Q.front &&Q.tag==0)
		return false;
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.data[Q.rear] = x;
	Q.tag=1;
	return true;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{
	if (QueueEmpty(Q))
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	Q.tag=0;
	return true;
}

总结

以上部分为王道课件代码，部分为自写代码，有问题欢迎交流。
注：王道本身图画得很形象，此处不再做图，有兴趣的伙伴可以去看一下王道该章节的内容。