『牛客|每日一题』循环队列

活动地址：CSDN21天学习挑战赛

👨‍🎓作者简介：一位喜欢写作，计科专业大二菜鸟
🏡个人主页：starry陆离

🕒首发日期：2022年8月20日星期六

🍁每日推荐：牛客网-面试神器

『牛客|每日一题』循环队列

• 1.每日一题
• 2.测试案例
• 3.思路分析
• 4.完整代码(数组实现)
• 5.每日推荐

1.每日一题

原题链接——》戳我戳我：传送法阵

2.测试案例

输入：

3 10
push 1
push 2
front
push 3
push 4
pop
pop
pop
front
pop
1
2
3
4
5
6
7
8
9
10
11

输出：

1
full
1
2
3
empty
empty
1
2
3
4
5
6
7

3.思路分析

对于循环队列我们要考虑的问题主要是，什么时候表示队列为空，什么时候队列为满？

对于可存n个整型数据的队列

• 如果一个下标front指示队首，下标rear指示队尾；
• 如果front=rear时，可以保证队列是空的，例如初始状态front=rear=0;
• 如果(rear+1)%(n+1)=front，即队列中如果再要存一个元素就只能覆盖front位置的元素了，说明此时队列为满

值得注意的细节是，对(n+1)取余，而不是对n取余。可以这么理解要判断队列满了，规定队列最多可以存n个元素，当循环队列中只剩下一个空闲存储单元时，队列就满了，这也是为什么代码中开辟的队列空间大小为（n+1)而不是n的缘由。

4.完整代码(数组实现)

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sca=new Scanner(System.in);
        int n=sca.nextInt();
        int q=sca.nextInt();
        sca.nextLine();
        String s;
        //注意这里不是n,而是n+1
        MyCirQueue queue=new MyCirQueue(n+1);
        for(int i=0;i<q;++i){
            s=sca.nextLine();
            String strs[]=s.split(" ");
            if(strs[0].equals("push")){
                queue.push(Integer.parseInt(strs[1]));
            }else if(strs[0].equals("front")){
                queue.front();
            }else{
                queue.pop();
            }
        }
    }
}
class MyCirQueue{
    int maxSize;
    int rear,front;
    int []q;
    public MyCirQueue(int maxSize){
        this.maxSize=maxSize;
        q=new int[maxSize];
        rear=0;
        front=0;
    }
    
    //添加元素
    public void push(int val){
        if(isFull()){
            System.out.println("full");
        }else{
        	//从队尾入队
            q[rear]=val;
            //队尾下标+1
            rear=(rear+1)%maxSize;
        }
    }
    
    //输出但不移除队首元素
    public void front(){
        if(isEmpty()){
            System.out.println("empty");
        }else{
        	//队首元素出列
            System.out.println(q[front]);
        }
    }
    
    //输出且移除队首元素
    public void pop(){
        if(isEmpty()){
            System.out.println("empty");
        }else{
        	//队首元素出列
            System.out.println(q[front]);
            //队首下标+1
            front=(front+1)%maxSize;
        }
    }
    
    //判断队列是否为空
    public boolean isEmpty(){
        if(rear==front){
            return true;
        }
        return false;
    }
    
    //判断队列是否为满
    public boolean isFull() {
    	if((rear+1)%maxSize==front){
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

5.每日推荐

📚订阅专栏：『牛客刷题集锦』

🍁每日推荐：基础算法无论在研究生面试还是求职面试都是十分重要的一环，这里推荐一款算法面试神器：牛客网-面试神器；算法题只有多刷勤刷才能保持思路与手感，大家赶紧行动起来吧（温馨提示：常见的面试问答题库也很nice哦）

如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