数组模拟环形队列

川长思鸟来 2024-03-30 17:16 83阅读 0赞

取模方式实现环形队列

分析说明：

1.尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,  
这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front 满\]

2.rear == front \[空\]

3.分析示意图

![在这里插入图片描述][16422f31074040cf98308ddbcc9cf942.png]  
分析思路：  
1.//front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr\[front\] 就是队列的第一个元素  
//front 的初始值 = 0

2.//rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.  
//rear 的初始值 = 0

3.当队列满时，条件是 (rear + 1)%maxSize == front;

4.队列为空的条件 rear == front

5.当我们这样分析，队列中有效的个数 (rear + maxSize - front) % maxSize;

package com.atguigu.queue;
    
    import java.util.Scanner;
    
    public class CircleArrayQueueDemo {
    
    	public static void main(String[] args) {
    		
    		//测试一把
    		//创建一个环形队列
    		CircleArray queue = new CircleArray(4);//说明设置4，其队列有效数据最大是3
    		char key = ' ';//接收用户输入
    		Scanner scanner = new Scanner(System.in);
    		boolean loop = true;
    		//输出一个菜单
    		while(loop) {
    			System.out.println("s(show):显示队列");
    			System.out.println("e(exit):退出程序");
    			System.out.println("a(add):添加数据到队列");
    			System.out.println("g(get):从队列取出数据");
    			System.out.println("h(head):查看队列头的数据");
    			key = scanner.next().charAt(0);//接收一个字符
    			switch (key) {
    			case 's':
    				queue.showQueue();
    				break;
    			case 'a':
    				System.out.println("输出一个数");
    				int value = scanner.nextInt();
    				queue.addQueue(value);
    				break;
    			case'g':
    				try {
    					int res = queue.getQueue();
    					System.out.printf("取出的数据是%d\n",res);
    				} catch (Exception e) {
    					// TODO: handle exception
    					System.out.println(e.getMessage());
    				}
    				break;
    			case'h':
    				try {
    					int res = queue.getQueue();
    					System.out.printf("队列头的数据是%d\n",res);
    				} catch (Exception e) {
    					// TODO: handle exception
    					System.out.println(e.getMessage());
    				}
    				break;
    			case'e':
    				scanner.close();
    				loop = false;
    				break;
    			default:
    				break;
    			}
    		}
    		System.out.println("程序退出");
    	}
    
    }
    
    
    class CircleArray{
    	private int maxSize;//表示数组的最大容量
    	//front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
    	//front 的初始值 = 0
    	private int front;//队列头
    	//rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定. 
    	//rear 的初始值 = 0
    	private int rear;//队列尾
    	private int[] arr;//该数据用于存放数据，模拟队列
    	
    	public CircleArray(int arrMaxsize) {
    		maxSize = arrMaxsize;
    		arr = new int[maxSize];
    		
    	}
    	
    	//判断队列是否满
    	public boolean isFull() {
    		return(rear + 1)%maxSize == front;
    		
    	}
    	//判断队列是否为空
    	public boolean isEmpty() {
    		return rear == front;
    	}
    	//添加数据到队列
    	public void addQueue(int n) {
    	//判断队列是否满
    	if(isFull()) {
    		System.out.println("队列满不能加入数据~~~");
    		return;
    	}
    		//直接将数据加入
    		arr[rear] = n;
    		//将rear后移，这里必须考虑取模
    		rear = (rear + 1) % maxSize;
    	}
    	//获取队列数据，出队列
    	public int getQueue() {
    		//判断是否空
    		if(isEmpty()) {
    			//通过抛出异常
    			throw new RuntimeException("队列空，不能取数据~~~");
    		}
    		//这里需要分析出front是指向队列的第一个元素
    		//1.先把front对应的值保留到一个临时变量
    		//2.将front后移
    		//3.将临时保留的变量返回
    		int value = arr[front];
    		front = (front + 1) % maxSize;
    		return value;
    	}
    		
    	//显示队列的所有数据
    			public void showQueue() {
    				//遍历
    				if(isEmpty()) {
    					System.out.println("队列空的没有数据~~~");
    					return;
    				}
    				//思路:从front开始遍历，遍历多少个元素
    					
    				for (int i = front; i < front + size(); i++) {
    					System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
    				}
    			}
    				
    			//求出当前队列有效数据的个数
    			public int size() {
    				return (rear + maxSize - front) % maxSize;
    			}
    			//显示队列的头部数据，注意不是取出数据
    			public int headQueue() {
    				//判断
    				if(isEmpty()) {
    					throw new RuntimeException("队列空的没有数据~~~");
    				}
    				return arr[front];
    			}
    		}

[16422f31074040cf98308ddbcc9cf942.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4ded93b43b6447599676de34de4db03b.png