数组模拟环形队列

1.使用数组模拟环形队列的思路分析

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
6.在原来的队列上修改得到一个环形队列

2.代码实现

几个关键的点需要记住：

• 初始值rear=front=0;

• 新增了一个获取队列中数据个数的方法，数据个数为(rear-front+maxSize)%maxSize;

• 判断队列空的条件是rear == front;

• 判断队列满的条件是 (rear+1)%maxSize == front

• 遍历队列中所有元素：

  for(int i = front; i < front +Arrcount(); i++ ) {

          System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i % maxSize]);
      }
  

• 取出数据时需要一个临时变量来存储数据

  ​ int value = arr[front];
  ​ front = (front+1) % maxSize;
  ​ return value;

• 添加数据时的操作是

  ​ arr[rear] = n;
  ​ //rear后移，这里需要考虑取模
  ​ rear = (rear+1) % maxSize;

• 要显示头元素时只需要return arr[front]；

package queue;

import java.util.Scanner;

public class ArrayCircleQueue {
		//测试队列
		public static void main(String args[]) {
			CircleArrayQueue cqueue = new CircleArrayQueue(5);
			char key = ' ';
			boolean loop = true;
			Scanner in = new Scanner(System.in);
			while(loop) {
				
				System.out.println("s(show):显示队列");
				System.out.println("a(add):向队列中添加数据");
				System.out.println("g(get):从队列中取出一个数据");
				System.out.println("h(head):显示队列头部的数据");
				System.out.println("e(exit):退出程序");
				System.out.println("请选择操作：输入对应的字母");
				key = in.next().charAt(0);
			switch(key) {	
			case 's':
				try {
					cqueue.showQueue();
				} catch(Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'a':
				try {
					System.out.println("请输入要添加的数据：");
					int value = in.nextInt();
					cqueue.addQueue(value);
				} catch(Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'g':
				try {
					System.out.println("您获取的数据是"+cqueue.getQueue());
					
				} catch(Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'h':
				try {
					System.out.println("您获取的数据是"+cqueue.getHead());
					
				} catch(Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				loop = false;
				in.close();
				break;
			default:
				break;
			}
		}
}
}
//编写一个ArrayQueue类
class CircleArrayQueue {
	private int maxSize;
	private int front;
	private int rear;
	private int[] arr;
	
	//创建队列的构造器
	public CircleArrayQueue(int amaxSize) {
		maxSize = amaxSize;
		arr = new int[maxSize];
		front = 0;
		rear = 0;
	}
	//判断是否满
	public boolean isFull() {
		return (rear+1)%maxSize == front;
	}
	//判断是否为空
	public boolean isEmpty() {
		return rear == front;
	}
	
	//求出当前队列有效数据的个数
	public int Arrcount() {
		return (rear - front + maxSize) % maxSize;
	}
	//添加数据到队列中
	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 +Arrcount(); i++ ) {
			System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i % maxSize]);
		}
	}
	//显示头元素
	public int getHead() {
		if(isEmpty()) {
			throw new RuntimeException("队列空，没有数据");
		}
		return arr[front];
	}
}