简单的算法：环形数组实现队列详细分析，

我不是女神ヾ 2023-01-05 12:37 106阅读 0赞

## 楔子 ##

2021-1-12，天气晴  
学习算法的第二天，嗯，头发还是一如既往的疯狂的掉，昨天在学习队列的过程中，我本以为：队列？就这啊！不就是一个先进先出，后进后出吗？这不有手就行？然后一写代码…(懵)啊，这是人学的玩意！！！，偶受不了了！哼╭(╯^╰)╮不管了，劳资今天不写了，想影响我的心态，不存在的。如果明天还拿不下你，我就去搞前端…。第二天：完了完了，还是不会呀，怎么办，偶不想写前端呀，就在这时，我的天灵盖发出一阵耀眼的光芒，随之，一道宛如远古英灵般的碎语在我的脑海中响起：8点了，起床写代码了，8点了，起床写代码了；然后我就醒了。起床洗漱，打开电脑，当我再次拿起昨天的代码，我发现我的思路异常清晰，好了，我编不下去了，直接进入正题吧！

--------------------

## 数组实现队列：思路一(有缺陷) ##

1.  设置maxSize表示队列的最大存储数
2.  设置两个指针，分别代表头部（head）和尾部（tail），**front**表示head，默认值为-1，指向队列的head元素（Element）的前一个位置；**rear**表示tail，默认值为-1，指向队列的tail的**有效**元素（注意，这里并不是指向队列的尾部，而是有效数据也就是你存入的数据中，最后一个元素）；
3.  将尾部指针往下移：rear+1
    
     *  当rear = front时，表示队列为空
     *  当尾部指针rear小于队列的最大下标maxSize-1时，表示队列还未满，则可以进行数据存入；
     *  当尾部指针rear大于队列的最大下标时，rear = maxSize - 1，表示队列已满，这时候无法存入数据

**代码实现**

package com.fufu.queue;
    /** * @function 队列demo * @author fufu * @version 1.8 */
    public class ArrayQueue { 
    	private int maxSize;//最大存储数
    	private int rear;//队列头
    	private int front;//队列尾
    	 int[] queueArr;//用来存数据的数组，模拟队列
    	
    	public ArrayQueue() { 
    		maxSize = 10;//默认队列的最大存储数为10
    		rear = -1;
    		front = -1;
    		queueArr = new int[maxSize];
    	}
    	
    	public ArrayQueue(int maxSize) { 
    		this.maxSize = maxSize;//初始化队列最大存储数
    		rear = -1;//指向队列的尾部数据(队列的最后一个数据)
    		front = -1;//指向队列头部，分析出front是指向队列头部的前一个位置 
    		queueArr = new int[maxSize];
    	}
    	
    	//判断队列是否为空
    	public boolean isEmpty() { 
    		return rear==front;
    	}
    	
    	//判断队列的数据是否已满
    	public boolean isFull() { 
    		return rear==maxSize-1;
    	}
    	
    	//添加一个数据到队列
    	public void addDataToQueue(int num) { 
    		//如果队列已经满了，则抛出异常
    		if(isFull()) { 
    			throw new RuntimeException("队列溢出...~~");
    		}
    		rear++;
    		queueArr[rear] = num;
    	}
    	
    	//获取\取出一个数据
    	public int getDataFromQueue() { 
    		if(isEmpty()) { 
    			throw new RuntimeException("PointNullException~~队列为null");
    		}
    		front++;
    		return queueArr[front];
    	}
    	
    	//显示队列数据
    	public void showQueueData() { 
    		if(isEmpty()) { 
    			System.out.println("队列为null");
    			return ;
    		}
    		for(int i=0;i<queueArr.length;i++) { 
    			System.out.printf("queueArr[%d]=%d\t",i,queueArr[i]);
    		}
    	}
    	
    	//显示队列头部数据
    	public int showQueueHeadData() { 
    		if(isEmpty()) { 
    			System.out.println("数据为空");
    			return -1;
    		}
    		front++;
    		return queueArr[front];
    	}
    }

