环形队列-java实现

其实,环形队列的变化具体就在于front指向了第一个数,而rear指向最后一个数的后一位

,然后环形嘛,就要注意越界问题,所以取模是必不可少的,总的来说还是比较容易

boolean isFull(){
 return (rear+1)%maxSize==front;
}

void add(int n){
arr[rear]=n;
rear=(rear+1)%maxSize;
}

int getFront(){
if(isEmpty()){
throw new RuntimeException("这都能错?")  
 }
int first=front;
front=(front+1)%maxSize;
return arr[first];
}

int getAll(){
if(isEmpty()){
....
 }
for(int i=front;i<fornt+maxSize;i++){
 System.out.print(arr[(i+maxSize)%maxSize]);
 }
}


}

大致就这个意思,在上面打的,可能会有点错误,谢谢

完整代码 

package queue;

import java.util.Scanner;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;

public class CircleArrayQueue {

	public static void main(String[] args) {
      //测试
		System.out.println("测试环形队列()");
		
		//1、创建一个环形队列
		CircleArray array = new CircleArray(4);
		//2.输入一个字符指令
		char input=' ';
		Scanner scanner = new Scanner(System.in);
		//3.设置一个控制循环的变量
		boolean loop=true;
		//4.遍历菜单
		while(loop) {
			System.out.println("(s)显示队列:");
			System.out.println("(e)退出程序:");
			System.out.println("(a)添加数据:");
			System.out.println("(g)取出数据");
			System.out.println("(l)查看头数据");
			//接收用户输入的字符
			input=scanner.next().charAt(0);//发现字符收集需要用charAt()
			switch(input) {
			case's':
				array.show();
				break;
			case'a':
				System.out.println("请输入一个数");
				int n=scanner.nextInt();
				array.addQueue(n);
				break;
			case'g':
				int value = array.getQueue();
				System.out.printf("取出的数据是%d\n",value);
				break;
			case'l':
				int look = array.look();
				System.out.printf("队列的头数据为%d\n",look);
				break;
			case'e'://退出
				scanner.close();//关闭流
				loop=false;//while循环终止
				break;
			}
		}
		//循环退出
		System.out.println("程序退出");
	}

}
class CircleArray{
	private int maxSize;
	private int front;//指向第一个数
	private int rear;//指向最后一个元素的后一个位置
	private int[]arr;//初始化一个数组模拟队列
	
	public CircleArray(int maxSize) {
		this.maxSize=maxSize;
        arr=new int[maxSize];
	}
	
	//是否满
	public boolean isFull() {
		//rear的下一个指向front ,%maxSize防止数组越界
		return (rear+1)%maxSize==front;
	}
	
	public boolean isEmpty() {
		return front==rear;
	}
	
	//添加队列
	public void addQueue(int n) {
		//1.首先判断队列是否为满
		if(isFull()) {
			System.out.println("队列已经满了!不能加入数据");
		}
		//2.直接加入数据
		arr[rear]=n;
		//3.rear需要后移
		rear=(rear+1)%maxSize;//记住不能溢出数组
	}
	
	//获取
	public int getQueue() {
		//1.先判断是否为空
		if(isEmpty()) {
			throw new RuntimeException("队列空,不能取数据");
		}
		//2.然后进行赋值
		int value=arr[front];
		//3.队列后移,将元素取出
		front=(front+1)%maxSize;//front不断后移,%maxSzie保证不越界
		return value;
	}
	
	//队列有效个数
	public int size() {
		return (rear-front+maxSize)%maxSize;//记住越界
	}
	
	//获取队列中所有数据
	public void show() {
		//1.首先判断是否有数据
		if(isEmpty()) {
			System.out.println("队列中啥也没有");
		}
		
		//2.从front开始遍历,因为是环形队列,所以要确保数量size,他是整个都可以遍历的到的,不会浪费资源
		for(int i=front;i<front+size();i++) {
			System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
		}
	}
	
	//看头数据
	public int look() {
		//1.首先判断是否有数据
		if(isEmpty()) {
			System.out.println("队列中无数据");
		}
		return arr[front];
	}
	
}

 

上一篇:2021-11-10


下一篇:数据结构--队列