数组模拟环形队列java（数据结构与算法）

你的名字 2023-10-01 21:09 11阅读 0赞

#### 思路： ####

#### ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_11_color_FFFFFF_t_70_g_se_x_16][] ####

####  ####

#### **背景** ####

**队列有两种实现方式：1、数组，2 、链表**

**在数组实现队列时，有的教科书中只说了队列满的条件是 (rear + 1) % manSize = front**

**这个公式真让人摸不着头脑**

**原来：这是数组模拟环形队列，才有的结果**

**队头 front ：初始值为0，指向队列的第一个元素**

**队尾 rear : 初始值为0 ，指向队列最后一个元素的下一位**

**对照以下环形图分析：当空队列新增一个元素时，rear++ ，rear变成1, 数组0的位置用于存放数据，rear不存放数据。**

**此时，如果再新增一个元素。rear++ ，rear变成2，数组1的位置存放数据。**

**队列满的条件是 (rear + 1) % manSize = front 由于rear留空，所以maxSize为8的数组，最多只能存放7位。当 rear为7时，(7+1)%8 = 0**

**队列中有效数据的个数是 (rear-front+maxSize)%manSize**

**由于是环形队列，所以rear 可能比front小，比如 rear = 1 ,front = 6 ，加上 maxSize 为了不用取绝对值，实际是|rear-front|%manSize，因为绝对值要调用Math的包。**

**可以对照的环形图来数，rear不保存值，得到是3个元素。**

**套用公式 (1-6+8)%8 = 3 % 8 = 3**

**为了便于理解，我画了一个同心圆**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA57u_5rap5aSc6KGM6ICF_size_20_color_FFFFFF_t_70_g_se_x_16][]

**图形演示：**

**假设maxsize=7**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_20_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_15_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_15_color_FFFFFF_t_70_g_se_x_16 1][]

package suanfa;
    
    import java.util.Scanner;
    
    public class xishuarr {
    	public static void main(String[] args) {
    		ArrayQueue Queue=new ArrayQueue(4);
    		char key=' ';//接受用户输入
    		Scanner scanner =new Scanner(System.in);
    		boolean loop=true;
    		while(loop) {
    			System.out.println("s(shou):显示队列");
    			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.show();
    				break;
    			case 'a':
    			System.out.println("请输入一个数");
    			int value=scanner.nextInt();
    			Queue.add(value);
    		    break;
    			case 'g':
    				try {
    					int res= Queue.get();
    					System.out.printf("取出的数据是%d\n",res);
    				} catch (Exception e) {
    					// TODO: handle exception
    					System.out.println(e.getMessage());
    				}
    				
    				break;
    			case 'h':
    				try {
    					int res= Queue.head();
    					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 ArrayQueue{
    	private int maxSize;//数组最大容量
    	private int front;//队列头
    	private int rear;//队列尾
    	private int[] arr;//该数据用于存放数据，模拟队列
    	
    	public ArrayQueue(int arrMaxSize) {
    		maxSize =arrMaxSize;
    		arr=new int[arrMaxSize];
    		front =0;//指向队列头部
    		rear=0;//指向队列尾
    	}
    	//判断队列是否为满
    	public boolean isfull() {
    		
    	        //因为是环形队列
    			return (rear+1)%maxSize==front;
    	
    		
    	}
    	//判断队列是否为空
    	public boolean isEmpty() {
    		
    		return rear==front;
    }
    	//添加数据到队列
    	public void add(int n){
    		if(isfull()) {
    			System.out.println("队列已满");
    			return ;
    		}
    		
    		arr[rear]=n;
    		rear=(rear+1)%maxSize;
    		
    		
    	}
    	//获取队列的数据,出队列
    	public int get(){
    		if(isEmpty()) {
    			//抛出一个异常
    		throw new RuntimeException("队列空,不能取数据");
    	}
    		
        int value=arr[front];
        
        
        front=(front+1)%maxSize;
    		
    	return value;
    	
    		
    	}
    	//显示队列的所有数据
    	public void show() {
    		
    		while(isEmpty()) {
    			
    			System.out.println("队列空的,没有数据-----");
    			return;
    		}
    		
    		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 head() {
    		if(isEmpty()) {
    			throw new RuntimeException("队列空的,没有数据");
    			
    		}
    		
    		return arr[front];
    	}
    	
    	
    	
    	
    	
    }

**本文部分内容参考CSDN博主「绿涩夜行者」的原创文章  
原文链接：https://blog.csdn.net/u013921288/article/details/123520874**

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_11_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/cc4fdcf823784193be0d8e80c8d1e4cc.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA57u_5rap5aSc6KGM6ICF_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/a49f173f67314827b23859fda0e0016e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA57u_5rap5aSc6KGM6ICF,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7543d619321d4a1c91dc875d4a52218c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_15_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/5f430d98f45847f5b90b9d71660f0a92.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_15_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/afc600ca601f46549aa10c92c0920190.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_15,color_FFFFFF,t_70,g_se,x_16