**测试代码**

import java.util.InputMismatchException;
    import java.util.Random;
    import java.util.Scanner;
    
    public class ArrayQueueTest { 
    	public static void main(String[] args) { 
    		ArrayQueue aq = new ArrayQueue(3);
    		Scanner sc = new Scanner(System.in);
    		char c ;
    		boolean flag = true;
    		while(flag) { 
    			System.out.println("按下'a'添加队列数据");
    			System.out.println("按下's'显示队列全部数据");
    			System.out.println("按下'h'显示队列顶部数据");
    			System.out.println("按下'e'退出");
    			System.out.println("按下'g'获取一个数据");
    			c = sc.next().charAt(0);
    			switch(c) { 
    			case 'a':
    				try { 
    					System.out.println("请输入：");
    					int i = sc.nextInt();
    					aq.addDataToQueue(i);
    				}catch(InputMismatchException e) { 
    					throw new RuntimeException("输入数异常");
    				}
    				break;
    			case 's':
    				aq.showQueueData();
    				break;
    			case 'h':
    				int num = aq.showQueueHeadData();
    				System.out.println(num);
    				break;
    			case 'e':
    				flag=!flag;
    				break;
    			case 'g':
    				int num1 = aq.getDataFromQueue();
    				System.out.println(num1);
    				break;
    			}
    		}
    		System.out.println("程序结束！！");
    	}
    }

**测试如下**

按下'a'添加队列数据
    按下's'显示队列全部数据
    按下'h'显示队列顶部数据
    按下'e'退出
    按下'g'获取一个数据
    a
    请输入：
    1
    按下'a'添加队列数据
    按下's'显示队列全部数据
    按下'h'显示队列顶部数据
    按下'e'退出
    按下'g'获取一个数据
    a
    请输入：
    2
    按下'a'添加队列数据
    按下's'显示队列全部数据
    按下'h'显示队列顶部数据
    按下'e'退出
    按下'g'获取一个数据
    a
    请输入：
    3
    按下'a'添加队列数据
    按下's'显示队列全部数据
    按下'h'显示队列顶部数据
    按下'e'退出
    按下'g'获取一个数据
    s
    queueArr[0]=1	queueArr[1]=2	queueArr[2]=3	按下'a'添加队列数据
    按下's'显示队列全部数据
    按下'h'显示队列顶部数据
    按下'e'退出
    按下'g'获取一个数据
    h
    1
    按下'a'添加队列数据
    按下's'显示队列全部数据
    按下'h'显示队列顶部数据
    按下'e'退出
    按下'g'获取一个数据
    g
    2
    按下'a'添加队列数据
    按下's'显示队列全部数据
    按下'h'显示队列顶部数据
    按下'e'退出
    按下'g'获取一个数据
    h
    3
    按下'a'添加队列数据
    按下's'显示队列全部数据
    按下'h'显示队列顶部数据
    按下'e'退出
    按下'g'获取一个数据
    h
    数据为空
    -1
    按下'a'添加队列数据
    按下's'显示队列全部数据
    按下'h'显示队列顶部数据
    按下'e'退出
    按下'g'获取一个数据

可以看到，当我显示头部元素和获取一个元素，它的指针都会往后走，当指针超过了队列的最大存储数时，就会发生异常，也就是说，这种写法只能使用一次，也就是一次性代码

**推论：**  
Q：**显示头部元素为什么要让指针移动，不让它的指针移动不就行了；**

A：不行，front在设定上是指向头部元素的前一个位置，所以在显示的时候必须+1，当然，你可以设置一个boolean标志来让它只加一次，比如这样：

//显示队列头部数据
    	int i=0;
    	public int showQueueHeadData() { 
    		
    		if(isEmpty()) { 
    			System.out.println("数据为空");
    			return -1;
    		}
    		if(i==0) { 
    			front++;
    			i++;
    		}
    		return queueArr[front];
    	}

但是，如果这时候队列里只有一个数据，那么我们显示了一次之后，front + 1会等于rear，就会出现明明还有一个数据，却显示为空，多个数据也是如此

