1.每日一题
原题链接——》戳我戳我：传送法阵
2.测试案例
输入：
310
push1
push2
front
push3
push4
pop
pop
pop
front
pop
输出：
1
full
1
2
3
empty
empty
3.思路分析
对于循环队列我们要考虑的问题主要是，什么时候表示队列为空，什么时候队列为满？
对于可存n个整型数据的队列
- 如果一个下标front指示队首，下标rear指示队尾；
- 如果
front=rear时，可以保证队列是空的，例如初始状态front=rear=0; - 如果
(rear+1)%(n+1)=front，即队列中如果再要存一个元素就只能覆盖front位置的元素了，说明此时队列为满
值得注意的细节是，对(n+1)取余，而不是对n取余。可以这么理解要判断队列满了，规定队列最多可以存n个元素，当循环队列中只剩下一个空闲存储单元时，队列就满了，这也是为什么代码中开辟的队列空间大小为（n+1)而不是n的缘由。
4.完整代码(数组实现)
importjava.util.*;
publicclassMain{
publicstaticvoidmain(String[] args){
Scannersca=newScanner(System.in);
intn=sca.nextInt();
intq=sca.nextInt();
sca.nextLine();
Strings;
//注意这里不是n,而是n+1
MyCirQueuequeue=newMyCirQueue(n+1);
for(inti=0;i<q;++i){
s=sca.nextLine();
Stringstrs[]=s.split(" ");
if(strs[0].equals("push")){
queue.push(Integer.parseInt(strs[1]));
}elseif(strs[0].equals("front")){
queue.front();
}else{
queue.pop();
}
}
}
}
classMyCirQueue{
intmaxSize;
intrear,front;
int []q;
publicMyCirQueue(intmaxSize){
this.maxSize=maxSize;
q=newint[maxSize];
rear=0;
front=0;
}
//添加元素
publicvoidpush(intval){
if(isFull()){
System.out.println("full");
}else{
//从队尾入队
q[rear]=val;
//队尾下标+1
rear=(rear+1)%maxSize;
}
}
//输出但不移除队首元素
publicvoidfront(){
if(isEmpty()){
System.out.println("empty");
}else{
//队首元素出列
System.out.println(q[front]);
}
}
//输出且移除队首元素
publicvoidpop(){
if(isEmpty()){
System.out.println("empty");
}else{
//队首元素出列
System.out.println(q[front]);
//队首下标+1
front=(front+1)%maxSize;
}
}
//判断队列是否为空
publicbooleanisEmpty(){
if(rear==front){
returntrue;
}
returnfalse;
}
//判断队列是否为满
publicbooleanisFull() {
if((rear+1)%maxSize==front){
returntrue;
}
returnfalse;
}
}
5.每日推荐
📚订阅专栏：『牛客刷题集锦』
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
