【算法入门】设计模板队列|循环队列

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

文章目录

🔥前言

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

1、AB7 【模板】队列

题目链接：设计队列

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

题目描述：

1.1、解题思路

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

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

1.2、代码实现及解析

本题源码：

#include<iostream>usingnamespace std;classqueue{int tail =0;int head =0;int buffer[100001];public:voidpush(int x){
        buffer[tail++]= x;}voidpop(){if(tail == head)
            cout <<"error"<< endl;else
            cout << buffer[head++]<< endl;}voidfront(){if(tail == head)
            cout <<"error"<< endl;else
            cout << buffer[head]<< endl;}};intmain(){
    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);}elseif(op =="pop")
            q.pop();else
            q.front();}return0;}

重要注释：

• 初始化队首和队尾指针为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<iostream>usingnamespace std;constint N =100001;int a[N];int front, rear =0;int n, q;int MAXSIZE;intmain(){
    cin >> n >> q;
    string oper;
    MAXSIZE = n +1;while(q--){
        cin >> oper;if(oper =="push"){//判断队满条件:front == (rear + 1) % MAXSIZEif(front ==(rear +1)% MAXSIZE){int x;
                cin >> x;
                cout <<"full"<< endl;}else{int x;
                cin >> x;
                a[rear]= x;
                rear =(rear +1)% MAXSIZE;}}elseif(oper =="front"){//判断队空条件：front==rearif(rear == front){
                cout <<"empty"<< endl;}else{
                cout << a[front]<< endl;}}else{//判断队空条件：front==rearif(rear == front){
                cout <<"empty"<< endl;}else{
                cout << a[front]<< endl;
                front =(front +1)% MAXSIZE;}}}return0;}

重要注释：

• main函数之前是一些变量的声明和初始化，MAXSIZE等于n+1，用来更新指针
• 对此题而言栈满时push操作仍然需要从键盘上输入元素，否则将和输出结果不匹配
• 三种操作都需要事先判断栈空或者栈满，push和pop更新指针的操作一定不要漏掉

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