数据结构(3.5)——队列的顺序实现

队列的顺序实现

#define MaxSize 10//定义队列中元素的最大个数
typedef struct {
	int data[MaxSize];//用静态数组存放队列元素
	int front, rear;//队头指针和队尾指针
} SqQueue;

void testQueue() {
	SqQueue Q;//声明一个队列(顺序存储)
}

队列的初始化操作和判空

//初始化队列
void InitQueue(SqQueue& Q) {
	//初始时 队头、队尾指针指向0
	Q->rear = Q->front = 0;
}
//判断队列是否为空
bool QueueEmpty(SqQueue Q) {
	if (q.rear == Q.front) {//判空条件
		return true;
	}
	else {
		return false;
	}
}

循环队列——入队操作

以下情况我们重点先考虑尾指针指向队尾元素的后一位情况

队列的入队操作只能从队尾入队(插入)

//入队
bool EnQueue(SqQueue& Q, int x) {
	if (Q.rear + 1) % MaxSize == Q.front){//判断队满
		return false;//队满报错
	}
	else {
		Q.data[Q.rear] = x;//新元素插入队尾
		Q.rear = (Q.rear + 1) % MaxSize;//队尾指针加1取模，队尾指针后移
		return true;
	}
}

该函数中的

		Q.rear = (Q.rear + 1) % MaxSize;//队尾指针加1取模

这一行代码实则是将一个顺序队列变成了循环队列

循环队列——入队操作

//出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue& Q, int& x) {
	if (Q.rear == Q.front) {//判断队空
		return false;//队空则报错
	}
	else {
		x = Q.data[Q.front];
		Q.front = (Q.front + 1) & MaxSize;//队头指针后移
		return true;
	}
}

循环队列——读取队头操作

读取队头的操作和出队操作很类似，只是将表格引用符号去掉，并且不要让队头指针往后移就行

//获得队头元素的值，用x返回
bool GetHead(SqQueue Q, int& x) {
	if (Q.rear == Q.front) {//判断队空
		return false;//队空则报错
	}
	else {
		x = Q.data[Q.front];
		return true;
	}
}
void testQueue() {
	SqQueue Q;//声明一个队列(顺序存储)
}

计算队列元素个数：

(rear+MaxSize-front)%MaxSize

方法二：增加一个辅助变量size判断空判满

由于刚刚第一种方法判空和判满会造成一些不必要的内存空间浪费，于是我们在队列中添加一个size来表示队列的长度，并且记录队列的入队和出队变化

typedef struct {
	int data[MaxSize];//用静态数组存放队列元素
	int front,rear;//队头指针和队尾指针
	int size;//队列当前长度
} SqQueue;
//初始化队列
void InitQueue(SqQueue& Q) {
	//初始时 队头、队尾指针指向0
	Q.rear = Q.front = 0;
	Q.size=0;
}

方法三：增加一个辅助变量tag判断空判满

#define MaxSize 10//定义队列中元素的最大个数
typedef struct {
	int data[MaxSize];//用静态数组存放队列元素
	int front,rear;//队头指针和队尾指针
	int tag;//最近进行的是删除为0/插入为1
} SqQueue;

例子：

// 初始化队列
void InitQueue(SqQueue *Q) {
	Q->front = Q->rear = 0;
	Q->tag = 0;
}

// 判断队列是否为空
int IsEmpty(SqQueue Q) {
	return Q.front == Q.rear && Q.tag == 0;
}

// 判断队列是否已满
int IsFull(SqQueue Q) {
	return Q.front == Q.rear && Q.tag == 1;
}

// 入队操作
int EnQueue(SqQueue *Q, int x) {
	if (IsFull(*Q)) {
		return 0; // 队列已满，入队失败
	}
	Q->data[Q->rear] = x;
	Q->rear = (Q->rear + 1) % MaxSize; // 循环使用数组
	Q->tag = 1;
	return 1; // 入队成功
}

// 出队操作
int DeQueue(SqQueue *Q, int *x) {
	if (IsEmpty(*Q)) {
		return 0; // 队列为空，出队失败
	}
	*x = Q->data[Q->front];
	Q->front = (Q->front + 1) % MaxSize; // 循环使用数组
	Q->tag = 0;
	return 1; // 出队成功
}