✅作者简介：热爱后端语言的大学生，CSDN内容合伙人
✨精品专栏：C++面向对象
🔥系列专栏：算法百炼成神

文章目录

• 🔥前言
• 1、AB7 【模板】队列
• • 1.1、解题思路
  • 1.2、代码实现及解析
• 2、AB8 【模板】循环队列
• • 2.1、解题思路
  • 2.2、代码实现及解析

🔥前言

本专栏收录的均为牛客网的算法题目，内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目，也有大厂的面试真题，面试、找工作完全可以来这里找机会。此外，网站内的编码主题多样化，调试功能可运用性强，可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗，快去注册开启算法百炼成神之路吧！

1、AB7 【模板】队列

题目链接：设计队列

考查队列的基本特点、类的设计，适合新手入门与老手巩固，不妨挑战一下

题目描述：

1.1、解题思路

解决此题需要明白队列的属性及含义：

• 初始状态下的队列示意图：
  
• 有元素入队后的队列示意图：
  
• 队首指针front和队尾指针rear是队列操作的核心
• 数组buffer可以看作是队列所占的空间
• 初始状态队首指针和队尾指针都在下标0的位置
• 随着元素入队，rear向后移动，front不变，只有出队操作可以让其向后移动

1.2、代码实现及解析

本题源码：

#include using namespace std;class queue {    int tail = 0;    int head = 0;    int buffer[100001];  public:    void push(int x) { buffer[tail++] = x;    }    void pop() { if (tail == head)     cout << "error" << endl; else     cout << buffer[head++] << endl;    }    void front() { if (tail == head)     cout << "error" << endl; else     cout << buffer[head] << endl;    }};int main() {    queue q;    int n;    cin >> n;    for (int i = 0; i < n; i++) { string op; cin >> op; if (op == "push") {     int x;     cin >> x;     q.push(x); } else if (op == "pop")     q.pop(); else     q.front();    }    return 0;}

重要注释：

• 初始化队首和队尾指针为0，根据操作次数n来确定队列大小为100001
• push操作会让队尾指针rear向后移动，因此使用了自增的形式
• front操作需要先判断队列是否为空，若为空就打印error，反之打印队首元素buffer[front]
• pop操作在front操作的基础上让队首指针自增，相当于队首出队

2、AB8 【模板】循环队列

题目链接：循环队列

在上面题的基础上，加了循环的特点，思考一下队空或者队满的条件即可解题

题目描述：

2.1、解题思路

根据输入描述可以知道循环队列可利用空间大小是由我们输入的，提前并不可知，因此直接封装成一个队列类不太合适。所以我把队列当作数组来处理，根据方法的要求来设计循环队列：

1. 当队首指针front和队尾指针rear相等时，代表的要么是队空或者队满：
   • 我们可以把front==rear当作队空的条件
   • 队满的判断：
     当循环队列中只剩下一个空存储单元时，队列就已经满了，
     因此队满条件为：(rear+1)%(n+1)==front
2. push操作先判断队列是否已满，如果满就输出full，反之元素入队，队尾指针rear循环
3. front操作先判断队列是否为空，如果空就输出empty，反之打印队首指针对应的元素
4. 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更新指针的操作一定不要漏掉

队列和循环队列的设计算法到此结束，下篇文章将更新链表的基本操作，期待你的关注！