数据结构——循环队列

思考

IMG_20241015_235239

头指针front指向的位置为队列头元素的前一个位置

尾指针rear指向的位置为队列尾元素

以上目的：为了区分队列是否为空或已满的判断条件

• 队列为空：当 front 和 rear 相等时，说明队列中没有元素，此时为空队列。
• 队列已满：当 (rear + 1) % MAXSIZE == front 时，说明队列已满，因为rear 紧跟在 front 的前面，队列的最后一个位置不可用，否则会与空队列的情况冲突。

注意事项：

由于判断队列满的条件需要 front 位置与 rear + 1 相等，意味着最多只能使用 MAXSIZE - 1 个元素的位置，这种策略用于避免空队列与满队列状态混淆。

若不做此区分，队空和队满的判断条件都是(rear + 1) % MAXSIZE == front，会发生混淆

代码

//循环队列
const int MAXSIZE = 100;
typedef struct {
	int data[MAXSIZE];
	int front;
	int rear;
}Queue;

//初始化队列
void InitQueue(Queue& Q) {
	Q.front = 0;
	Q.rear = 0;
}

//判断队列是否为空
bool IsEmpty(Queue Q) {
	return Q.front == Q.rear;
}

//判断队列是否已满
bool IsFull(Queue Q) {
	return (Q.rear + 1) % MAXSIZE == Q.front;
}

//入队
void push(Queue& Q, int x) {
	if (IsFull(Q)) {
		cout << "队列已满" << endl;
		return;
	}
	//指针先向后移动，再赋值
	Q.rear = (Q.rear + 1) % MAXSIZE;
	Q.data[Q.rear] = x;
}

//出队
int pop(Queue& Q) {
	if (IsEmpty(Q)) {
		cout << "队列为空" << endl;
		return -1;
	}
	//指针先向后移动，再返回值
	Q.front = (Q.front + 1) % MAXSIZE;
	return Q.data[Q.front];
}

//获取队头元素
int getFront(Queue Q) {
	if (IsEmpty(Q)) {
		cout << "队列为空" << endl;
		return -1;
	}
	//指针向后移动，再返回值，front指针指向的是队头元素的前一个位置
	return Q.data[(Q.front + 1) % MAXSIZE];
}

//获取队尾元素
int getRear(Queue Q) {
	if (IsEmpty(Q)) {
		cout << "队列为空" << endl;
		return -1;
	}
	//rear指针指向的是队尾元素
	return Q.data[Q.rear];
}

//测试函数
int main() {
	Queue Q;
	InitQueue(Q);
	push(Q, 1);
	push(Q, 2);
	push(Q, 3);
	cout << getFront(Q) << endl;
	cout << getRear(Q) << endl;
	cout << pop(Q) << endl;
	cout << getFront(Q) << endl;
	cout << getRear(Q) << endl;
	return 0;
}

注意事项：

入队逻辑：rear指针先向后移动一位，再赋值

出队逻辑：front指针先向后移动一位，再返回值，因为front指针指向的是队头元素的前一个位置

参考文献

【队列&循环队列】手动实现循环队列，掌握循环队列的每一处细节_哔哩哔哩_bilibili