2、AB8 【模板】循环队列 题目链接：循环队列 在上面题的基础上，加了循环的特点，思考一下队空或者队满的条件即可解题 题目描述： 2.1、解题思路 根据输入描述可以知道循环队列可利用空间大小是由我们输入的，提前并不可知，因此直接封装成一个队列类不太合适。所以我把队列当作数组来处理，根据方法的要求来设计循环队列： 当队首指针front和队尾指针rear相等时，代表的要么是队空或者队满： 我们可以把front==rear当作队空的条件 队满的判断： 当循环队列中只剩下一个空存储单元时，队列就已经满了， 因此队满条件为：(rear+1)%(n+1)==front push操作先判断队列是否已满，如果满就输出full，反之元素入队，队尾指针rear循环 front操作先判断队列是否为空，如果空就输出empty，反之打印队首指针对应的元素 pop操作在front的基础上将队首指针front循环 2.2、代码实现及解析 本题源码： #include using namespace std; const int N = 100001; int a[N]; int front, rear = 0; int n, q; int MAXSIZE; int main() { cin >> n >> q; string oper; MAXSIZE = n + 1; while (q--) { cin >> oper; if (oper == "push") { //判断队满条件:front == (rear + 1) % MAXSIZE if (front == (rear + 1) % MAXSIZE) { int x; cin >> x; cout << "full" << endl; } else { int x; cin >> x; a[rear] = x; rear = (rear + 1) % MAXSIZE; } } else if (oper == "front") { //判断队空条件：front==rear if (rear == front) { cout << "empty" << endl; } else { cout << a[front] << endl; } } else { //判断队空条件：front==rear if (rear == front) { cout << "empty" << endl; } else { cout << a[front] << endl; front = (front + 1) % MAXSIZE; } } } return 0; } 重要注释： main函数之前是一些变量的声明和初始化，MAXSIZE等于n+1，用来更新指针 对此题而言栈满时push操作仍然需要从键盘上输入元素，否则将和输出结果不匹配 三种操作都需要事先判断栈空或者栈满，push和pop更新指针的操作一定不要漏掉 队列和循环队列的设计算法到此结束，下篇文章将更新链表的基本操作，期待你的关注！