如何用数组实现环形队列

上次实现了一个普通队列，但是普通队列存在的问题就是队列是一次性的，并不能够重复利用，所以这次来写环形队列，实现队列的复用。

环形队列

环形队列要比普通的队列复杂一些，要对原来的普通队列做一些调整。

1. 首先头指针front要做一些变化，原本的front = -1，此时要让front指向队列的第一个元素也就是arr[front]就是队列的第一个元素，front的初始值变为了0。

2. 尾指针rear也要进行一些改变，要让rear指向最后一个元素的后一个位置，因为希望空出一个空间作为约定，rear的初始值也为0。

3. 队列的判满发生了改变，原本的rear = MaxSize-1变成了(rear+1)% MaxSize = front此处不太好理解，但是大家把它想象成环形的就比较容易理解了，至于为什么取模计算就是防止数组下标越界，后面还会用到。

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

5. 队列中的有效个数为==(rear + MaxSize - front) % MaxSize==，这个就是求环形队列中的有效数据的个数，希望大家能记住。
   
   由上面的图片可以看出环形队列的一个存储过程，也可以看出在环形队列中最后的一个空间是空出来的，正好对应上面的尾指针指向最后的元素的后一个位置。下面我们来用代码实现一下。

6. 首先我们仍旧是要创建循环队列的类，然后在类中定义需求变量，再定义环形队列的构造器。

class CircleQueue{
    
	private int maxSize;
	private int arr[];
	private int front;
	private int rear;
	
	//创建循环队列构造器
	public CircleQueue(int arrMaxsSize) {
    
		// TODO Auto-generated constructor stub
		maxSize = arrMaxsSize;
		arr = new int[maxSize];
		front = 0;
		rear = 0;
	}
}

7. 判断队列是否已满

//判满
	public boolean isFull() {
    
		return (rear + 1) % maxSize == front;
	}

8. 判断队列是否为空

//判空
	public boolean isEmpty() {
    
		return front == rear;
	}

9. 添加元素进队列，此处需要注意的是，在普通队列中添加元素是将rear++ 然后 arr[rear] = n，因为普通队列中，rear就是指向最后的元素，但是在环形队列中rear指向的是数组中最后一个元素的后一个位置，所以直接将 arr[rear] = n把数据添加进去即可，然后再向后移动 rear，因为是环形队列，需要考虑下标不能越界，所以再对MaxSize取模即可。

//添加元素进队列
	public void addQueue(int n) {
    
		if (isFull()) {
    
			System.out.println("队列已满，无法添加！");
			return;
		}
		arr[rear] = n;
		//防止下标越界必须要进行取模运算例如1%4=1，因为1/4=商0余1，所以也就是相当于取余
		rear = (rear + 1) % maxSize;
	}

10. 出队列，此时出队列也有了些变化，在普通队列中原本的front = -1，所以在出队列的时候直接将front++ 然后 arr[front]即可，但是在环形队列中front = 0，直接指向了环形队列中的第一个数据，所以可以先建立临时变量对数据进行存储，然后再将front向后移即可，同样为了防止下标越界要对maxSize取模，最后返回临时变量值即可。

//出队列
	public int getQueue() {
    
		if (isEmpty()) {
    
			throw new RuntimeException("队列为空，无法取出数据");
		}
		int value = arr[front];
		//防止下标越界必须要进行取模运算例如1%4=1，因为1/4=商0余1，所以也就是相当于取余
		front = (front + 1) % maxSize;
		return value;
	}

11. 显示队列中的数据，当然还是对数组进行遍历，但是需要注意的是，我们要从头指针指向的数组开始遍历，在对数组进行遍历时仍要防止下标越界，所以还是要对maxSize取模，同样遍历结束的条件也发生了改变，那就是要求出环形对列中有多少个有效数据，也就是
    (rear + front -maxSzie) % maxSize。

public void show() {
    
		if (isEmpty()) {
    
			System.out.println("队列为空！");
			return;
		}
		//因为是环形队列所以要从front开始遍历所有数据，i循环的条件是数组中有效元素的个数
		//i要通过取模来防止下标越界
		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;
}

12. 显示头元素

public int headQueue() {
    
		if (isEmpty()) {
    
			throw new RuntimeException("这是一个空队列！");
		}
		return arr[front];
	}

13. 创建CircleQueue环形队列的对象，进行代码验证

public class CircleQueueDemo {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		CircleQueue circleQueue = new CircleQueue(3);
		char key = ' ';//用来接收一个字符
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		while(loop)
		{
    
			System.out.println("输入s显示队列");
			System.out.println("输入e退出队列");
			System.out.println("输入a添加队列");
			System.out.println("输入h显示头队列");
			System.out.println("输入g取出队列");
			key = scanner.next().charAt(0);//用来添加一个字符、
			switch (key) {
    
			case 'a':
				System.out.println("请输入要存储的数据：");
				int value = scanner.nextInt();
				circleQueue.addQueue(value);
				break;
			case 'h':
				try {
    
					int res = circleQueue.headQueue();
					System.out.printf("头队列数据是%d", res);
				} catch (Exception e) {
    
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 's':
				circleQueue.show();
				break;
			case 'g':
				try {
    
					int res = circleQueue.getQueue();
					System.out.printf("出队列的元素是：%d", res);
				} catch (Exception e) {
    
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
		}

	}
	
}