【数据结构与算法】在循环队列中第k个元素之后插入元素的算法 C++实现（循环队列+模运算）

数组a[MaxSize]用作一个循环队列，front指向循环队列中队头元素的前一个位置，rear指向队尾元素的位置。设计在队列中第k个元素之后插入item的算法。

思路

首先，检查输入的位置 k 是否在合理的范围内，即 1 到 queueSize(Q)（包含两端）。如果 k 在这个范围外，那么返回 ERROR。

然后，计算插入位置 l。这里使用了模运算来处理循环队列的环状结构。如果 l 在队列的尾部和头部之间，那么 l 就是插入位置。否则，l 就是插入位置加上 MaxSize。

接下来，将队列的尾部 Q.rear 向后移动一位，为新元素 e 留出空位。这里也使用了模运算来处理循环队列的环状结构。

然后，从队列的尾部开始，将每个元素向后移动一位，直到到达插入位置 l。这个过程是通过一个循环来实现的，每次循环都将位置 p 的元素移动到位置 q，然后将 p 更新为 q。

最后，将新元素 e 插入到位置 l，然后返回 OK。

时间复杂度是 O ( n ) O(n) O(n)，其中 n n n 是队列的大小。这是因为在最坏的情况下，可能需要移动队列中的所有元素。空间复杂度是 O ( 1 ) O(1) O(1)，因为只使用了固定数量的额外空间，不依赖于输入的大小。

代码

#include <algorithm>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using Status = int;
using ElemType = int;

const int N = 1e6 + 7;
const int MaxSize = 100;
const int TRUE = 1;
const int FALSE = 0;
const int OK = 1;
const int ERROR = 0;
const int INFEASIBLE = -1;
// const int OVERFLOW = -2;

int n;
ElemType a[N];

struct CircularQueue {
	ElemType a[MaxSize];
	int front, rear;
};

Status initQueue(CircularQueue &Q) {
	Q.front = Q.rear = 0;
	return OK;
}

bool queueFull(CircularQueue Q) { return ((Q.rear + 1) % MaxSize == Q.front); }

bool queueEmpty(CircularQueue Q) { return (Q.front == Q.rear); }

int queueSize(CircularQueue &Q) {
	return ((Q.rear - Q.front + MaxSize) % MaxSize);
}

Status queuePush(CircularQueue &Q, ElemType e) {
	if (queueFull(Q)) {
		return ERROR;
	}
	Q.a[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MaxSize;
	return OK;
}

ElemType queueFront(CircularQueue Q) {
	if (queueEmpty(Q)) {
		return NULL;
	}
	return Q.a[Q.front];
}

Status queuePop(CircularQueue &Q) {
	if (queueEmpty(Q)) {
		return ERROR;
	}
	Q.front = (Q.front + 1) % MaxSize;
	return OK;
}

Status queueInsert(CircularQueue &Q, int k, ElemType e) {
	if (k < 1 || k > queueSize(Q)) {
		return ERROR;
	}
	int l = (Q.front + k - 1) % MaxSize;
	int p = Q.rear;
	Q.rear = (Q.rear + 1) % MaxSize;
	while (l < p) {
		int q = (p - 1) % MaxSize;
		Q.a[p] = Q.a[q];
		p = q;
	}
	Q.a[l] = e;
	return OK;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	CircularQueue Q;
	initQueue(Q);

	for (int i = 0; i < n; i++) {
		queuePush(Q, a[i]);
	}

	for (int i = 0; i < n; i++) {
		int f = queueFront(Q);
		cout << queueFront(Q) << " ";
		queuePop(Q);
		queuePush(Q, f);
	}
	cout << "\n";

	int k;
	ElemType e;
	cin >> k >> e;
	n += queueInsert(Q, k, e);

	for (int i = 0; i < n; i++) {
		int f = queueFront(Q);
		cout << queueFront(Q) << " ";
		queuePop(Q);
		queuePush(Q, f);
	}
	cout << "\n";
	return 0;
}