Q:**可是让它每显示一次front就移动一次的话，那我如果一直显示就会造成front>=rear的情况呀**

A：额！关于这一点，我也辩解不了，只能说是这个垃圾算法的问题吧（啊，哈哈哈哈）；

Q：**好，这个先不提，就拿存数据来说，我先存3个数据，然后再取出数据3次，这时候显示队列为空，然后，我再添加数据，这时候却显示队列已满，数据溢出，什么鬼？**

A：那肯定呀！因为你压根就没有把指针调回去，当存入三个数据时，rear（初始值为-1）指针会移动3次，这时候rear = maxSize - 1 = 2(在代码中我设置的最大存储数为3)，接着，又取数据3次，front又移动3次，3次之后，就会出现一个神奇的问题，front = rear = 2，根据我们之前的队列为空判断，front = rear的时候队列为空，但是，明明队列是空的却不能添加数据，显示队列已满，这不是自相矛盾吗？（再次感叹一句，垃圾算法！）

Q:**那你就不能加个判断把指针调回去吗？**

A：好，我试试看，唉，经过我半小时的研究，发现还是不可行，又引申出来好多问题，比如说，在添加数据的时候，当我们添加了3次数据之后，再取出第一个数据，这时候，front = 0，rear = 2；因为取出了一个数据，按道理来说，我们应该是可以再添加一个数据的，于是乎，我推出了可以添加数据的条件，当rear>2&&front!=-1时，才能添加数据，也就是rear>最大存储数时，而front刚好移动过，说明取出过数据，这时候，我们就可以把数据添加到数组的第一位，而这样的想法想要成立，需要考虑另外几种情况，如果我们要将数据添加进去，那么front的指针必须回调，重新指向-1，而rear将作为添加的数据的下标，为0，但是rear是指向末尾的，如果是按照环形的来看的话，新添加的数据确实是为末尾，但是，如果这时候我们再取出一个数据，front指针上移，front = 0，这时候，front又=>rear，那么，我们又不能添加数据了，按照我之前推论的条件rear>2&&front!=-1,很明显是不成立的。我塔喵的心态崩了呀

Q：**那…**

A：打住，别钻牛角尖了，后面我也想过用一个变量来代替rear作为赋值的下标，但又会引出很多其他问题，这么下去浪费的时间太多了，先打住吧，以后有机会再回看，我们先换一种方法来试试

Q：**难道，你…唉，终于还是要用了吗？**

A：没错，我已经决定了，即便耗尽此身头发，也要追求算法的极致

## 数组实现队列：思路二 ##

由于思路一无法完全的模拟队列，故引申出第二张思路：**环形数组模拟队列实现**  
思路分析：

1.  front变量调整：front指向队列的第一个元素，也就是说arr\[front\]就是队列的第一个元素，front的初始值为0
2.  rear变量调整：rear指向队列的最后一个元素的后一个位置，因为希望它空出一个空间作为约定。rear的初始值为0
3.  当队列满时：应有条件(rear + 1) % maxSize = front【满】  
    **解释：** 假设maxSize的值为5，那么，当我们有3个数据的时候，rear指向其后一个位置，及rear=4，这时候还需要留一个空间作为，故rear + 1，其值刚好等于maxSize，front的初始值为0，所以条件成立；%是为了实现环形的一个效果，我们知道，一个数%另一个数，其值一定在0到这个数之间；
4.  队列为空时：应有条件rear == front【空】
5.  我们还需要分析，队列中的有效数据的个数：应有（rear + maxSize - front） % maxSize;

**代码实现：**

package com.fufu.circlequeue;
    
    public class ArrayCricleQueue { 
    	private int front;//指向队列的第一个元素
    	private int rear;//指向队列的最后一个元素的后一个位置
    	private int maxSize;//队列的最大存储数
    	private int[] cricleArr;//模拟环形队列存储数据的数组
    	
    	//构造
    	public ArrayCricleQueue(int maxSize) { 
    		this.maxSize = maxSize;
    		cricleArr = new int[maxSize];
    	}
    	
    	//判断队列是否已满
    	public boolean isFull() { 
    		return (rear+1)%maxSize==front;
    	}
    	
    	//判断队列是否为空
    	public boolean isEmpty() { 
    		return front == rear;
    	}
    	
    	//添加一个元素到队列中
    	public void addElement(int n) { 
    		if(isFull()) { 
    			throw new RuntimeException("DataOverFlowException~~~数据溢出异常");
    		}
    		cricleArr[rear] = n;
    		rear = (rear+1) % maxSize;
    // System.out.println("rear:"+rear);
    	}
    	
    	//获取队列的一个元素
    	public int get() { 
    		if(isEmpty()) { 
    			throw new RuntimeException("PointNullException~~~队列为空");
    		}
    		int value = cricleArr[front];
    		front = (front+1) % maxSize;
    // System.out.println("front:"+front);
    		return value;
    	}
    	
    	//显示当前队列的全部元素
    	public void showAllElement() { 
    		if(isEmpty()) { 
    			System.out.println("当前队列为空");
    		}
    // System.out.print("front:"+front+" "+"rear:"+rear+" ");
    		for(int i=front;i<front+size();i++) { 
    			System.out.printf("cricleArr[%d]=%d\t",i%maxSize,cricleArr[i%maxSize]);
    		}
    		System.out.println();
    	}
    	
    	//获取队列的有效数据
    	public int size() { 
    		return (rear + maxSize - front) % maxSize;
    	}
    
    }

**运行测试**

package com.fufu.circlequeue;
    
    public class ArrayCricleQueueTest { 
    	public static void main(String[] args) { 
    		ArrayCricleQueue acq = new ArrayCricleQueue(3);
    		acq.addElement(2);
    		acq.addElement(5);
    // acq.addElement(10);有一块空间需要留作约定，所以当可存数据为n时，实践的可用空间为n-1
    		acq.showAllElement();
    		acq.get();
    		acq.get();
    		acq.showAllElement();
    		acq.addElement(3);
    		acq.addElement(4);
    		acq.showAllElement();
    	}
    
    }

**运行结果**

rear:1
    rear:2
    front:0 rear:2 cricleArr[0]=2	cricleArr[1]=5	
    front:1
    front:2
    当前队列为空
    front:2 rear:2 
    rear:0
    rear:1
    front:2 rear:1 cricleArr[2]=3	cricleArr[0]=4

嗯，这样就基本实现了队列的一个效果了；

--------------------

## 总结 ##

在第一种思路中，它的缺陷在于无法重复的使用，只能使用一次，其根本原因在于指针的指向一直在往上走，没有重新调零，如果想要实现第一种思路，可以根据特定条件对指针进行调0，但是这样引申出来的问题太多了，从实用性来说，并不适合，但是从算法性来说的话，这是一个思考的过程，有兴趣可以研究研究。

在第二种思路中，在思路一的方式上进行了巧妙的改变，将数组想象成一个环形的，也就是以环形数组的思维去实现它；在思路一的基础上，对指针进行了一个调整，front指向当前队列第一个元素，rear指向队列的最后一个数据的后一个位置，这样调整的意义在于，我们每次添加一个元素，rear都会改变，让rear指向最后一个元素的后一个位置，因为需要空一个一个空间来作为约定，这个约定具体是干嘛的？我只能说它是该算法的核心思想，是一种比较抽象的思维理念，不好用言语来形容，当rear的指向超过了队列最大存储数的范围，那么就对它进行调0，这么说也不太合适，可以把它想象成一个环形的，无论它怎么走都是在这个环里面，这里巧妙的使用了%，我们知道，一个数%另一个数，其取值范围始终在0到这个数之间，而%【取模】也是环形思想的最重要的部分，当然，环形数组其本质还是数组，当我们进行取值的时候，如果之前存入了值，取出并不代表数组里的元素被取出了，实际上，它是通过不停的对数组进行复制操作来完成存值和取值的；